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

Author
  • himuhasib's Avatar

    himuhasib

    Hasib is passionate about sport programming and artificial intelligence. He was an IOI participant through years 2013-2015. He qualified to ACM-ICPC World Finals 2016. He studies at North South University.
Discussion
Submit

Login to submit