#P5957. [Usaco2022 Feb]Phone Numbers P
[Usaco2022 Feb]Phone Numbers P
题目描述
本题源比赛时限为 秒。
Bessie 的手机有九个数字键,排列如下。
123
456
789
为了更快输入号码,Bessie 的一只蹄子一次可以按下一个键、两个共边的键(共十二对),或者四个排成一个 正方形的键(1245、2356、4578、5689)。同一次按下的数字会以任意顺序输入到手机中,但不会与另一次按下的数字交错。
例如,想输入 123659874,可以依次按下 、、、。实际的输入结果也可能是 123596847、213659874 等。
给出手机实际收到的数字串,求 Bessie 原本可能想输入的不同号码数,对 取模。
输入格式
第一行一个整数 (),表示独立的数据组数。接下来 行,每行一个只由数字 1 到 9 组成的非空字符串。所有字符串的长度之和不超过 。
输出格式
每组数据输出一行,写出可能的不同号码数对 取模的结果。
样例 #1
样例输入 #1
5
1478
4455
5968
31313211
123659874
样例输出 #1
5
2
24
3
255
样例解释 #1
第 组的五个可能号码是 1478、1487、4178、4187、1748。如果原本想输入 4187,她可以先同时按下 ,再同时按下 。第 组的四个数字构成一个正方形,任意排列都可能是原号码。
测试点性质
- 测试点 2–3 中,每个号码长度不超过 。
- 测试点 4–5 中,号码只含
1、2、3。 - 测试点 6–7 的号码不含
5。 - 测试点 8–9 的号码只含
5、6、8、9。 - 测试点 10–12、13–15、16–18 的字符串长度之和分别不超过 、、。
- 测试点 19–21 无额外限制。