We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Shashank and the Palindromic Strings

Shashank and the Palindromic Strings

Shashank loves strings, but he loves palindromic strings the most. He has a list of strings, , where each string, , consists of lowercase English alphabetic letters. Shashank wants to count the number of ways of choosing non-empty subsequences such that the following conditions are satisfied:

  1. is a subsequence of string , is a subsequence of string , is a subsequence of string , , and is a subsequence of string .
  2. is a palindromic string, where + denotes the string concatenation operator.

You are given queries where each query consists of some list, . For each query, find and print the number of ways Shashank can choose non-empty subsequences satisfying the criteria above, modulo , on a new line.

Note: Two subsequences consisting of the same characters are considered to be different if their characters came from different indices in the original string.

Input Format

The first line contains a single integer, , denoting the number of queries. The subsequent lines describe each query in the following format:

  • The first line contains an integer, , denoting the size of the list.
  • Each line of the subsequent lines contains a non-empty string describing .

Constraints

  • over a test case.

For of the maximum score:

  • over a test case.

Output Format

For each query, print the number of ways of choosing non-empty subsequences, modulo , on a new line.

Sample Input 0

3
3
aa
b
aa
3
a
b
c
2
abc
abc

Sample Output 0

5
0
9

Explanation 0

The first two queries are explained below:

  1. We can choose the following five subsequences:

    1. , , , where is the first character of and is the first character of .
    2. , , , where is the second character of and is the second character of .
    3. , , , where is the first character of and is the second character of .
    4. , , , where is the second character of and is the first character of .
    5. , ,

    Thus, we print the result of on a new line.

  2. There is no way to choose non-empty subsequences such that their concatenation results in a palindrome, as each string contains unique characters. Thus, we print on a new line.