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.
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 .
over a test case.
For of the maximum score:
over a test case.
For each query, print the number of ways of choosing non-empty subsequences, modulo , on a new line.
Sample Input 0
Sample Output 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.