XOR on Pascal

Let's define $F(N)$ as following:

$F(N) = \binom{N}{0} \oplus \binom{N}{1} \oplus \binom{N}{2} \oplus \cdots \oplus \binom{N}{N}$

You are given an integer $N (0 \leq N \leq 10^5)$, you have to find the remainder when $F(N)$ is divided by $10^9 + 7$. More formally, you have to find the value of $F(N) \mod{(10^9 + 7)}$

Definitions:

$\binom{N}{k}$ means how many ways can you choose $k$ elements from $N$ different elements when order doesn't matter.

Examples:

$\binom{0}{0} = 1$

$\binom{5}{2} = 10$

$\binom{4}{3} = 4$

$\binom{5}{4} = 5$

$\binom{5}{5} = 1$

$\oplus$ is the XOR (Exclusive-OR) operator. XOR outputs 1 when the two input bits are different. The truth table for XOR:

Example:

$4 \oplus 3 = 7$

$3 \oplus 2 = 1$

$3 \oplus 3 = 0$

Input

The first line of the input will contain a single integer $T$ ($1 \leq T \leq 10^4$) denoting the number of test cases. On the next $T$ lines, there will be a single integer $N$ ($0 \leq N \leq 10^5$).

Output

For each test case, print the answer in a single line.

Sample

Input	Output
2 2 4	2 6