#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define all(x) x.begin(), x.end()
const int N = 9000 + 10;
int ch[N][4];
int mod = 1e9 + 7;
void change(int &x)
{
    int y = 0;
    while (x)
    {
        y += x % 10;
        x /= 10;
    }
    swap(x, y);
}
void init()
{
    for (int i = 1; i <= 9000; i++)
    {
        int x = i;
        for (int j = 0; j < 4; j++)
        {
            ch[i][j] = x;
            change(x);
        }
    }
}
int dp[1000][N][2];
int vis[1000][N][2];
int cnt = 0;
int m, k;
string s;
int dfs(int n, int sum, int flag)
{
    assert(sum <= 9000);
    if ((s.size() - n) * 9 + sum < m)
        return 0;
    if (n == s.size())
        return ch[sum][k - 1] == m;
    if (vis[n][sum][flag] == cnt)
        return dp[n][sum][flag];
    vis[n][sum][flag] = cnt;
    i64 res = 0;
    int hi = flag ? s[n] - '0' : 9;
    for (int lo = 0; lo <= hi; lo++)
    {
        res += dfs(n + 1, sum + lo, (flag) && (lo == hi));
    }
    return dp[n][sum][flag] = res % mod;
}
void solve()
{
    cin >> s;
    cin >> k >> m;
    k = min(k, 4);
    // m<=10000
    if (m >= 1e5)
    {
        cout << 0 << endl;
        return;
    }
    if (k > 1 && m > 35)
    {
        cout << 0 << endl;
        return;
    }
    if (k > 2 && m > 11)
    {
        cout << 0 << endl;
        return ;
    }
    ++cnt;
    cout << dfs(0, 0, true) << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    init();
    while (T--)
        solve();
}