Welcome to ZOJ Problem Sets Information Select Problem Runs Ranklist ZOJ Problem Set - 4074
The Easiest One

Time Limit: 1 Second      Memory Limit: 131072 KB

Given an nonnegative integer $x$, Chiaki can perform the following two operations:

• obtain $x-1$ from $x$.
• obtain $x-2^i$ from $x$, if $x \text{ AND } 2^i$ is not $0$.

Let $f(x, y)$ be the minimum operations needed to change $x$ to $y$ using the above operations, Chiaki would like to know the value of $$\sum\limits_{0 \le y \le x \le n} f(x, y)$$ where $n$ is a given number.

Input

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains an integer $n$ in binary representation ($0 \le n < 2^{500}$) without leading zeros.

It's guaranteed that the sum of lengths of $n$ over all test cases will not exceed $500$.

Output

For each test case, output the answer modulo ($10^9+7$).

Sample Input

10
0
1
10
11
100
101
110
111
1000
1001


Sample Output

0
1
3
7
13
22
31
43
60
83


Author: LIN, Xi
Source: Yet Another Xi Lin Contest
Submit    Status