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 × 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⁹ + 7.

Input

The input starts with the number of test cases T ≤ 1000. For each test case, there is an integer L ≤ 10⁶ 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⁹ + 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) → A = (2,2) and B = (1,2)
• A = (2,1) and B = (1,2) → A = (1,2) and B = (1,2)
• A = (2,1) and B = (2,2) → A = (2,2) and B = (2,2)
• A = (2,1) and B = (2,2) → A = (1,2) and B = (2,2)