Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
148 - The 14th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple - L
Chiaki Sequence

Time Limit: 3 Seconds      Memory Limit: 131072 KB

Chiaki is interested in an infinite sequence a1, a2, a3, ..., which defined as follows:

where rn is the smallest positive integer not in the set Sn = {aj - ai | 1 ≤ i < jn}.

Chiaki would like to know the sum of the first n terms of the sequence, i.e. . As this number may be very large, Chiaki is only interested in its remainder modulo (109 + 7).

Input

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

The first line contains an integer n (1 ≤ n < 10100) without leading zeros.

Output

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

Sample Input

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

Sample Output

1
3
7
15
31
52
94
145
247
359
834069170

Submit    Status