406313: GYM102354 D Magic Strings

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

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.

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

3
1 2 3

4 17 226 

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