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: UNKNOWN_DIFFICULTY

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
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])


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])