P17806 [ICPC 2019 Nanchang R] And and Pair

Given an extremely large non-negative integer $n$, you are asked to count the number of pairs $(i,j)$ of integers satisfying the following conditions: - $0\leq j\leq i\leq n$; - $i \ \& \ n=i$; and - $i \ \& \ j=0$. Here `&` represents the bitwise AND operator. For simplicity, the binary representation of $n$ will be given. Meanwhile, you only need to output the answer modulo $(10^9+7)$.

The first line contains an integer $T~(1\le T\le 20)$ indicating the number of test cases. Each of the following $T$ lines contains a string $S~(1 \le |S| \le 10^5)$ which is the binary representation of the non-negative integer $n$. Note that leading zeros of $S$ could appear in the input.

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