//(ᗜ ˰ ᗜ)
// #define NDEBUG
#include <bits/stdc++.h>
using namespace std;
namespace LING
{
#ifdef ONLINE_JUDGE
#define DBG(...) ;
#define dbg(...) ;
#else
#define DBG(x) cout << "! " << #x << " = " << x << endl
#include "debug.h"
#endif
	using ll = long long;
	using db = double;
#define SPO(x) fixed << setprecision(x)
#define FOR(i, l, r) for (ll i = l; i <= (r); ++i)
#define ROF(i, r, l) for (ll i = r; i >= (l); --i)
#define edl '\n'
#define fir first
#define sec second
#define str string
#define pll pair<ll, ll>
#define heap priority_queue
	// constexpr db PI = acos(-1.0);
	// constexpr db EPS = 1.0e-9;
	constexpr long long LNF = 0x3f3f3f3f3f3f3f3fLL;
	constexpr int INF = 0x3f3f3f3f;
	constexpr long long MOD = 1e9 + 7;
	constexpr ll MXN = 1e6 + 5;
	ll KSM(ll base, ll exp, ll MOD)
	{
		ll res = 1;
		base %= MOD;
		while (exp)
		{
			if (exp & 1)
				res = (res * base) % MOD;
			base = (base * base) % MOD;
			exp >>= 1;
		}
		return res;
	}
}
using namespace LING;
template<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(ll x) : x{norm(x % P)} {}
    
    constexpr int norm(int x) const {
        if (x < 0) {
            x += P;
        }
        if (x >= P) {
            x -= P;
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(P - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    constexpr MInt &operator*=(MInt rhs) {
        x = 1LL * x * rhs.x % P;
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        ll v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};
 
template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();
 
// constexpr int P = 998244353;
constexpr int P = 1e9+7;
using Z = MInt<P>;
 
str n;
ll x;
ll k, m;
Z f[1005][9005];
ll l, r, p, len, a[1005];
ll cc(ll n)
{
	ll ans = 0;
	while (n)
	{
		ans += n % 10;
		n /= 10;
	}
	return ans;
}
Z 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 && f[pos][sum] != -1)
	{
		return f[pos][sum];
	}
	int up = lim ? a[pos] : 9;
	Z tmp = 0;
	for (int i = 0; i <= up; i++)
	{
		tmp += dfs(pos - 1, sum + i, lim && (i == up), lead0 && (i == 0));
	}
	if (!lim && !lead0)
	{
		return f[pos][sum] = tmp;
	}
	return tmp;
}
Z 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(void)
{
	for (int i = 0; i <= 1002; i++)
		for (int j = 0; j <= 9001; j++)
			f[i][j] = -1;
	cin >> n >> k >> m;
	k = min(k, 4LL);
	cout << cal(n) << edl;
	return;
}
int main(void)
{
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	// #ifndef ONLINE_JUDGE
	// freopen("cin.txt","r",stdin);
	// freopen("cout.txt","w",stdout);
	// #endif

	int t = 1;
	cin >> t;
	while (t--)
		Solve();
	return 0;
}