#include <bits/stdc++.h>

void Yes() {
    std::cout << "YES" << "\n";
    return;
}

void No() {
    std::cout << "NO" << "\n";
    return;
}

template<typename T>
void out(T x) { std::cout << x << "\n"; }

using namespace std;
using int = long long;
using PII = pair<int, int>;

const int N = 2e5 + 10;
int k, m;
string n;
int a[1005];
int dp[1004][9004];
const int mod = 1e9 + 7;
//int tong[9001];
int cc(int x) {
    int tmp = 0;
    while (x) {
        tmp += x % 10;
        x /= 10;
    }
    return tmp;
}

int dfs(int pos, int sum, int lim, int lead0) {
    if (pos == 0)
    {
        for (int i = 1; i <= k - 1; i++) {
            sum = cc(sum);
        }
        return sum == m;
    }
    if (!lim && !lead0 && dp[pos][sum] != -1) {
        return dp[pos][sum];
    }
    int up = lim ? a[pos] : 9;
    int tmp = 0;
    for (int i = 0; i <= up; i++) {
        tmp += dfs(pos - 1, sum + i, lim && (i == up), lead0 && (i == 0));
        tmp%=mod;
    }
    if (!lim && !lead0) {
        return dp[pos][sum] = tmp;
    }
    return tmp;
}

int cal(string s) {
    int len = 0;
    reverse(s.begin(), s.end());
    for (auto p: s) {
        a[++len] = p - '0';
    }
    return dfs(len, 0, 1, 1);
}

void Solve() {
    for (int i = 0; i <= 1002; i++)
        for (int j = 0; j <= 9001; j++)
            dp[i][j] = -1;
    cin >> n >> k >> m;
    k = min(k, 5int);
    cout << cal(n) <<"\n";
}

signed main() {
    for (int i = 0; i <= 1002; i++)
        for (int j = 0; j <= 9001; j++)
            dp[i][j] = -1;
    int t = 1;
    cin>>t;
    while (t--)
        Solve();
}

answer.code:17:7: error: expected nested-name-specifier before ‘int’
   17 | using int = long long;
      |       ^~~
answer.code: In function ‘void Solve()’:
answer.code:73:16: error: unable to find numeric literal operator ‘operator""int’
   73 |     k = min(k, 5int);
      |                ^~~~
answer.code:73:16: note: use ‘-fext-numeric-literals’ to enable more built-in suffixes