Twins X65570

HOLIDAYS ARE COMING!

Last day of the advanced algorithmic classes and two siblings are walking in a big corridor. But one of the twins asks his brother: “Do you know in how many ways we can walk through this corridor?”

The corridor is $L$ meters long and it is represented as a $2 \times L$ grid. Initially, twin $A$ is at $(1,1)$ and twin $B$ is at $(2,1)$, and they set the rules to move along the corridor:

• A twin can move to the left tile $(+1,0)$.

• A twin can advance to the tile in front $(0,+1)$.

• A twin can cross in a diagonal, e.g. $(+1,+1)$ or $(-1,+1)$.

• The destination tiles must exist.

• Both move at the same time.

• They always move while they are not in the last tiles $(1,L)$ or $(2,L)$.

• They finish when both are in any of the last tiles $(1,L)$ or $(2,L)$.

For a given $L > 1$, return the number of of ways in which the twins can walk through the corridor. Because this number could be very large, return the result modulo $10^9 + 7$.

Input

The input starts with the number of test cases $T \leq 1000$. For each test case, there is an integer $L \leq 10^6$ representing the length of the corridor.

Output

For each test case, output an integer on a single line representing the number of ways in which the twins can walk through the corridor, modulo $10^9 + 7$.

In the first example there are 8 combinations:

• $A = (1,2)$ and $B = (1,2)$

• $A = (1,2)$ and $B = (2,2)$

• $A = (2,2)$ and $B = (1,2)$

• $A = (2,2)$ and $B = (2,2)$

• $A = (2,1)$ and $B = (1,2) \rightarrow A = (2,2)$ and $B = (1,2)$

• $A = (2,1)$ and $B = (1,2) \rightarrow A = (1,2)$ and $B = (1,2)$

• $A = (2,1)$ and $B = (2,2) \rightarrow A = (2,2)$ and $B = (2,2)$

• $A = (2,1)$ and $B = (2,2) \rightarrow A = (1,2)$ and $B = (2,2)$