There is a TV remote that contains three buttons:

1. Next channel
2. Previous channel
3. Volume change

Find the number of ways such that after $N$ clicks on the remote you remain on the same channel.

You can assume there are infinite channels.

Since the answer can be too large, print answer modulo $1000000007$.

Input format

• The first line contains $T$ denoting the number of test cases.
• The first line of each test case contains a single integer $N$.

Output format

For each test case, print the number of ways modulo $1000000007$ in a single line.

Constraints

$1\leq T \leq 100$

$1 \leq N \leq 100000$

Sum of $N$ over all test cases does not exceed $1e5$