P6978: 电话号码
传统题
4.000s
时间限制
512MB
内存限制
2 提交
1 解决
【题目描述】
【题目描述】
Bessie
得到了一个新的手机，上面有九个按键，如下排列：
123
456
789
Bessie
正试图快速输入一个给定的电话号码，因此她决定用一只蹄子同时按下多个按钮来节省时间。 具体地说，Bessie 的蹄子可以按下一个数字，两个共边的数字（总共有十二个可能的数对），或者形成一个正方形的四个数字（1245，2356，4578 或 5689）。
例如，如果 Bessie
试图输入的电话号码是 123659874，为了节省时间，她可以：
(1)
同时按下 1
和 2。
(2)
按下 3
。
(3)
同时按下 6
，5，9 和 8。
(4)
同时按下 7
和 4。
不幸的是，Bessie
大大高估了她执行这项任务的技能水平——如果 Bessie 的蹄子同时按下多个按钮，那么所有的数字可能会以任意顺序被输入。因此，如果 Bessie 尝试以上述顺序按键，她最终可能会打出 123596847 或 213659874（或许多其他可能性之一）。
给定 Bessie
打出的数字序列，计算她可能尝试输入的电话号码的数量，答案对 10
^9+7
取模。
**注意：本题的时间限制为 4 秒，通常限制的两倍。**
【
输入格式】
（从终端 /
标准输入读入）：
输入的第一行包含 T
（1≤T≤10
），为需要独立求解的子测试用例的数量。
以下 T
行每行包含一个由数字 1 到 9 组成的非空字符串。输入保证所有字符串的长度和不超过 10^5
。
【
输出格式】
（输出至终端 /
标准输出）：
对于每一个子测试用例，输出她可能尝试输入的电话号码的数量，答案对 10
^9+7
取模。
【
输入样例】
：
5
1478
4455
5968
31313211
123659874
输出样例：
5
2
24
3
255
【样例说明】
对于第一个子测试用例，Bessie
可能尝试输入的是以下四个电话号码之一：
1478
1487
4178
4187
1748
例如，如果 Bessie
尝试输入 4187，她可能会尝试同时按下 1 和 4，然后尝试同时按下 7 和 8。
对于第三个子测试用例，由于这些数字组成一个正方形，Bessie
可能尝试输入的是这个序列的任意排列。
【
测试点性质】
：
测试点 2-3
中，所有电话号码的长度不超过 8。
测试点 4-5
中，电话号码仅包含 1，2 和 3。
测试点 6-7
中，电话号码不包含数字 5。
测试点 8-9
中，电话号码仅包含 5，6，8 和 9。
测试点 10-12
中，所有字符串的长度和不超过 10^2
。
测试点 13-15
中，所有字符串的长度和不超过 10^3
。
测试点 16-18
中，所有字符串的长度和不超过 10^4
。
测试点 19-21
中，没有额外限制。