#P14111. [ZJCPC 2017] Chiaki Sequence

[ZJCPC 2017] Chiaki Sequence

题目描述

Chiaki is interested in an infinite sequence a1,a2,a3,a_1,a_2,a_3,\dots, 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 rnr_n is the smallest positive integer not in the set Sn={ajai1i<jn}S_n = \{a_j-a_i | 1 \le i < j \le n\}.

Chiaki would like to know the sum of the first nn terms of the sequence, i.e. i=1nai\sum\limits_{i=1}^{n}a_i. As this number may be very large, Chiaki is only interested in its remainder modulo (109+7)(10^9+7).

输入格式

There are multiple test cases. The first line of input contains an integer TT (1T10001 \le T \le 1000), indicating the number of test cases. For each test case:

The first line contains an integer nn (1n<101001 \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