// https://qoj.ac/contest/1464/problem/7996
// 1次f最大达到9000（sum 10^1000-1）
// 2次f最大达到35（sum 8999）
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e3 + 5;
const int M = 9e3 + 5;
const int mod = 1e9 + 7;
int dp[N][M]; // dp[i][j] 表示长度为i+1的总和为j的数的个数
int k, m;
string s;
int n;
int SUM(int x) {
    int res = 0;
    while (x) {
        res += (x % 10);
        x /= 10;
    }
    return res;
}
void pre_dp() {
    memset(dp, 0, sizeof(dp));
    int sum = s[0] - '0';
    for (int i = 0; i < s[0] - '0'; i++) dp[0][i] = 1;
    for (int i = 1; i < n; i++) {
        // 前面的i位数都顶到上限，当前位不超过(s[i]-'0')的数量都++
        for (int j = 0; j <= 9 * (i + 1); j++) {
            if (j - sum >= 0 && j - sum < s[i] - '0') {
                dp[i][j]++;
            }
            for (int k = 0; k <= 9; k++) {
                if (j - k < 0) break;
                dp[i][j] += dp[i - 1][j - k];
                dp[i][j] %= mod;
            }
        }
        sum += s[i] - '0';
    }
    dp[n - 1][sum]++;
}
void solve() {
    cin >> s >> k >> m;
    if (m > 9000 || (k >= 2 && m >= 36)) {
        cout << "0\n";
        return;
    }
    if (k > 4) k = 4;
    n = s.length();
    pre_dp();
    int ans = 0;
    for (int i = 1; i <= 9000; i++) {
        int x = i;
        for (int j = 1; j < k; j++) {
            x = SUM(x);
            if (x < 10) break;
        }
        if (x == m) {
            ans += dp[n - 1][i];
            ans %= mod;
        }
    }
    cout << ans << '\n';
}
int main()
{
    int T_T = 1;
    cin >> T_T;
    while (T_T--)
        solve();
    return 0;
}