Problem 3. Phone Numbers

USACO 2022 February Contest, Platinum

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\le T\le 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 中，没有额外限制。

供题：Nick Wu