- Prepare
- Algorithms
- Dynamic Programming
- Shashank and the Palindromic Strings

# 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:

- is a subsequence of string , is a subsequence of string , is a subsequence of string , , and is a subsequence of string .
- 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:

We can choose the following five subsequences:

- , , , where is the first character of and is the first character of .
- , , , where is the second character of and is the second character of .
- , , , where is the first character of and is the second character of .
- , , , where is the second character of and is the first character of .
- , ,

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

- 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.