Alex And One More Equation

easy

Alex is a DSA entusiast guy who creates problem and solve them.

Recently he has got 2 equations
a=b+c
and
p=q+r
where,  r=q+1=c+2=b+3.

Now alex randomly chooses an integer 'n' is curious to know for how many b in the range from (0,2^n) given equation satisfies i.e. a==p.

Alex need your help to solve this problem.

Input Format

The first line contains an integer T, the number of test cases. Then the test cases follow. The only line of each test case contains a single integer N.

Output Format

For each test case, output in a single line the answer to the problem modulo 10^9+7.

Constraints

1&lt;=T&lt;=10^5 
1&lt;=N&lt;=10^5

Notice

Example

Input

2
1
2

Output

1
2

First Non Repeating Character In Stream

Making The Test Difficult