SANVI - Sanvi and Magical Numbers

no tags 

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 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
9
5
9

hide comments
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,
I beginner and I do not understand anything yet -:))

Last edit: 2017-08-27 19:54:25

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