题目描述

题目译自 USACO 2022 February Contest, Platinum Problem 3. Phone Numbers

Bessie 获得了一个九键的新手机，键位如下所示：

123
456
789

Bessie 正在匆忙中尝试打出一个给定的电话号码，所以她决定通过用她的其中一个蹄子一次按下多个按钮的方式来节省时间。具体来说，Bessie 的蹄子可能按下一个键，两个共用一条边的键（总共有 $12$ 种可能），或者形成一个正方形的四个键（$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$ 取模后的值。

输入格式

第一行一个整数 $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

数据范围与提示

对于第 $2\sim 3$ 组数据，所有电话号码的长度最多为 $8$。

对于第 $4\sim 5$ 组数据，电话号码只包含 $1,2$ 和 $3$。

对于第 $6\sim 7$ 组数据，电话号码不包含 $5$。

对于第 $8\sim 9$ 组数据，电话号码只包含 $5,6,8,9$。

对于第 $10\sim 12$ 组数据，电话号码总长度不超过 $10^2$。

对于第 $13\sim 15$ 组数据，电话号码总长度不超过 $10^3$。

对于第 $16\sim 18$ 组数据，电话号码总长度不超过 $10^4$。

对于第 $19\sim 21$ 组数据，无附加限制。