Shaun was given $N$ pairs of parenthesis ( )  by his teacher who gave him a difficult task.The task consists of two steps. First,Shaun should colour all $N$ pairs of parenthesis each with different color but opening and closing bracket of a particular pair should be of same colour. Then,Shaun should report to his teacher the number of ways he can arrange all $2*N$ brackets such that sequence form is valid. Teacher defined valid sequence by these rules:
- Any left parenthesis '(' must have a corresponding right parenthesis ')'.
- Any right parenthesis ')' must have a corresponding left parenthesis '('.
- Left parenthesis '(' must go before the corresponding right parenthesis ')'. 
Note: Shaun could match opening and closing brackets of different colours. 
Since number of ways can be large, Shaun would report the answer as modulo 1000000007 ($10^9 + 7$).

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, one integer $N$. 

-----Output:-----
For each testcase, output in a single line answer given by Shaun to his teacher modulo 1000000007.

-----Constraints-----
- $1 \leq T \leq 100000$
- $1 \leq N \leq 100000$

-----Sample Input:-----
3
1
2
3

-----Sample Output:-----
1
6
90

-----EXPLANATION:-----
Here numbers from $1$ to $N$ have been used to denote parenthesis.A unique number corresponds to a unique pair of parenthesis.
-In the first test case , you can use only one color to color the parenthesis  you could arrange it only in one way i.e, 1 1
-In the second test case  you can use two colors and the possible ways of arranging it are
1 1 2 2
1 2 2 1
1 2 1 2
2 2 1 1
2 1 1 2
2 1 2 1

Difficulty: interview

Starter code:

Solutions:
mod = 1000000007
fac = [1,1]
maxn = (10**5)+5
for i in range(2,maxn):
    x = (fac[-1]*i)%mod
    fac.append(x)

pre = [1]
for i in range(2,maxn):
    x = 2*i-1
    x = (pre[-1]*x)%mod
    pre.append(x)

for _ in range(int(input())):
    n = int(input())
    x = fac[n]
    y = pre[n-1]
    print((x*y)%mod)

def getdp():
    nonlocal mod,maxx
    for i in range(2,maxx):
        n = 2*(i-1) + 1 
        n = (n * (n+1))//2 
        dp[i] = (dp[i-1]*n)%mod 

mod = 1000000007
maxx = 100001
dp=[1]*maxx
getdp()
t=int(input())
while t>0 :
    n=int(input())
    print(dp[n])
    t-=1

import atexit
import io
import sys
import math
from collections import defaultdict,Counter

# _INPUT_LINES = sys.stdin.read().splitlines()
# input = iter(_INPUT_LINES).__next__
# _OUTPUT_BUFFER = io.StringIO()
# sys.stdout = _OUTPUT_BUFFER

# @atexit.register
# def write():
#     sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())

# sys.stdout=open("CP2/output.txt",'w')
# sys.stdin=open("CP2/input.txt",'r')

m=pow(10,9)+7
t=int(input())
l=[0]*100001
l[1]=1
for i in range(2,100001):
    l[i]=(((i*l[i-1])%m)*(2*i-1))%m
for i in range(t):
    n=int(input())
    print(l[n])


m = 10**9+7;a = [0]*(10**5+10);a[0] = 1
for i in range(1,10**5+5):a[i] = (a[i-1]*(i*(2*i-1)%m)%m)
for _ in range(int(input())):print(a[int(input())])

a = list(map(int, open(0)))[1:]
N = max(a) + 1
b = [1] * N
for i in range(1, N):
 j = 2 * i
 b[i] = b[i - 1] * j * (j - 1) // 2 % (10**9 + 7)

for n in a:
 print(b[n])


# generate the array
m = 10**9+7
a = [0]*(10**5+10)
a[0] = 1
for i in range(1,10**5+5):
	a[i] = (a[i-1]*(i*(2*i-1)%m)%m)

for _ in range(int(input())):
	n = int(input())
	print(a[n])

N = 100001
a = [1] * N
for i in range(1, N):
 j = 2 * i
 a[i] = a[i - 1] * j * (j - 1) // 2 % (10**9 + 7)

for s in[*open(0)][1:]:
 print(a[int(s)])


fac = 1
facts = [1]
for i in range(1,100000):
    fac = (fac*(2*i+1)*(i+1))%1000000007
    facts.append(fac)

T = int(input())

for _ in range(T):
    N = int(input())
    print(facts[N-1])

e=10**9+7
n=100000
l=[1]
for i in range(1,n+1):
    x=(i*(2*i-1))%e
    l.append((x*l[-1])%e)
t=int(input())
for _ in range(t):
    n=int(input())
    print(l[n])