Problem Description

A string whose each character is either `C` or `P` is called a *CP-String*, so there are $2^N$ different *CP-Strings* of length $N$. We define the *CCPCness* of a *CP-String* as the number of the most non-overlapping `CCPC` as its substrings.

For example, the *CCPCness* of `CCPCCCPC` is $2$, but the *CCPCness* of `CCPCCPC` is $1$ because the chosen `CCPC` substrings can not overlaps.

You are given an integer $N$, and you need to calculate the sum of *CCPCness* of all the $2^N$ different *CP-Strings* of length $N$. The answer may be too large, so you just need to output it modulo $(10^9+7)$.

Input

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

For each test case, there is one line with one integer $N$ ($1\leq N\leq 10^9$).

Output

For each test case, print one integer in one line, denoting your answer modulo $(10^9+7)$.

7
3
4
5
6
7
10
123456789

0
1
4
12
31
417
11557040