// https://qoj.ac/contest/1464/problem/7996
// 1次f最大达到9000（sum 10^1000-1）
// 2次f最大达到35（sum 8999）
// 3次f最大达到11（sum 29）
// 4次f最大达到9（sum 9）
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const int M = 9e3 + 5;
const int N = 1e3 + 5;
ll dp[N][M], mp[M];
string str;
int k, m, n;
int SUM(int x) {
    int res = 0;
    while (x) {
        res += (x % 10);
        x /= 10;
    }
    return res;
}
ll dfs(int p, int s, bool reach_up) { // p for position, s for sum
    // reach_up for str[p-1] have reached upper limit or not
    if (p == n) return mp[s];
    if (p > n) return 0;
    if (!reach_up && dp[p][s] != -1) return dp[p][s];
    ll res = 0;
    for (int i = 0; i <= 9; i++) {
        if (reach_up && str[p] - '0' < i) continue;
        res += dfs(p + 1, s + i, reach_up & (str[p] - '0' == i));
        res %= mod;
    }
    if (!reach_up) dp[p][s] = res;
    return res;
}
void solve() {
    cin >> str >> k >> m;
    if ((m > 9000) || (k >= 2 && m >= 35)) {
        cout << 0 << '\n';
        return;
    }
    n = str.length();
    for (int i = 1; i <= 9000; i++) {
        int x = i;
        for (int i = 1; i < k; i++) {
            x = SUM(x);
            if (x < 10) break;
        }
        if (x == m) mp[i] = 1;
        else mp[i] = 0;
    }
    memset(dp, -1, sizeof(dp));
    cout << dfs(0, 0, 1) << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}