A001856 - Chiaki Sequence

数列 [A001856](https://oeis.org/A001856) 为一个无穷数列 $a_1,a_2,a_3,\dots$，满足： $$ a_n=\begin{cases}n&n\le2\\2\cdot a_{n-1}& 2\nmid n\\a_{n-1}+r_{n-1}&2\mid n\end{cases} $$ 其中 $r_n$ 为在 $S_n=\{a_j-a_i\mid 1\le i < j \le n\}$ 中未出现过的最小正整数。 给定 $n$（$1\le n\le 10^{100}$） ，求 $\left(\sum_{i=1}^na_i\right)\bmod (10^9+7)$。多测，$T\le 10^3$。 by @Sya_Resory

Chiaki is interested in an infinite sequence $ a_1, a_2, a_3, ... $ , which defined as follows: $$ a_n = \begin{cases} n, & n \le 2 \\ 2 \cdot a_{n-1}, & n \text{ is odd} \\ a_{n-1}+r_{n-1}, & n \text{ is even}\end{cases} $$ where $ r_n $ is the smallest positive integer not in the set $ S_n = \{a_j - a_i \mid 1 \le i < j \le n\} $ . Chiaki would like to know the sum of the first $ n $ terms of the sequence, i.e. $ \sum\limits_{i=1}^{n} a_n $ . As this number may be very large, Chiaki is only interested in its remainder modulo ( $ 10^9 + 7 $ ).

There are multiple test cases. The first line of input contains an integer $ T $ ( $ 1 \le T \le 1000 $ ), indicating the number of test cases. For each test case: The first line contains an integer $ n $ ( $ 1 \le n < 10^{100} $ ) without leading zeros.

For each test case, output an integer denoting the answer.

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

1
3
7
15
31
52
94
145
247
359
834069170