You are playing a board game. The game consists of $q$ cards. The $i^{th}$ card is a table with the following features:

• $3$ rows numbered from $1$ to $3$, considering the bottom to top approach
• $N$ columns numbered from $1$ to $n$, considering the left to right approach 

In each move, you can move from a block with coordinates $(x,y)$ to either of the following coordinates:

• $(x+1, y+1)$
• $(x+1, y-1)$

You want to know the number of ways you can move from the block $(1,1)$ to block $(n_i,3)$. 

Note: Print the answer $modulo\ 10^9+7$.

Input format

• First line: Integer $q$ denoting the number of cards
• Next $q$ lines: $i^{th}$ card containing one integer $n_i$denoting the size of the $i^{th}$ card

Output format

In $q$ lines, print the answer that represents the number of ways you can move from the block $(1,1)$ to block $(n_i,3)$.

Constraints

$1 \leq q \leq 1000\\ 1 \leq n_i \leq 10^{18}$