Chef is solving mathematics problems. He is preparing for Engineering Entrance exam. He's stuck in a problem.
$f(n)=1^n*2^{n-1}*3^{n-2} * \ldots * n^{1} $ 
Help Chef to find the value of $f(n)$.Since this number could be very large, compute it modulo $1000000007$.

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

-----Output:-----
For each testcase, output in a single line the value of $f(n)$ mod $1000000007$.

-----Constraints-----
- $1 \leq T \leq 10^6$
- $1 \leq N \leq 10^6$

-----Subtasks-----
Subtask 1(24 points) : 
- $1 \leq T \leq 5000$
- $1 \leq N \leq 5000$
Subtask 2(51 points) : original constraints

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

-----Sample Output:-----
12

Difficulty: interview

Starter code:

Solutions:
T=int(input())
t=[]
for _ in range(T):
 N=int(input())
 t.append(N)
N=max(t)+1
l=[0 for i in range(N)]
p=1
a=1
for i in range(1,N):
 a=(a*i)%1000000007
 p=p*a%1000000007
 l[i]=p
for i in t:
 print(l[i])


import sys;
input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

M = 10**9+7
f = [1]*(1000001)
for i in range(2,1000001):
 f[i] = (i*f[i-1])%M
for i in range(2,1000001):
 f[i] = (f[i]*f[i-1])%M

for _ in range(inp()):
 n = inp()
 print(f[n])

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

M = 10**9+7
f = [1]*(1000001)
for i in range(2,1000001):
 f[i] = (i*f[i-1])%M
for i in range(2,1000001):
 f[i] = (f[i]*f[i-1])%M

for _ in range(inp()):
 n = inp()
 print(f[n])

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

M = 10**9+7
f = [1]*(1000001)
for i in range(2,1000001):
 f[i] = (i*f[i-1])%M
for i in range(2,1000001):
 f[i] = (f[i]*f[i-1])%M

for _ in range(inp()):
 n = inp()
 print(f[n])

from sys import stdin,stdout
from collections import defaultdict
input=stdin.readline
print=stdout.write
T=int(input())
M=1000000007
n=1000005
Array=[1]
f=1
for j in range(1,n+1):
 Array.append((f*j*Array[j-1])%M)
 f=(f*j)%M
for i in range(T):
 print(str(Array[int(input())])+"\n")

fact = [0]*1000009
dp = [0]*1000009
fact[1]=1
fact[2]=2
dp[1]=1
dp[2]=2
mod = 1000000007
for i in range(3,1000001):
 fact[i]=((fact[i-1]%mod)*(i%mod))%mod
for i in range(3,1000001):
 dp[i]=((dp[i-1]%mod)*(fact[i]%mod))%mod
t = int(input())
for i in range(t):
 n = int(input())
 print(dp[n]%mod)

# cook your dish here
m = 1000000007
def jk(n):
 arr = [1]
 cnt = 1
 ans = []
 for i in range(1,n+1):
  cnt = (cnt*i)%m
  ans.append(cnt)
 for i in range(1,len(ans)):
  arr.append((arr[-1]*ans[i])%m)
 return arr
t = jk(10**6)
for _ in range(int(input())):
 n = int(input())
 print(t[n-1])

from sys import *
input=stdin.readline
l=[0]*(10**6+1)
l[1]=1
p=1
m=10**9+7
for i in range(2,10**6+1):
 l[i]=(l[i-1]*(p*i)%m)%m
 p*=i
 p=p%m
for u in range(int(input())):
 print(l[int(input())])



from collections import Counter
import string
import math
import sys
def array_int():
 return [int(i) for i in sys.stdin.readline().split()]
def vary(number_of_variables):
 if number_of_variables==1:
  return int(sys.stdin.readline())
 if number_of_variables>=2:
  return list(map(int,sys.stdin.readline().split())) 
def makedict(var):
 return dict(Counter(var))
mod=1000000007
fact=[1]*1000001
c=1
for i in range(1,1000001):
 fact[i]=(fact[i-1]*c)%mod
 c+=1
prod=[1]*1000001
pro=1
for i in range(1,1000000+1):
 pro=((pro%mod)*fact[i])%mod
 prod[i]=pro 
for _ in range(vary(1)):
 n=vary(1)
 
 
 print(prod[n]%mod)
 


 


 





from collections import Counter
import string
import math
import sys
def array_int():
 return [int(i) for i in sys.stdin.readline().split()]
def vary(number_of_variables):
 if number_of_variables==1:
  return int(sys.stdin.readline())
 if number_of_variables>=2:
  return list(map(int,sys.stdin.readline().split())) 
def makedict(var):
 return dict(Counter(var))
mod=1000000007
fact=[1]*1000001
c=1
for i in range(1,1000001):
 fact[i]=(fact[i-1]*c)%mod
 c+=1

for _ in range(vary(1)):
 n=vary(1)
 pro=1
 for i in range(1,n+1):
  pro=((pro%mod)*fact[i])%mod
 print(pro%mod)
 


 


 





from sys import *
input=stdin.readline
l=[0]*(10**6+1)
l[1]=1
p=1
m=10**9+7
for i in range(2,10**6+1):
 l[i]=(l[i-1]*(p*i)%m)%m
 p*=i
 p=p%m
for u in range(int(input())):
 print(l[int(input())])


l=[0]*(10**6+1)
l[1]=1
p=1
m=10**9+7
for i in range(2,10**6+1):
 l[i]=(l[i-1]*(p*i)%m)%m
 p*=i
 p=p%m
for u in range(int(input())):
 print(l[int(input())])


from math import factorial
from functools import reduce 

lst=[1]*(10**6+1)

for j in range(1,10**6+1):
 lst[j]=(lst[j-1]*j)%(10**9+7)
for j in range(1,10**6+1):
 lst[j]=(lst[j-1]*lst[j])%(10**9+7)
for i in range(int(input())):
 n=int(input())
 x=lst[n]
 print(x%(10**9 +7))

t=int(input())
n=[]
for i in range(t):
 num=int(input())
 n.append(num)
fact=[1]
facti=[1]
for i in range(1,max(n)+1):
 fact.append(i*fact[i-1]%1000000007)
 facti.append(facti[i-1]*fact[i]%1000000007)
for i in n:
 print(facti[i])

try:
 t=int(input())
 n=[]
 for i in range(t):
  num=int(input())
  n.append(num)
 fact=[1]
 facti=[1]
 for i in range(1,max(n)+1):
  fact.append(i*fact[i-1]%1000000007)
  facti.append(facti[i-1]*fact[i]%1000000007)
 for i in n:
  print(facti[i])
except:
 pass

try:
 m=10**9+7
 def jk(n):
  count = 1
  arr=[]
  ans=[1]
  
  for i in range(1,n+1):
   count = (count*i)%m
   arr.append(count)
   
  for i in range(1,len(arr)):
   ans.append((ans[-1]*arr[i])%m)
 
  return ans
  
 t = jk(10**6)
 for _ in range(int(input())):
  num = int(input())
  print(t[num-1])
  
except:
 pass

try:
 m=10**9+7
 def jk(n):
  count = 1
  arr=[]
  ans=[1]
  
  for i in range(1,n+1):
   count = (count*i)%m
   arr.append(count)
   
  for i in range(1,len(arr)):
   ans.append((ans[-1]*arr[i])%m)
 
  return ans
  
 t = jk(10**6)
 for _ in range(int(input())):
  num = int(input())
  print(t[num-1])
  
except:
 pass

m=10**9+7
def jk(n):
 count = 1
 arr=[]
 ans=[1]
 
 for i in range(1,n+1):
  count = (count*i)%m
  arr.append(count)
 
 for i in range(1,len(arr)):
  ans.append((ans[-1]*arr[i])%m)
 
 return ans
  
t = jk(10**6)
for _ in range(int(input())):
 num = int(input())
 print(t[num-1])

def cal(n):
 prod = 1
 fac = 1
 for i in range(1,n+1):
  fac*=i
  fac = fac%1000000007 
  prod*=fac
  prod = prod%1000000007
 print(prod)

t = int(input())
while t:
 prod = 1
 fac = 1
 t-=1
 n = int(input())
 cal(n)

from math import factorial
from functools import reduce 

lst=[1]*(10**6+1)

for j in range(1,10**6+1):
 lst[j]=(lst[j-1]*j)%(10**9+7)
for j in range(1,10**6+1):
 lst[j]=(lst[j-1]*lst[j])%(10**9+7)
for i in range(int(input())):
 n=int(input())
 x=lst[n]
 print(x%(10**9 +7))

a=[0]*(10**6 + 1)
mod=10**9 + 7
a[1]=1
p=1
for i in range(2,10**6 + 1):
 a[i]=(a[i-1]*((p*i)%mod)%mod)
 p*=i
 p=p%mod
t=int(input())
for i in range(t):
 n=int(input())
 print(str(a[n]))


m = 10**9+7
n = 10**6

h = 1
b = [0]*n
c = [0]*n

for i in range(1,n+1):
 h = (h*i)%m
 b[i-1] = h
h=1
for i in range(n):
 h = (h*b[i])%m
 c[i] = h
for z in range(int(input())):
 print(c[int(input())-1])

m = 10**9+7
n = 10**6

h = 1
b = [0]*n
c = [0]*n

for i in range(1,n+1):
 h *= i
 h %= m
 b[i-1] = h%m
h=1
for i in range(n):
 h *= b[i]
 h %= m
 c[i] = h%m
for z in range(int(input())):
 print(c[int(input())-1])

from sys import stdin,stdout
a=[0]*(10**6 + 1)
mod=10**9 + 7
a[1]=1
p=1
for i in range(2,10**6 + 1):
 a[i]=(a[i-1]*((p*i)%mod)%mod)
 p*=i
 p=p%mod
t=int(stdin.readline())
for i in range(t):
 n=int(stdin.readline())
 stdout.write(str(a[n]))
 stdout.write('\n')

n=100000
m=1000000007
a=[0]*n
a[0]=1
fib=1
for i in range(2,n-200):
 fib=(fib*i)%m
 a[i-1]=(a[i-2]*fib)%m
for _ in range(int(input())):
 n=int(input())
 print(a[n-1])