D. Magic Strings
time limit per test
4 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

Consider the sequence of strings $$$F_1, F_2, \dots$$$, defined as:

$$$$$$ F_1 = ab\text{,} $$$$$$ $$$$$$ F_{k+1} = F_kF_kb\text{.} $$$$$$

Calculate the number of distinct subsequences of the string $$$F_{n}$$$ modulo $$$10^9+7$$$.

Input

The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 10$$$), which is the number of test cases.

The second line of input contains $$$t$$$ integers $$$n$$$ ($$$1 \leq n \leq 10^{18}$$$), one for each test case.

Output

For each test case, output the single integer which is the answer to the problem. Separate consecutive answers by single spaces.

Example
Input
3
1 2 3
Output
4 17 226
Note

The first three strings are: $$$F_1 = \texttt{ab}$$$, $$$F_2 = \texttt{ababb}$$$, and $$$F_3 = \texttt{ababbababbb}$$$.