【题目描述】

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