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