Hard Divide and Conquer > Dynamic Programming

Let us define a **Magical number** as a positive integer number which meets the following criteria on its representation: 1.) It does not contain any zeros. 2.) Each digits may appears at most twice in it. 3.) 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**. Sample Input ------------ 10 1 0 5 3 2 Sample Output ------------- 9 5 Note: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. So, **{2,3,5,7} are prime digits**.

Bishal Gautam