#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);
}
i64 f[1001][9001];
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);
        }
    }
    f[0][0] = 1;
    for (int i = 1; i <= 1000; i++)
        for (int k = 0; k < 10; k++)
            for (int j = k; j <= 9000; j++)
            {
                f[i][j] += f[i - 1][j - k];
                f[i][j] %= mod;
            }
}
// 1000*9000*10
// 预处理非flag,x个数和为y的方案数C(x+y-1,x-1),但是有大于10的，对m=1，到m=10的预处理出来，
int dp[1000][N][2];
int vis[1000][N][2];
int cnt = 0;
int m, k;
string s;
vector<int> bad;
int dfs(int n, int sum, int flag)
{
    assert(sum <= 9000);
    if (bad.empty() || (s.size() - n) * 9 + sum < m)
        return 0;
    if (sum > bad.back())
        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;
    if (flag)
    {
        int hi = s[n] - '0';
        for (int lo = 0; lo <= hi; lo++)
        {
            res += dfs(n + 1, sum + lo, flag && (lo == hi));
        }
    }
    else
    {
        for (int i = 0; i < bad.size() && sum + (s.size() - n) * 9 >= bad[i]; i++)
        {
            if (sum <= bad[i])
            {
                res += f[s.size() - n][bad[i] - sum];
            }
        }
    }
    //014
    return dp[n][sum][flag] = res % mod;
}
void solve()
{
    cin >> s;
    cin >> k >> m;
    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;
    }
    k = min(k, 4);
    ++cnt;
    bad.clear();
    for (int i = 0; i <= 9000; i++)
    {
        if (ch[i][k - 1] == m)
        {
            bad.push_back(i);
        }
    }
    cout << dfs(0, 0, 1) << endl;
}

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