
ZOJ Problem Set  4074
Given an nonnegative integer $x$, Chiaki can perform the following two operations:
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. InputThere 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$. OutputFor each test case, output the answer modulo ($10^9+7$). Sample Input10 0 1 10 11 100 101 110 111 1000 1001 Sample Output0 1 3 7 13 22 31 43 60 83 Author: LIN, Xi Source: Yet Another Xi Lin Contest 