DCEPC805 - Catalan Powered

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

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 NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.