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.

 

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 seperate line .

Example

Input:
2
1
2

Output
9
23

Explaination :
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