406313: GYM102354 D Magic Strings

Memory Limit:0 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Magic Stringstime limit per test4 secondsmemory limit per test256 mebibytesinputstandard inputoutputstandard 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.

ExampleInput
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}$$$.

加入题单

上一题 下一题 算法标签: