Bessie 有一部新手机，上面有九个按键，布局如下：
123 456 789
Bessie 正急着输入一个给定的电话号码，因此她决定通过用蹄子同时按下多个按键来节省时间。具体来说，Bessie 的蹄子可以按下单个数字、两个相邻的数字（共有 12 种可能的组合），或者四个构成正方形的数字（1245、2356、4578 或 5689）。
例如，如果 Bessie 想要输入的电话号码是 123659874，她可能会尝试通过以下方式节省时间：
- 同时按下 1 和 2。
- 按下 3。
- 同时按下 6、5、9 和 8。
- 同时按下 7 和 4。
不幸的是，Bessie 严重高估了自己完成这项任务的技巧——如果 Bessie 的蹄子同时按下了多个按钮，那么这些数字将以任意顺序输入。因此，如果 Bessie 尝试上述按键序列，她最终可能会输入 123596847 或 213659874（或者其他多种可能性）。
给定 Bessie 输入的一串数字，计算她原本可能想要输入的电话号码的数量，结果对 $10^9+7$ 取模。
注意：本题的时间限制为 4 秒，是默认限制的两倍。
输入格式
第一行包含 $T$ ($1\le T\le 10$)，表示需要解决的独立测试用例的数量。
接下来的 $T$ 行，每行包含一个由 1 到 9 组成的非空字符串。保证这些字符串的总长度不超过 $10^5$。
输出格式
对于每个测试用例，输出 Bessie 可能想要输入的电话号码数量，结果对 $10^9+7$ 取模。
样例
输入格式 1
5 1478 4455 5968 31313211 123659874
输出格式 1
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：无额外限制。