#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
const int N = 1e3 + 5;
const int M = 9e3 + 5;
const int P = 1e9 + 7;
int T, n, k, m, op[M], t[2][M], f[N][M];
char s[N];
inline int read()
{
    int w = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        w = w * 10 + (ch - 48);
        ch = getchar();
    }
    return w;
}

inline void Add(int &x, int y) { x += y; if (x >= P) x -= P; }

inline int dfs(int p, int lim, int sum)
{
 if (p == n + 1) return (sum == 0);
    if (!lim && f[n - p][sum] != -1) return f[n - p][sum];
   
    int up = std::min(sum, (lim ? s[p] - '0' : 9)), res = 0;
    for (register int i = 0; i <= up; i++) Add(res, dfs(p + 1, lim && (i == (s[p] - '0')), sum - i));
    if (!lim) return f[n - p][sum] = res;
    return res; 
}

signed main()
{
    T = read();
    for (int i = 0; i < M; i++)
    {
        int x = i, cnt = 0; 
        while (x)
        {
            cnt += (x % 10);
            x /= 10;
        }
        op[i] = cnt;
    }
memset(f, -1, sizeof(f));
    while (T--)
    {
        // memset(t, 0, sizeof(t));
        // memset(f, -1, sizeof(f));
        scanf("%s", s + 1); k = read(), m = read(); n = strlen(s + 1);
        if (m > 9000) { printf("0\n"); continue; }
        if (k >= 2 && m > 36) { printf("0\n"); continue; } 
        int kel = 0;
        for (int i = 0; i <= 9000; i++) t[kel][i] = dfs(1, 1, i); k--;
        // for (int i = 0; i <= 20; i++) printf("%lld ", t[kel][i]); printf("\n");
        k = std::min(4, k);
        if (k == 0) { printf("%d\n", t[kel][m]); continue; }
        kel ^= 1; memset(t[kel], 0, sizeof(t[kel])); for (int j = 0; j <= 9000; j++) Add(t[kel][op[j]], t[kel ^ 1][j]); k--;
        for (int i = 1; i <= k; i++)
        {
            kel ^= 1; memset(t[kel], 0, sizeof(t[kel]));
            for (int j = 0; j <= 36; j++) Add(t[kel][op[j]], t[kel ^ 1][j]);
        }
        printf("%d\n", t[kel][m]);
    }
   
    return 0;
}