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`

, and`d`

.

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