Migrated from Lutece 417 Counting

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

In a math class,you are assigned the following task.

First,look at the definition $F(n,d)=k$ which means that in the given number $n$,there are $k$ $d$'s.

For instance, $F(311,1)=2$, $F(311,3)=1$

For the given $(n,k,d)$ you are to find how many $i'$s which can meet the constraits below

1. $1\leq i\leq n$
2. $F(i,d)=k$

Input

Multiple lines ended with EOF

Each line contains three integers $n$($1\leq n<2^{31}$), $k$($1\leq k\leq 9$), $d(1\leq d\leq 9$)

Output

A single integer

Samples

14 1 1
123 2 2
876 2 3

5
2
26

Note

For the first case,there are $5$ numbers $(1,10,12,13,14)$

For the second case,there are $2$ numbers $(22,122)$

Resources

5th BUPT Programming Contest Preliminary