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\)