Phone Numbers

题目描述

Bessie 有一部新手机，带有九个按键，布局如下： 123 456 789 Bessie 正赶着输入一个给定的电话号码，因此她决定用一只蹄子同时按下多个按键来节省时间。 具体来说，Bessie 的蹄子可能会按下：一个数字；两个共享一条边的数字（总共有十二种可能的配对）；或四个组成一个 $2\times2$ 正方形的数字（1245、2356、4578 或 5689）。 例如，如果 Bessie 想输入的电话号码是 123659874，她可能会尝试通过以下方式节省时间： 同时按下 1 和 2。 按下 3。 同时按下 6、5、9 和 8。 同时按下 7 和 4。 不幸的是，Bessie 严重高估了自己完成这项任务的能力——如果 Bessie 的蹄子同时按下多个按键，那么所有数字会以任意顺序被输入。因此，如果 Bessie 尝试上述按键序列，她最终可能会输入 123596847 或 213659874（或者许多其他可能结果之一）。 给定 Bessie 实际输入的一串数字，计算她原本可能想输入的电话号码数量，并对 $10^9+7$ 取模。 注意：本题的时间限制为 4s，是默认值的两倍。

输入格式

第一行包含 $T$（$1\le T\le 10$），表示需要解决的独立测试用例数量。 接下来的 $T$ 行每行包含一个非空字符串，由数字 1 到 9 组成。 保证这些字符串的总长度不超过 $10^5$。

输出格式

对于每个测试用例，输出 Bessie 可能想输入的电话号码数量，并对 $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 可能想输入的是输入序列的任意一个排列。 SCORING: 在输入 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

标签: USACO|2022|Platinum

来源

USACO|2022|Platinum