Kids and Integers

This is the fourth time that Little I and Little J have played the counting game, so they have decided not to create lengthy problem statements anymore. You only need to know that they have come up with another strange rule for selecting the numbers to count, and want to figure out how many such numbers are there.

For any positive integer $n$, we define the function $f(n)$ as the sum of its decimal digits, for example, $f(114514) = 1 + 1 + 4 + 5 + 1 + 4 = 16$. Obviously, $f(n)$ is also a positive integer, so the function can be applied repeatedly as $f(f(n))$, $f(f(f(n)))$, and so on. For positive integers $n$ and $k$, we define the function $g(n, k)$ as $f(f(\ldots f(n)\ldots))$ with $k$ applications of $f$.

To make the counting game different each time, the kids decided to set two positive integers $k$ and $m$ for each round, and then to specify the rule: in this round, the numbers to count are all positive integers $n$ satisfying $g(n, k) = m$.

As both of them are game experts, they can find arbitrarily many such integers. To prevent the game from going on forever, they also pick a positive integer $N$ in each round as the upper bound for counting. They want to know: among positive integers not exceeding $N$, how many numbers satisfy $g(n, k) = m$? Since the answer may be very large, find it modulo $10^9 + 7$.

The first line of the input contains one integer $T$, representing the number of rounds Little I and Little J will play ($1 \le T \le 5$).

Each of the next $T$ lines contains three positive integers $N$, $k$, $m$ describing a single round of the game ($1 \le N \le 10^{1000}$, $1 \le k, m \le 10^9$).

For each of the $T$ rounds, print a line with a single integer: the number of numbers that cannot be counted in this round of the game, modulo $10^9 + 7$.