Watson gives a square of side length 1 to Sherlock. Now, after each second, each square of some arbitrary side $\boldsymbol{\mbox{I}}$ will break into four squares each of side [MATH1].

Now, Watson asks Sherlock: What will be the sum of length of solid lines after $N$ seconds?

As the number can be large print result mod $(10^9+7)$.

For example, after 0 seconds, the length is 4.

After 1 second, the length is 6.

Input Format

First line contains $\mathbf{T}$, the number of testcases. Each testcase contains $N$ in one line.

Output Format

For each testcase, print the required answer in a new line.

Constraints

$1\leq T\leq10^5$

$0\leq N\leq10^9$

Sample input

3
0
1
5

Sample output

4
6
66

见题面

见题面