시간 제한메모리 제한제출정답맞힌 사람정답 비율
15 초 (추가 시간 없음) 256 MB111100.000%

문제

Call a multiset of positive integers $A = \{a_1, a_2, \ldots, a_k\}$ $n$-handsome if the sum of its elements is equal to $n$, and each integer from $1$ to $n$ can be uniquely represented as a sum of its elements up to their order. For example, $\{1, 2, 4\}$ is $7$-beautiful, $\{1, 1, 3\}$ is $5$-beautiful. Given an integer $n$, find the following sum: \[\left(\sum\limits_{A\text{ is }n\text{-beautiful}}|A| \right) \bmod p.\]

You can choose $p = 10^9 + 7$ or $p = 10^9 + 9$ by yourself for each $n$ you are computing the answer.

입력

The first line contains an integer $t$ ($1 \le t \le 5$) -- the number of test cases in the input file.

Each of the next $t$ lines contain one integer $n_i$ ($1 \le n_i \le 10^{16}$), for which you need to output the answer. It is guaranteed that all $n_i$ in one file are different.

출력

Output $t$ lines. The $i$-th of them should contain the answer for the number $n_i$. Each answer has to be correct either with $p = 10^9 + 7$ or $p = 10^9 + 9$, and $p$ can be chosen independently for each test case. Note that you should not output the chosen $p$, only the remainder of the answer.

예제 입력 1

5
1
2
3
4
5

예제 출력 1

1
2
5
4
11

예제 입력 2

5
6
7
8
9
10

예제 출력 2

6
18
12
19
10

예제 입력 3

5
99
17
14
24
38

예제 출력 3

572
64
26
32
66