NICESEQ - NICE SEQUENCES


A nice sequence is a sequence of digits in which a digit d is placed at any index iff d is 0 or any divisor of d (except 1) has been placed already. First digit can be anything from 1 to 9.

Find the number of nice sequences of length n.

Input

Input consists of number of test cases t
Following t lines have a single line containing n as described in the problem statement.

Output

Print the number of nice sequences of length n modulo 1000000007 in a separate line.

Example

Input
2
1
2

Output
9
23

Explanation

For n=2 nice sequences are: 10, 20, 22, 24, 26, 28, 30, 33, 36, 39, 40, 44, 48 and so on !

Constraints

1<=n<=1000


hide comments
mahmud2690: 2018-07-12 10:44:23

for n = 3, result = 71.

prakash1108: 2018-07-06 17:57:18

what will be the answer for n=3?

shubham_001: 2018-06-29 07:11:44

atleast explain the question and testcases properly

i_am_ipsita: 2018-06-26 17:20:04

Nice question ! ;)

Last edit: 2018-06-26 17:20:28
raunak96: 2018-06-26 12:05:18

good question a2j sirjee :)

aayushsinha44: 2018-06-26 07:33:40

Nice Question.

shuvam_kedia: 2018-06-25 22:26:03

Nice question a2j !

amit_redoc: 2018-06-25 21:22:58

nice question a2j ;)

ayush926: 2018-06-25 20:35:46

Nice question.
a2j007 pro!


Added by:a2j
Date:2018-06-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own Problem