#include <bitsdc++.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 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, 4);
    cout << cal(n) << "\n";
}

signed main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
        Solve();
}

answer.code:1:10: fatal error: bitsdc++.h: No such file or directory
    1 | #include <bitsdc++.h>
      |          ^~~~~~~~~~~~
compilation terminated.