Magic Strings

Time limit4sMemory limit512 MB

Summary

Given n up to 10^18, count the distinct subsequences of the recursively doubled string F_n modulo 10^9+7 for up to 10 test cases.

Level: Hard9 of 10
Topics: Dynamic programming, Matrix, String, Combinatorics
Solved: No attempts yet

Problem

Consider the sequence of strings $F_1, F_2, \ldots$ defined as follows.

$F_1 =$ ab

$F_{k+1} = F_k F_k$ b

Calculate the number of distinct subsequences of the string $F_n$ modulo $10^9 + 7$ .

Input

The first line contains a single integer $t$ ( $1 \le t \le 10$ ), the number of test cases. The second line contains $t$ integers $n$ ( $1 \le n \le 10^{18}$ ), one for each test case.

Output

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

Hint

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

Examples1

Example 1
Input
```
3
1 2 3
```
Expected output
```
4 17 226
```