OPC1708C - Factorial large

no tags 

 

Given a number n print its factorial%(10^9+7)

 

 

Given a number n print its factorial%(10^9+7)

Input

 

First line contains an integer t (t<=10000). 

t lines follow.Each line contains an integer n. (0<=n<=1000000)

 

Output

For each test case print factorial(n)%(10^9+7)

Example

Input:
5
2
3
1
400
0

Output:
2
6
1
390998217
1



Added by:bashrc is back
Date:2012-08-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64