Migrated from Lutece 1555 Fact0rial

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Calculate $N!$ mod $(10^{11}+3)$.

Input

The first line contains an integer $T$, denoting the number of the test cases.

Each test case contains one number $N$.

$1\leq T\leq 5, 1\leq N\leq 10^{11}+3$

Output

$N!$ mod $(10^{11}+3)$.

Samples

5
1
3
5
7
20

1
6
120
5040
8103652940

Resources

The 15th UESTC Programming Contest Preliminary