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