SANVI - Sanvi and Magical Numbers
Let us define a Magical number as a positive integer number which meets the following criteria on its representation:
- It does not contain any zeros.
- Each digits may appears at most twice in it.
- The absolute differences between summation of count of non-prime digits and count of prime-digits do not exceed K.
Sanvi likes numbers which are not prime. So, she wants to allow at most M non-prime numbers to violate the rule number-2. Sanvi also uses following algorithm in rule number-3 to calculate count of each digit d in a number:
count(d) = min(total occurrences of d in number, 2)
You are given an integer number N. Your task is to find the total Magical numbers in the range from 1 to N following Sanvi's command. Since the answer could be very large, print it modulo 10^9+7.
Input
Input contains several test cases up to EOF (End Of File), which contains three space separated integers N (1 ≤ N ≤ 10^18), K (0 ≤ K ≤ 18) and M (0 ≤ M ≤ 5) as described in the problem statement. Total test cases will not exceed 5.
Output
Output a single integer denoting the total Magical numbers from 1 to N following Sanvi's command. Since the answer could be very large print it modulo 10^9+7.
Example
Input: 10 1 0 5 3 2 Output: 9 5
hide comments
Oleg:
2023-10-19 06:38:22
Took 16 WAs to realize that M is not "M non-prime numbers" like description states but "M non-prime digits"
|
|
BISHAL GAUTAM:
2017-08-27 19:55:42
Please read the problem statement again. I think problem is easy to understand. |
|
ellaharris873:
2017-08-27 08:55:16
Hello,
|
Added by: | BISHAL GAUTAM |
Date: | 2017-08-26 |
Time limit: | 3s-5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | https://devskill.com/CodingProblems/ViewProblem/392 |