Xiao Z 和 Xiao R 又开始玩数数游戏了。这一次，面对游戏缺乏新意以及 Xiao R 即将出国交换的困境，他们发现无法再面对面一起玩，只能在线上交流。

然而，线上游戏的想法激发了新的灵感。众所周知，数据是以二进制形式表示的。以前他们玩的是十进制游戏，但这次他们提议改玩二进制。

在传统的数数游戏中，玩家轮流数数，任何 7 的倍数或包含数字 7 的数都必须跳过。遗憾的是，他们很快意识到这个规则在二进制下并不有趣，因为二进制中不存在数字 7，且一个数是否为 7 的倍数与其在任何进制下的表示无关。

但如果换个角度看呢？同一个数字字符串在不同的进制下可以表示截然不同的数值。例如，字符串 “1010” 在二进制下表示 10 ($1010_2 = 0 \cdot 2^0 + 1 \cdot 2^1 + 0 \cdot 2^2 + 1 \cdot 2^3 = 10$)，但在三进制下表示 30 ($1010_3 = 0 \cdot 3^0 + 1 \cdot 3^1 + 0 \cdot 3^2 + 1 \cdot 3^3 = 30$)。遵循这个逻辑，有多少个数字字符串在任何进制下都不是 7 的倍数？他们决定制定一条规则，只数这样的数。

因此，他们定义了以下形式规则：

当且仅当字符串 $s$ 非空、仅由字符 '0' 和 '1' 组成且不以 '0' 开头时，称 $s$ 为一个合法的 01 字符串。

他们还定义了一个进制函数 $f(s, k)$，其中 $s$ 是一个合法的 01 字符串，$k$ 是不小于 2 的整数。如果 $s$ 的长度为 $n$，下标从 0 开始，则 $f(s, k) = \sum_{i=0}^{n-1} s_{n-i-1} \cdot k^i$，其中 $s_0$ 是高位，$s_{n-1}$ 是低位。

给定一个合法的 01 字符串 $s$ 作为计数的上限，他们想知道有多少个字符串（模 $10^9 + 7$）不超过 $s$，且在任何进制下都不是 7 的倍数？换句话说，有多少个合法的 01 字符串 $s'$ 满足：对于任何整数 $k \ge 2$，7 不能整除 $f(s', k)$，其中 “不超过 $s$” 指的是在二进制意义下，即 $f(s', 2) \le f(s, 2)$。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试数据的组数。对于每组测试数据：

第一行包含一个合法的 01 字符串 $s$ ($|s| \le 10^4$)，表示计数的上限。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示答案。由于答案可能很大，你需要将其对 $10^9 + 7$ 取模。

样例

输入 1

5
1
1010
110101
1000111000
101101001000

输出 1

1
2
15
114
514