We call a string, , consisting of the letters in the set a perfect string if both the conditions below are true:
where denotes the number of occurrences of character in . For example, the diagram below demonstrates why is a perfect string:
Solve queries, where each query consists of a string, . For each query, print the number of non-empty subsequences of that are perfect strings. As this number can be very large, print it modulo .
Input Format
The first line contains an integer, , denoting the number of queries.
Each of the subsequent lines contains string for a query.
Constraints
- String consists only of the following characters:
a,b,c, andd.
Subtask
- For of the total score, .
Output Format
For each , print the number of non-empty subsequences of that are perfect strings, modulo , on a new line.
Sample Input 0
3
abcd
cad
dcc
Sample Output 0
3
1
2
Explanation 0
We peform the following queries:
- has non-empty perfect subsequences: , , and . Thus, the answer is .
- has non-empty perfect subsequence: . Thus, the answer is .
- has non-empty perfect subsequences: and . Note that, while both these strings contain the same characters, they are distinct subsequences of (i.e., and ). Thus, the answer is .