Define the sequence of strings $F_1, F_2, \ldots$ as follows:

$$ F_1 = \text{dt}, \\ F_{k+1} = F_k F_k \text{t} $$

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

Input

The first line contains an integer $T$ ($1 \leq T \leq 10$), representing the number of test cases.

Each of the next $T$ lines contains a positive integer $n$ ($1 \leq n \leq 10^{18}$), representing a test case.

Output

Output $T$ integers, representing the answers.

Examples

Input 1

4
1 2 3 100000

Output 1

4 17 226 73460621

Note

$F_1 = \text{dt}, F_2 = \text{dtdtt}, F_3 = \text{dtdttdtdttt}$.

Constraints

It is guaranteed that $1 \leq T \leq 10$ and $1 \leq n \leq 10^{18}$.

Subtask 1 (24 pts): $n \leq 18$.

Subtask 2 (12 pts): $n \leq 2000$.

Subtask 3 (15 pts): $n \leq 10^6$.

Subtask 4 (11 pts): $n \leq 10^9$.

Subtask 5 (38 pts): No additional constraints.