#P18527. Count off 3

Count off 3

Count off 3

小 Z 和小 R 又开始玩报数游戏。这次,由于小 R 出国交流,他们只能在线交流。计算机用二进制表示数据,这让他们想到把原来十进制的游戏改到二进制。

传统的报数游戏要跳过 7 的倍数或者包含数字 7 的数;但二进制没有数字 7,而是否为 7 的倍数与表示进制无关,因此这种改法并不有趣。不过,同一串数字在不同进制下会表示不同的值,例如 1010 在二进制下是 10,在三进制下是 30。他们于是提出:只允许报出在任何进制下都不是 7 的倍数的数字串。

正式定义如下:非空字符串 ss 若只含字符 0、1 且首字符不是 0,称为一个合法 01 串。

对合法 01 串 ss 和整数 k≥2k\ge2,定义将 ss 视为 kk 进制时的值为 f(s,k)f(s,k)。若串长为 nn,下标从 0 开始,则

f(s,k)=∑i=0n−1sn−i−1ki,f(s,k)=\sum_{i=0}^{n-1}s_{n-i-1}k^i,

其中字符 sjs_j 按对应数值 0 或 1 计算,s0s_0 是最高位,sn−1s_{n-1} 是最低位。

给你一个合法 01 串 ss 作为报数上界。求满足以下条件的合法 01 串 s′s' 的数量:

  • f(s′,2)≤f(s,2)f(s',2)\le f(s,2),即不超过上界的含义按二进制数值判断。
  • 对每一个整数 k≥2k\ge2,7 都不整除 f(s′,k)f(s',k)。

答案对 109+710^9+7 取模。

输入格式

第一行包含整数 TT(1≤T≤101\le T\le10),表示测试用例数。

每个测试用例占一行,包含一个合法 01 串 ss(1≤∣s∣≤1041\le |s|\le10^4),表示上界。每个串分别满足该长度限制,原题没有额外的所有串长度之和限制。

输出格式

每个测试用例输出一行一个整数,表示所求数量对 109+710^9+7 取模的结果。

完整原样例

5
1
1010
110101
1000111000
101101001000
1
2
15
114
514