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 testcases.
Each of the next line contains a single number 1 ≤ N ≤ 3*10^{5} , the required sum (and so the required product).
Output
For each testcase, print the number of existing numbers. Since this number might be pretty huge, output it modulo 10^{9}+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
akjol2049:
20181123 10:54:59
can it be solved with dynamic programming ..Thanks


zephyr_96:
20180314 16:50:10
TLE on test case 14 :( with java .@Morass, please check my latest submission. This is the reason I don't try new problems with JAVA. Most of the time TLE with java or very strict time limits with java. Last edit: 20180314 18:32:56 

holmesherlock:
20180128 16:23:44
Last edit: 20180128 16:35:25 

febrianandawp:
20170916 18:45:16
Nice problem XD. I got many TLEs because of wrong approach Last edit: 20170916 18:49:37 

morass:
20170915 22:31:42
@gokul_prasanth: Good day to you


shubham_001:
20170915 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: 20170916 06:15:21 

gokul_prasanth:
20170915 15:41:52
@morass can you please explain the problem?? 

morass:
20170915 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 worstcase (or why it is unexpected?) or it deserves another "hard" version with bigger constraints (or so) tell me ^_^


[Rampage] Blue.Mary:
20170915 15:07:38
Unexpected 0.00 second AC... 
Added by:  Morass 
Date:  20170915 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 