Problem Description

Bessie has gotten a new phone with a 9-key keypad, laid out as follows:

123
456
789

Bessie is in a hurry and is trying to type a given phone number, so she decides to save time by using one of her hooves to press multiple buttons at once. Specifically, Bessie's hoof may press a single key, two keys that share an edge (there are $12$ such possibilities), or the four keys that form a square ($1245$, $2356$, $4578$, $5689$).

For example, if the phone number Bessie wants to type is $123659874$, she might try to save time by pressing keys in the following way:

1. Press $1$ and $2$ at the same time.
2. Press $3$.
3. Press $6,5,9,8$ at the same time.
4. Press $7$ and $4$ at the same time.

Unfortunately, Bessie greatly overestimated her ability to do this task—if Bessie's hoof presses multiple keys at the same time, then all of those keys will be entered in an arbitrary order. So if Bessie tries to press keys in the sequence above, the phone number she ends up typing could be $123596847$ or $213659874$ (or any other possible sequence).

Given a sequence that Bessie has already typed, compute the number of phone numbers she might have intended to type, modulo $10^9+7$.

Input Format

The first line contains an integer $T$ ($1\le T\le 10$), representing the number of independent test cases.

The next $T$ lines each contain a non-empty digit string consisting only of digits from $1$ to $9$. It is guaranteed that the total length of all digit strings in the input does not exceed $10^5$.

Output Format

For each test case, output the number of phone numbers Bessie might have intended to type, modulo $10^9+7$.

5
1478
4455
5968
31313211
123659874

5
2
24
3
255

Hint

Sample Explanation

For the first test case, Bessie might have intended to type one of the following five phone numbers:

1478
1487
4178
4187
1748

For example, if Bessie intended to type $4187$, she could have tried to press $1$ and $4$ at the same time, and then press $7$ and $8$ at the same time.

For the third test case, since these digits form a square, any permutation of the typed sequence could be the phone number Bessie intended.

Constraints

• For test cases $2\sim 3$, the length of every phone number is at most $8$.
• For test cases $4\sim 5$, each phone number contains only $1,2$ and $3$.
• For test cases $6\sim 7$, each phone number does not contain $5$.
• For test cases $8\sim 9$, each phone number contains only $5,6,8,9$.
• For test cases $10\sim 12$, the total length of all phone numbers does not exceed $10^2$.
• For test cases $13\sim 15$, the total length of all phone numbers does not exceed $10^3$.
• For test cases $16\sim 18$, the total length of all phone numbers does not exceed $10^4$.
• For test cases $19\sim 21$, there are no additional constraints.

Translated by ChatGPT 5