Phone Numbers

Bessie has a new cell phone with nine buttons, laid out as follows:

123
456
789

Bessie is typing a phone number in a hurry, so she saves time by pressing several buttons at once with one of her hooves. Her hoof may press a single digit, two digits that share a side (twelve possible pairs in total), or four digits that form a square (1245, 2356, 4578, or 5689).

For example, if the phone number Bessie wants to type is 123659874, she might try the following.

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

Bessie greatly overestimated her skill. When her hoof presses several buttons at once, the digits are typed in arbitrary order. So the presses above may produce 123596847, 213659874, or many other sequences.

Given a sequence of digits that Bessie has typed, count the phone numbers she could have been trying to type, modulo $10^9+7$.

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

Each of the next $T$ lines contains a nonempty string of the digits 1 through 9. The total length of these strings does not exceed $10^5$.

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

For the first case, Bessie might be trying to type any of the following five phone numbers:

1478
1487
4178
4187
1748

For example, if Bessie was trying to type 4187, she might have pressed 1 and 4 at the same time and then pressed 7 and 8 at the same time.

For the third case, the numbers form a square, so Bessie might have been trying to type any permutation of the input sequence.