贝西有一部带有九个按钮的新手机，布局如下： 123 456 789 贝西正试图匆忙输入给定的****，因此她决定 通过用一只 蹄子同时按下多个按钮来节省时间。具体来说，贝西的蹄子可能会按一个数字，共享一条边 的两个数字（总共十二个可能的对），或形成一个正方形的 四个数字（1245、2356、4578 或 5689）。 例如，如果 Bessie 尝试键入的****123659874，她 可能会尝试通过以下方式节省时间 同时按 1 和 2。 按 3。 同时按 6、5、9 和 8。 同时按 7 和 4。 不幸的是，贝茜大大高估了她执行这项 任务的技能——如果贝茜的蹄子同时按下多个按钮，那么所有 数字都将以任意顺序输入。因此，如果 Bessie 尝试 上述按压顺序，她最终可能会输入123596847或213659874 （或许多其他可能性之一）。 给定 Bessie 键入的一系列数字，计算她可能尝试键入模数的**** 数量 1 0 9 + 7 10 9 +7. 注意：此问题的时间限制为 4 秒，是默认值的两倍。 输入格式 第一行包含 � T ( 1 ≤ � ≤ 10 1≤T≤10），要解决的独立测试 用例的数量。 下一个 � T每行都包含一个由数字 1 到 9 组成的非空字符串。 保证这些字符串的总长度不超过 1 0 5 10 5 . 输出格式 对于每个测试用例，Bessie 可能尝试 键入模数的****数量 1 0 9 + 7 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 可能一直在 尝试键入输入序列的任何排列。

Bessie 有一部有九个按钮的新手机，布局如下： 123 456 789 Bessie 试图快速输入给定的****，因此她决定 用其中一个按钮同时按多个按钮来节省时间 马蹄。具体来说，Bessie 的蹄子可能会按下单个数字、 共用一条边的两个数字（总共 12 对可能的数字）或 形成正方形的四个数字（1245、2356、4578 或 5689）。 例如，如果 Bessie 尝试输入的****是 123659874，她 可能会尝试通过以下方式来节省时间： 同时按 1 和 2。 按 3。 同时按 6、5、9 和 8。 同时按 7 和 4。 不幸的是，贝西大大高估了她执行这项 任务的能力 - 如果贝西的蹄子同时按下多个按钮，那么所有 数字都将以任意顺序输入。因此，如果 Bessie 尝试按 上述顺序，她最终可能会输入 123596847 或 213659874 （或许多其他可能性之一）。 给定 Bessie 键入的数字序列，计算 她可能尝试键入的****的数量，并取模 1 0 9 + 7 10 9 +7。 注意：本题的时间限制为4s，是默认值的两倍。 输入格式 第一行包含 时间 时间 ( 1 ≤ 时间 ≤ 10 1≤时间≤10），要解决的独立测试用例的数量 。 下一个 时间 时间每行包含一个由数字 1 到 9 组成的非空字符串。 保证这些字符串的总长度不超过 1 0 5 10 5 . 输出格式 对于每个测试用例，Bessie 可能尝试输入的****数量取模 1 0 9 + 7 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 可能一直在尝试 键入输入序列的任何排列。