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

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

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

Unfortunately, Bessie drastically overestimated her skill at performing this
task - if Bessie's hoof pressess multiple buttons at the same time, then all of
the digits will be typed in arbitrary order. So if Bessie attempts the above
sequence of presses, she may end up typing 123596847 or 213659874 instead (or
one of many other possibilities).

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\).

*Note: the time limit for this problem is 4s, twice the default.*

Problem credits: Nick Wu

SCORING

• In inputs 2-3, all phone numbers have length at most \(8\).
• In inputs 4-5, the phone number only contains 1, 2, and 3.
• In inputs 6-7, the phone number doesn't contain the digit 5.
• In inputs 8-9, the phone number only contains 5, 6, 8, and 9.
• In inputs 10-12, the sum of the string lengths does not exceed \(10^2\).
• In inputs 13-15, the sum of the string lengths does not exceed \(10^3\).
• In inputs 16-18, the sum of the string lengths does not exceed \(10^4\).
• In inputs 19-21, no additional constraints.

Problem credits: Nick Wu

The first line contains \(T\) (\(1\le T\le 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\).

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

riseoj 작성

출처 올림피아드 > USACO > 2021-2022 > February > Platinum