Kandy had a dream in which he dreamt of the Good String. The impact of that string was so much that it forced Kandy to calculate the number of possible Good Strings after he woke up.
Kandy is afraid to code right now. So, he mails you the required conditions to calculate the number of possible Good Strings. Some properties of these strings include:-
They are of given specific length.
They consist of digits only between 0-9 (both inclusive).
They may have leading zeros.
They have certain Good Product which is defined as product of
digits in the string.
Their F(Good Product) is always greater than 0.

F(P) is calculated as Bitwise XOR of all the prime factors of P.

For eg: 12 is written as 22 * 31
Therefore, F(12) = 2 xor 2 xor 3 = 3

Input:
First line of the input consists of number of testcases T
Next T lines consists of length of the Good String N

Output:
Print the number of possible Good Strings modulo 10^9+7 of given length N for each test case in a separate line.

Constraints:
Subtask 1:
1 ≤ T ≤ 100
1 ≤ N ≤ 105
Subtask 2:
1 ≤ T ≤ 10
1 ≤ N ≤ 1018

Note:
Leading zeros in the string also contribute to its product of digits which would be zero anyway.

SAMPLE INPUT
5
1
5
7
8
2

SAMPLE OUTPUT
6
52806
4370778
39585232
64

Explanation

[Case 1:] For N = 1, possible evil strings are "2","3","5","6","7","8". Their F(Evil Product) is greater than 0.

Rest of the cases is for you to figure out.

见题面

见题面