# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

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

#### Samples

Input | Output |
---|---|

2 2 4 | 2 6 |