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
|
armaanepiic:
2024-01-06 01:32:04
anybody!
|
|
legion0retr0:
2020-08-21 15:28:51
Wow dp+recursion+math nice combo |
|
nadstratosfer:
2020-01-03 07:42:49
Found some analysis of this yesterday in my "todo_maybe_one_day" dir. It's dated 2017-09-29 and going through it brought back strangely vivid memories of that day when I was fruitlessly trying to figure this out while going about my work and other things. Seems it had really gotten under my skin back then! Anyway I gave up too early it seems as this time I only needed some 15mins for the crucial insight to kick in. My solution is a bit clumsy, hopefully I won't need another 2 years to correct the part I don't like. Fun problem though! |
|
sohit5012:
2019-05-21 11:22:02
@morass I have considered almost all kinds of test cases and yet I am getting a wrong answer on test 14 and 15, can you please check my submission and give a little hint where I am getting wrong.
|
|
akjol2049:
2018-11-23 10:54:59
can it be solved with dynamic programming ..Thanks
|
|
zephyr_96:
2018-03-14 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: 2018-03-14 18:32:56 |
|
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
|
|
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?? |
| Added by: | Morass |
| Date: | 2017-09-15 |
| Time limit: | 0.5s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
RSS