You are playing a board game. The game consists of q cards. The ith card is a table with the following features:
In each move, you can move from a block with coordinates (x,y) to either of the following coordinates:
You want to know the number of ways you can move from the block (1,1) to block (ni,3).
Note: Print the answer modulo 109+7.
Input format
Output format
In q lines, print the answer that represents the number of ways you can move from the block (1,1) to block (ni,3).
Constraints
1≤q≤10001≤ni≤1018
There is only one way to go from (1,1) to (3,3) and that is [(1,1),(2,2),(3,3)].
There is no way to go from (1,1) to (2,3).
There are 2 ways to go from (1,1) to (5,3).