8158: USACO 2022 February Contest, Platinum Problem 3. Phone Numbers
[Creator : ]
Description
Bessie has a new cell phone with nine buttons, laid out as follows:
Bessie is trying to type out a given phone number in a hurry, so she decides to save time by pressing multiple buttons at the same time with one of her hooves. Specifically, Bessie's hoof might press a single digit, two digits that share a side (for twelve possible pairs in total), or four digits that form a square (1245, 2356, 4578, or 5689).
For example, if the phone number Bessie is trying to type is 123659874, she might attempt to save time by
Given a sequence of digits that Bessie has typed, count the number of phone numbers that she could have been trying to type modulo $10^9+7$.
123 456 789
Bessie is trying to type out a given phone number in a hurry, so she decides to save time by pressing multiple buttons at the same time with one of her hooves. Specifically, Bessie's hoof might press a single digit, two digits that share a side (for twelve possible pairs in total), or four digits that form a square (1245, 2356, 4578, or 5689).
For example, if the phone number Bessie is trying to type is 123659874, she might attempt to save time by
- Pressing 1 and 2 at the same time.
- Pressing 3.
- Pressing 6, 5, 9, and 8 at the same time.
- Pressing 7 and 4 at the same time.
Given a sequence of digits that Bessie has typed, count the number of phone numbers that she could have been trying to type modulo $10^9+7$.
Input
The first line contains T (1≤T≤10), the number of independent test cases to solve. The next T lines each contain a nonempty string of the digits 1 through 9.
It is guaranteed that the total length of these strings does not exceed $10^5$.
It is guaranteed that the total length of these strings does not exceed $10^5$.
Output
For each test case, the number of phone numbers Bessie might have been trying to type modulo $10^9+7$.
Sample 1 Input
5
1478
4455
5968
31313211
123659874
Sample 1 Output
5
2
24
3
255
For the first case, Bessie might be trying to type any of the following five phone numbers:
For example, if Bessie was trying to type 4187, she might have tried pressing 1 and 4 at the same time and then tried pressing 7 and 8 at the same time.
For the third case, as the numbers form a square, Bessie might have been trying to type any permutation of the input sequence.
1478 1487 4178 4187 1748
For example, if Bessie was trying to type 4187, she might have tried pressing 1 and 4 at the same time and then tried pressing 7 and 8 at the same time.
For the third case, as the numbers form a square, Bessie might have been trying to type any permutation of the input sequence.