OMEGLE IS ADDICTIVE

0

0 votes
Problem

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.

 

 

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For 2x2 matrix the possible ways are 2 : RU , UR.

For 3X3 matrix the possible ways are  6:

RRUU

UURR

URRU

RUUR

RURU

URUR

Editor Image

?