#P5957. [Usaco2022 Feb]Phone Numbers P

    ID: 4957 传统题 1500ms 512MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-字符串子集构造动态规划自动机 DP计数 DP状压 DP滚动数组模拟与实现技巧稀疏状态重置CF2700

[Usaco2022 Feb]Phone Numbers P

题目描述

本题源比赛时限为 44 秒。

Bessie 的手机有九个数字键,排列如下。

123
456
789

为了更快输入号码,Bessie 的一只蹄子一次可以按下一个键、两个共边的键(共十二对),或者四个排成一个 2×22\times2 正方形的键(1245、2356、4578、5689)。同一次按下的数字会以任意顺序输入到手机中,但不会与另一次按下的数字交错。

例如,想输入 123659874,可以依次按下 {1,2}\{1,2\}、{3}\{3\}、{6,5,9,8}\{6,5,9,8\}、{7,4}\{7,4\}。实际的输入结果也可能是 123596847、213659874 等。

给出手机实际收到的数字串,求 Bessie 原本可能想输入的不同号码数,对 109+710^9+7 取模。

输入格式

第一行一个整数 TT(1≤T≤101\le T\le10),表示独立的数据组数。接下来 TT 行,每行一个只由数字 1 到 9 组成的非空字符串。所有字符串的长度之和不超过 10510^5。

输出格式

每组数据输出一行,写出可能的不同号码数对 109+710^9+7 取模的结果。

样例 #1

样例输入 #1

5
1478
4455
5968
31313211
123659874

样例输出 #1

5
2
24
3
255

样例解释 #1

第 11 组的五个可能号码是 1478、1487、4178、4187、1748。如果原本想输入 4187,她可以先同时按下 4,14,1,再同时按下 8,78,7。第 33 组的四个数字构成一个正方形,任意排列都可能是原号码。

测试点性质

  • 测试点 2–3 中,每个号码长度不超过 88。
  • 测试点 4–5 中,号码只含 1、2、3。
  • 测试点 6–7 的号码不含 5。
  • 测试点 8–9 的号码只含 5、6、8、9。
  • 测试点 10–12、13–15、16–18 的字符串长度之和分别不超过 10210^2、10310^3、10410^4。
  • 测试点 19–21 无额外限制。