Adam is standing at the end (lower left corner) of a Nx1 grid; an example is shown below. Since childhood, it was his dream to reach the far end of this grid; marked with an X in the diagram below. You see he is a freak when it comes to creative stuff, and the spot X marks nothing less than DreamWorks Animation Studios.

IMGUR link of the image He can walk on the grid lines. So we ask you this: how many ways are there for Adam to reach the X marked spot; given that he wonâ€™t ever walk twice on the same path. Letâ€™s call this Y. Then you have to find Y mod 10^9+7.

Input: The first line contains the number of testcases T. T lines follow, each of which contains an integer N, representing the size of the grid for that test case i.e. Nx1

Limits: 1 <= T <= 100000 1 <= N <= 1000000

Example Input 1 2

Output 4

Explanation Possible paths are: Up => Right => Right Right => Up => Right Right => Right => Up Up => Right => Down => Right => Up