#P14111. [ZJCPC 2017] Chiaki Sequence
[ZJCPC 2017] Chiaki Sequence
题目描述
Chiaki is interested in an infinite sequence , 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 is the smallest positive integer not in the set .
Chiaki would like to know the sum of the first terms of the sequence, i.e. . As this number may be very large, Chiaki is only interested in its remainder modulo .
输入格式
There are multiple test cases. The first line of input contains an integer (), indicating the number of test cases. For each test case:
The first line contains an integer () 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