Farmer Bini

Time limit1sMemory limit1024 MB

Summary

Count N-digit positive integers (no leading zero) whose digit sum and digit product are both divisible by 7, modulo 1e9+7, for up to 10000 queries.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, Math, Number theory
Solved: No attempts yet

Problem

Bini, a born farmer, has lately fallen deep into studying numbers. While studying numbers hard, Bini could not help but be startled, because the digit 7 looks like the sickle Bini cherishes most. An old saying goes that one does not know the digit 7 even with a sickle set down in front of them. It occurred to Bini to wonder how many numbers have both the sum and the product of their digits divisible by 7. To find the answer, Bini resolved to farm hard.

Given N, write a program that finds the number of N-digit positive integers for which both the sum and the product of the digits are divisible by 7. A number cannot start with 0.

Input

The first line gives the number of test cases T.

Each of the following T lines gives an integer N, one per line.

Output

For each test case, print the answer on its own line. The answer can be very large, so print it modulo $10^9 + 7$ .

Constraints

$1 \le T \le 10{,}000$
$1 \le N \le 10{,}000$

Hint

Among 2-digit numbers, 70 and 77 satisfy the condition.

Among 4-digit numbers, 2237 and others satisfy the condition. For 2237, the sum of the digits is $2+2+3+7=14$ and the product of the digits is $2\times 2\times 3\times 7=84$ , and both 14 and 84 are divisible by 7.

Examples1

Example 1
Input
```
4
1
2
3
4
```
Expected output
```
1
2
54
692
```