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
Explanation Possible paths are: Up => Right => Right Right => Up => Right Right => Right => Up Up => Right => Down => Right => Up