DCEPC805 - Catalan Powered

no tags 

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 no. 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



Added by:dce coders
Date:2012-08-19
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem