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