This one is pretty simple! Given ‘n’, evaluate n^C(n).

    C(n) = (2n)! / (n! * n! * (n + 1))

Since the answer can be very large, output it modulo 10^9+7.

Input

First line contains T, the number of test cases.

Next T lines contain one integer per line, ‘n’.

Output

Output T lines, each for a single test case, containing the required output.

Constraints

0 < T <= 100

1 <= n <= 10^5

Example

Input:
2
2
4

Output:
4
268435456