1239 : 报数III

Description

【题目背景】

小 Z 和小 R 又开始玩报数游戏了。相较于先前十进制下的报数游戏，这次他们打算尝试一下其他进制——比如，计算机中数据是以二进制形式表示的，那么二进制下的报数游戏是什么样的呢？

传统的报数游戏中，所有人轮流报数，遇到 \(7\) 的倍数或本身含有数字 \(7\) 的数必须跳过。但两人立刻看出这个规则在二进制下没什么意思——二进制下根本没有数字 \(7\)，而一个数是不是 \(7\) 的倍数跟它被表示成几进制又没有关系。

但反过来呢？同样的一个数字串，将其看成不同进制下的数，其表示的数天差地别。比如数字串 \(1010\)，将其看成二进制的话表示 \((1010)_2=0\cdot 2^0+1\cdot 2^1+0\cdot 2^2+1\cdot 2^3=10\)，但其看成三进制的话就表示 \((1010)_3=0\cdot 3^0+1\cdot 3^1+0\cdot 3^2+1\cdot 3^3=30\)，以此类推。既然如此，有多少个数字串在任意进制下都不是 \(7\) 的倍数？他们希望制定一个规则，只有这样的数才能被报出。

于是他们定义了如下的形式化规则：

【题目描述】

称字符串 \(s\) 是合法 01 串，当且仅当 \(s\) 非空，仅由字符 0 和 1 组成，且不以 0 开头。

定义 \(|s|\) 为字符串 \(s\) 的长度。

对于合法 01 串 \(s = s_0s_1\cdots s_{|s|-1}\) 和不小于 \(2\) 的整数 \(k\)，定义进制函数 \[f(s,k)=\sum_{i=0}^{|s|-1} s_{|s|-i-1}\times k^i.\]注意 \(s_0\) 是高位，\(s_{|s|-1}\) 是低位。

给定一个合法 01 字符串 \(s\)，求同时满足以下两个条件的合法 01 串 \(s'\) 的数量，对 \((10^9+7)\) 取模：

• \(f(s', 2) \le f(s, 2)\)；
• \(\forall k \ge 2, 7 \nmid f(s', k)\)。

注意，\(s\) 与 \(s'\) 的长度不一定要相等。

Input

本题有多组测试数据。第一行一个正整数 \(T\)（\(1\leq T\leq 10\)），表示询问组数。

接下来 \(T\) 行，每行一个字符串 \(s\)，保证 \(|s| \le 10^4\)，且 \(s\) 是合法 01 串。

Output

共 \(T\) 行，每行一个整数，表示这组询问的答案，对 \((10^9+7)\) 取模。

Sample

5
1
1010
110101
1000111000
101101001000

1
2
15
114
514

Hint

Source

Author

THU