33OJ
登录 注册

#P17806. [ICPC 2019 Nanchang R] And and Pair

[ICPC 2019 Nanchang R] And and Pair

Problem Description

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 \ \& \ n=i; and
  • i & j=0i \ \& \ j=0.

Here & 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 Format

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

Each of the following TT lines contains a string S (1≤∣S∣≤105)S~(1 \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 Format

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

2
111
1010
14
15