Description

Chiaki 对一个无限数列 $a_1,a_2,a_3,\dots$ 感兴趣，该数列定义如下：

$$a_n = \begin{cases} n & n \le 2 \\ 2 \cdot a_{n-1} & n \text{ 为奇数} \\ a_{n-1} + r_{n-1} & n \text{ 为偶数} \end{cases}$$

其中 $r_n$ 是满足 $S_n = \{a_j - a_i \mid 1 \le i < j \le n\}$ 的集合中没有出现的最小正整数。

Chiaki 想知道该数列的前 $n$ 项和，即 $\sum\limits_{i=1}^{n} a_i$。由于这个数可能非常大，Chiaki 只关心它对 $10^9+7$ 取模后的结果。

Input Format

有多组测试用例。输入的第一行包含一个整数 $T$（$1 \le T \le 1000$），表示测试用例的数量。对于每组测试用例：

第一行包含一个整数 $n$（$1 \le n < 10^{100}$），无前导零。

Output Format

对于每组测试用例，输出一个整数表示答案。

11
1
2
3
4
5
6
7
8
9
10
1000000000

1
3
7
15
31
52
94
145
247
359
834069170

Hint

由 ChatGPT 5 翻译