# 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

Limits: 1s, 1.0 GB

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

InputOutput
2
2
4

2
6


Discussion
Submit