In a village named CodeVillage, there lived a old man called Digo. Digo is very fond of playing with numbers. His favorite sport is to calculate factorial of large numbers!!! But since factorials can be very large he takes modulo 'm' of the factorials he generates. You have to help him check his answer by generating the mod m of factorial of any number.
Digo knows one thing that if a modulo m is b and c modulo m is d so a*b modulo m is c*d modulo m.
Input:
First line contains the integer 'm'.
Next line contains an integer 'n' giving the number of test cases.
'n' line follows that contain an integer each.

Output:
n lines containing factorial of the integer mod m

Sample input:
91
3
5
4
3

Output:
29
24
6

Explanation of test cases:
here m =91
number of test cases is 3
first integer is 5. 5 factorial is 120 and 120 mod 91=29
second integer is 4. 4 factorial is 24 and 24 mod 91=24
first integer is 3. 3 factorial is 6 and 6 mod 91=6