Bob is playing with binary strings. He defines two strings $S$ and $T$ to be similar if at least one of the following conditions holds:

1. $S=T$
2. The lengths of both $S$ and $T$ must be divisible by $2$. Let $S_1$ denote the first half of $S$, and $S_2$ denote the second half. Similarly, define $T_1$ and $T_2$ as the first and second halves of $T$. Then $S$ and $T$ are similar if either:
   • $S_1$ is similar to $T_1$ and $S_2$ is similar to $T_2$ or
   • $S_1$ is similar to $T_2$ and $S_2$ is similar to $T_1$

If both conditions do not hold then $S$ and $T$ are not similar.

Bob begins to wonder about $N$ particular lengths of binary strings. These lengths are $a_1,a_2,\dots ,a_N$.

For each $a_i$, Bob generates all $2^{a_i}$ possible binary strings of length $a_i$. He wonders how many ordered pairs of binary strings from his set are similar. Since these numbers may be massive, print the answers modulo ${10}^9+7$.

Constraints

In all subtasks,
$1\le N\le 50$
$1\le a_i\le {10}^{18}$

Subtask 1 [5%]

$1\le a_i\le 5$

Subtask 2 [10%]

All the $a_i$ are odd integers.

Subtask 3 [15%]

$N=1$
$1\le a_i\le 26$

Subtask 4 [10%]

$N=1$
$1\le a_i\le 52$

Subtask 5 [30%]

$1\le a_i\le 1024$

Subtask 6 [30%]

$1\le a_i\le {10}^{18}$

Input Specification

The first line contains a single integer, $N$.
$N$ lines follow, the $i$-th of which containing a single integer, $a_i$.

Output Specification

Output $N$ lines, the $i$-th of which containing the answer modulo ${10}^9+7$ for binary strings of length $a_i$.

Sample Input 1

1
2

Sample Output 1

6

Sample Input 2

2
3
4

Sample Output 2

8
54

Explanation for Sample Output 2

There are a total of $8$ ordered pairs of similar strings for binary strings of length $3$, and there are a total of $54$ ordered pairs of similar strings for binary strings of length $4$.