Vivek and Sita are in a relationship. Both of them love playing with numbers and treat each other with puzzles every now and then.

When Sita visits her class she comes to see that there is a gift packed in a wooden box which has a lock in it which can only be unlocked by solving the puzzle written on the paper note which is pasted on the top of the box by Vivek.

Sita is stuck with this puzzle, help her in solving it.

The puzzle description is as follows:

R(n) is a function as follows,

R(0) = 1, R(1) = 1, R(2) = 1

R(n) = product of all odd primes less than or equal to n (for n≤10)

R(n) = (2^(n/4) × R(n/5) × R(n/10)) mod (10^9+7) (for n>10)

NOTE: For every fraction, the ceiling value is taken for evaluation. (eg: ceil(4.05) = 5, and ceil(4.9) = 5)

Consider an example:

R(15) = 2^⌈15/4⌉ × R(⌈15/5⌉) × R(⌈15/10⌉) = 2^4 × R(3) × R(2) = 48

Now the puzzle is that you are given n and you have to find out the maximum value of x^y mod (10^9 + 7) such that non negative integers x and y satisfy the relation gcd(x,y) = R(n), where x, y ≤ 5 × R(n)

Here, gcd is the greatest common divisor. Where gcd(0,0) = 0, 0^0 = 0.

Input Format

First line contains an integer T, the number of test cases
T lines will follow, each having an integer N, for which the result needs to be calculated.

Output Format

For each test case, print the desired value on a new line

Constraints

1 ≤ T ≤ 25

0 ≤ N ≤ 30

Input Example

2
1
2

Output Example

1024
1024

Example Explanation

x & y for both the inputs (1&2) can be 1 to 5, and the max value for x^y is when x = 4 and y = 5

SAMPLE INPUT
1
14

SAMPLE OUTPUT
996023990

Explanation

R(14) = 48, x & y can be from 1 to 48×5 (=240). the maximum value of (x^y) mod (10^9 + 7) is when x = 240 and y = 96.

见题面

见题面