Forbidden Number Counting

For any positive integer \(n\), define the function \(f(n)\) as the sum of its digits in decimal representation, i.e., \[ f(n)=\sum{\text{digits of }n}, \] for example \(f(114514)=1+1+4+5+1+4=16\). Since \(f(n)\) is also a positive integer, we can apply it repeatedly. Define \[ g(n,k)=\underbrace{f(f(\cdots f(n)\cdots))}_{k \text{ times}}. \] In a counting game, two players choose two positive integers \(k\) and \(m\) and forbid all positive integers \(n\) such that \(g(n,k)=m\). In addition, a positive integer \(N\) is given as an upper bound. Your task is to determine how many numbers in the range \([1, N]\) are forbidden.

Note: When \(k \ge 2\), it can be observed that for any \(n \ge 10\), \(g(n,k)\) becomes the digital root of \(n\). In other words, if \(1 \le m \le 8\) then \(g(n,k)=m\) if and only if \(n \equiv m \pmod{9}\), and if \(m=9\) then \(g(n,k)=9\) if and only if \(n\) is a multiple of 9. If \(m \ge 10\) and \(k \ge 2\), only one-digit numbers can satisfy \(g(n,k)=m\>.

inputFormat

The input consists of a single line containing three space-separated positive integers \(k\), \(m\), and \(N\) (the upper bound). \(N\) can be large so consider using efficient algorithms.

outputFormat

Output a single integer: the count of forbidden numbers \(n\) in the range \([1, N]\) that satisfy \(g(n,k)=m\).

sample

1 7 100

8