Given an extremely large non-negative integer nn, you are asked to count the number of pairs (i,j)(i,j) of integers satisfying the following conditions:

  • 0≤j≤i≤n0\leq j\leq i\leq n;
  • i ∧ n=ii\ \wedge\ n=i;
  • i ∧ j=0i\ \wedge\ j=0.

Here $\wedge $ represents the bitwise AND operator.

For simplicity, the binary representation of nn will be given. Meanwhile, you only need to output the answer modulo (109+7)(10^9+7).

Input

The first line contains an integer TT (1≤T≤201\le T\le 20) indicating the number of test cases.

Each of the following TT lines contains a string SS (1≤∣S∣≤1051 \le |S| \le 10^5) which is the binary representation of the non-negative integer nn. Note that leading zeros of SS could appear in the input.

Output

For each test case, output a line containing the answer described above modulo (109+7)(10^9+7).

样例输入复制

1
2
3
2
111
1010

样例输出复制

1
2
14
15

题解

对于确定的 nn，若其中某一位为 11，则 ii 该位可为 00 或 11；若其中某一位为 00，则 ii 该位只能是 00。对于确定的 ii，若其中某一位为 11，则 jj 该位只能是 00；若其中某一位是 00，则 jj 该位可为 00 或 11。

为满足 0≤j≤i≤n0\le j\le i\le n 的性质，不妨枚举 ii 最高位 11 的位置，即 ii 的二进制表示形如 ⋯000001⋯\cdots 000001\cdots。在 ii 最高位 11 的位置和最高位的左侧，jj 只能填 00，否则不满足 j≤ij\le i 和 i∧j=0i \wedge j=0。假设在最高位 11 右侧，nn 中有 num0num_0 个 00，num1num_1 个 11。对于 00 的位置，ii 在该位置填 00，jj 产生两种方案；对于 11 的位置，枚举 ii 在该位置填 kk 个 00，jj 在 kk 个位置有两种方案，在 num1−knum_1-k 个位置只有一个方案。根据乘法原理，在 ii 最高位 11 的右侧，有 2num0∑k=0num1Cnum1k2k2^{num_0}\sum\limits_{k=0}^{num_1}C_{num_1}^k2^k 个方案。

根据二项式定理，有 (x+1)n=∑i=0nCnixi(x+1)^n=\sum\limits_{i=0}^nC_n^ix^i，将 x=2x=2 代入，得到 3n=∑i=0nCni2i3^n=\sum\limits_{i=0}^nC_n^i2^i。

最终得到，在 ii 最高位 11 的右侧，有 2num0×3num12^{num_0}\times3^{num_1} 种方案。从低位到高位枚举各个可放置 11 的位置作为 ii 的最高位，累加答案即可。最后还需要累加上 i=j=0i=j=0 的特例。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 计蒜客 T42578
Date: 2021 July 15th
Description: Count
*******************************************************************/
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAX_LEN = 100004;
const int MOD = 1e9 + 7;
int _, n;
char s[MAX_LEN];
int power2[MAX_LEN], power3[MAX_LEN];
inline void init()
{
	power2[0] = power3[0] = 1;
	for (int i = 1; i < MAX_LEN;i++)
	{
		power2[i] = 1ll * power2[i - 1] * 2 % MOD;
		power3[i] = 1ll * power3[i - 1] * 3 % MOD;
	}
}
int main()
{

	init();
	for (cin >> _; _; _--)
	{
		scanf("%s", s + 1);
		n = strlen(s + 1);
		int num[2] = {0};
		ll ans = 0;
		for (int i = n; i >= 1; i--)
		{
			switch (s[i])
			{
			case '1':
				ans = (ans + 1ll * power2[num[0]] * power3[num[1]] % MOD) % MOD;
				++num[1];
				break;
			case '0':
				++num[0];
				break;
			default:
				break;
			}
		}
		ans = (ans + 1) % MOD;
		cout << ans << endl;
	}
	return 0;
}