#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define all(x) x.begin(), x.end()
const int N = 9000 + 10;
int bad[N];
int ch[N][4];
int mod = 1e9 + 7;
// k>=1
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);
        }
    }
}
/*
1
114 1 5
*/
int dp[1000][N][2];
int vis[1000][N][2];
int cnt = 0;
int m, k;
int dfs(string &s, int n, int sum, int flag)
{
    assert(sum <= 9000);
    if (n == -1)
        return ch[sum][k - 1] == m;
    if (vis[n][sum][flag] == cnt)
        return dp[n][sum][flag];
    vis[n][sum][flag] = cnt;
    int &res = dp[n][sum][flag];
    res = 0;
    int hi = flag ? s[n] - '0' : 9;
    for (int lo = 0; lo <= hi; lo++)
    {
        res += dfs(s, n - 1, sum + lo, (flag) && (lo == hi));
        res %= mod;
    }
    return res;
}
void solve()
{
    string s;
    cin >> s;
    cin >> k >> m;
    k=min(k,4);
    //(g,n,k)<=1e6
    ++cnt;
    reverse(all(s));
    // 状态数位和[1000][9999],1e8种状态
    i64 res = dfs(s, s.size() - 1, 0, true);
    cout << res << endl;
}

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