给定一个非负整数 $x$，Chiaki 可以执行以下两种操作：

1. 将 $x$ 变为 $x - 1$。
2. 如果 $x \text{ AND } 2^i \neq 0$，则将 $x$ 变为 $x - 2^i$。

其中，$a \text{ AND } b$ 表示 $a$ 和 $b$ 的按位与运算。这些操作可以以任意顺序执行任意次数。 令 $f(x, y)$ 为将 $x$ 变为 $y$ 所需的最少操作次数。对于给定的数 $n$，Chiaki 想知道以下式子的值：

$$\sum_{0 \le y \le x \le n} f(x, y)$$

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。 对于每组测试数据： 第一行包含一个以二进制表示的整数 $n$ ($0 \le n < 2^{500}$)，且不含前导零。 保证所有测试数据中 $n$ 的二进制表示长度之和不超过 $500$。

输出格式

对于每组测试数据，输出答案对 $10^9 + 7$ 取模的结果。

样例

输入 1

10
0
1
10
11
100
101
110
111
1000
1001

输出 1

0
1
3
7
13
22
31
43
60
83