Omegle is taking over its user's mind and trapping them inside a maze . The maze is a grid consisting of NXN empty boxes. The user is initially standing at (1,1) . The target of the user is to move out of the box and end up at position (N,N). The thing is that the person can only move in a rightwards or upwards direction.
*check the note for references. also the figure for reference.
Note: Left Botton corner is marked as 1,1 and top right corner is marked as N,N.
Basically the user needs instructions R and U . R - Right and U - Upwards.
You need to answer that a for a given possible N*N Matrix how many different possible ways are there to reach the destination . Since the number of ways may be large so print the output modulo
1000000007. i.e. (1e9+7)
INPUT:
T number of test cases .
N the dimension of the matrix .
OUTPUT:
Print each answer in a newline .
CONSTRAINTS:
1<=T<=105.
2<=N<=105.
For 2x2 matrix the possible ways are 2 : RU , UR.
For 3X3 matrix the possible ways are 6:
RRUU
UURR
URRU
RUUR
RURU
URUR