Given a number n print factorial(n) % (10⁹ + 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⁹ + 7)

Example

Input:
5
2
3
1
400
0

Output:
2
6
1
390998217
1