Chiaki Sequence Revisited

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

Chiaki is interested in an infinite sequence $a_1, a_2, a_3, ...$, which is defined as follows:
$$a_n=\begin{cases}1 & n = 1,2 \\ a_{n - a_{n-1}} + a_{n-1 - a_{n-2}} & n \ge 3\end{cases}$$
Chiaki would like to know the sum of the first $n$ terms of the sequence, i.e. $\sum\limits_{i=1}^{n}a_i$. 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 10^5$), indicating the number of test cases. For each test case:
The first line contains an integer $n$ ($1 \le n \le 10^{18}$).

Output

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

Sample Input

10 1 2 3 4 5 6 7 8 9 10

Sample Output

1 2 4 6 9 13 17 21 26 32

Hint

liuyiding

Source

2018 Multi-University Training Contest 1

提交代码