A001856 - Chiaki Sequence
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$).
Input
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.
Output
For each test case, output an integer denoting the answer.
Example
Input
11 1 2 3 4 5 6 7 8 9 10 1000000000
Output
1 3 7 15 31 52 94 145 247 359 834069170
Information
There are $5$ input files and my unoptimized python3 code runs about 1.1 sec per file.
hide comments
[Rampage] Blue.Mary:
2018-05-10 05:49:26
I don't know what do you mean by unoptimized. In my opinion this needs heavy optimization. |
Added by: | zimpha |
Date: | 2018-01-14 |
Time limit: | 3s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |