Mehta and the Evil Strings
Tag(s):

## Algorithms, Bitmask, Linear Algebra, Mathematics, Matrix Exponentiation, Medium

Problem
Editorial
Analytics

Background:
Mehta had a horrible nightmare in which he dreamt of the Evil String. The impact of that string was so much that it forced Mehta to calculate the number of possible Evil Strings after he woke up.

Mehta is afraid to code right now. So, he mails you the required conditions to calculate the number of possible Evil Strings. Some properties of these strings include:-

They are of given specific length.
They consist of digits only between 0-9 (both inclusive).
They have certain Evil Product which is defined as product of digits in the string.
Their F(Evil 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 Evil String N

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

Constraints:
1 <= T <= 100
1 <= N <= 105
1 <= T <= 10
1 <= N <= 1018

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

Problem statement in native language : http://hck.re/Lo1koZ

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.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

Japan National Programming Challenge

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Basic Math
• Algorithms > Searching
• Algorithms > Dynamic Programming