## Liberating Cities

Time Limit: 1 sec
Memory Limit: 256 MB
Attempts: 1
Accuracy: 0.00%
Author: Akashdeep Goel

Daenarys Stormborn is preparing to free a new city from slavery.In order to do so she and her army has to clear the barrier of a big wall of length n.For clearing the wall she creates a stair of length n joinning smaller stairs.The length of smaller stairs can only be unequal primes.If the number of ways she can create stair of length n is 'a'

then b is a mod 1000000007.And p is the largest prime factor of b. Her dragons demand her to break p as sums of q1,q2â€¦qk(for any k > 0) i.e. q1+q2+....+qk=p, such that q1,q2...qk have largest possible GCD. If more than one such set exists then take the set in which q1,q2...qk have largest product .GCD of single number is 1 .

Report (Product of q1,q2....qk) mod 1000000007. If the number of ways modulo m ie. b = 0 or 1 report 0 .

Input-

First Line contains t, number of test cases.

Followed by t lines each containing an integer n, the length of wall .

Output-

Report the value of (Product of q1,q2....qk) mod 1000000007 as asked above.

Constraints-

0 < t <= 10

4 < n < 1200

Example-

Input-

2

5

6

Output-

2

0

Explanation-

5=2+3 or 5

Thus a=2

Thus b=2(2 mod 1000000007)

Thus p=2(Largest prime factor of b)

Thus possible sets of qi 's with largest GCD (1,1) or (2)

Thus one with largest Product is 2

ID

SUBMITTED AT

STATUS

LANGUAGE

TIME

MEMORY USED

USER

TIME

STATUS

LANGUAGE

TIME

MEMORY USED

4 years ago

cpp

0.00 sec

0 KB