ADADIG - Ada and Digits


As you might already know, Ada the Ladybug is a farmer and she also loves math. One day, as farming is sometimes very notorious work, she was thinking about numbers. She was wondering about how many numbers there are having exactly same digital sum as digital product.

She have found out some answers for small N (sum & product), but then the numbers started getting big. Can you help her to find out the answers for bigger sums to satisfy her mind?

Input

The first line contains a single integer 1 ≤ T ≤ 100, number of test-cases.

Each of the next line contains a single number 1 ≤ N ≤ 3*105 , the required sum (and so the required product).

Output

For each test-case, print the number of existing numbers. Since this number might be pretty huge, output it modulo 109+7 (1000000007).

Example Input

8
1
2
3
7
8
12
16
144

Example Output

1
1
1
1
23
240
1091
243368058

hide comments
febrianandawp: 2017-09-16 18:45:16

Nice problem XD. I got many TLEs because of wrong approach

Last edit: 2017-09-16 18:49:37
morass: 2017-09-15 22:31:42

@gokul_prasanth: Good day to you

Simply find the number of numbers whose digital sum equals to "N" and so digital product equals to "N" (modulo 10^9+7)

Example -> 21221 ... 2+1+2+2+1==8 / 2*1*2*2*1==8 (so for N==8 you would count this number)

Hope it heped a little bit

Good Luck ^_^

shubham_001: 2017-09-15 16:24:23

@gokul you need to output number of numbers having sumOfDigits=ProductOfDigits ,say for each prime only the number itself is the sum and product of itself so answer for all primes is 1 and if it is more than 1 digit number it wud be 0

Last edit: 2017-09-16 06:15:21
gokul_prasanth: 2017-09-15 15:41:52

@morass can you please explain the problem??

morass: 2017-09-15 15:12:40

@[Rampage] Blue.Mary: Right, firstly I aimed for "easier" solution so I've let the constraints to be low :/ Anyway if you think I'm missing some kind of worst-case (or why it is unexpected?) or it deserves another "hard" version with bigger constraints (or so) tell me ^_^

Thanx & Wish you a great day!!

[Rampage] Blue.Mary: 2017-09-15 15:07:38

Unexpected 0.00 second AC...


Added by:Morass
Date:2017-09-15
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All