Master Oogway has forseen that a panda named Po will be the dragon warrior, and the master of Chi. But he did not tell anyone about the spell that would make him the master of Chi, and has left Po confused. Now Po has to defeat Kai, who is the super villian, the strongest of them all. Po needs to master Chi, and he finds a spell which unlocks his powerful Chi. But the spell is rather strange. It asks Po to calculate the factorial of a number! Po is very good at mathematics, and thinks that this is very easy. So he leaves the spell, thinking it's a hoax. But little does he know that this can give him the ultimate power of Chi. Help Po by solving the spell and proving that it's not a hoax.

-----Input-----
First line of input contains an integer T denoting the number of test cases.
The next T lines contain an integer N.

-----Output-----
For each test case, print a single line containing the solution to the spell which is equal to factorial of N, i.e. N!. Since the output could be large, output it modulo 1589540031(Grand Master Oogway's current age).

-----Constraints-----
- 1 ≤ T ≤ 100000
- 1 ≤ N ≤ 100000

-----Example-----
Input:
4
1
2
3
4

Output:
1
2
6
24

见题面

见题面