#include <bits/stdc++.h>

template <int m>
class ModInt {
    int raw;
    using mint = ModInt;
    using i64 = int64_t;

public:
    ModInt() : raw(0) {}
    ModInt(const auto &v) {
        raw = v % m;
        if (raw < 0) {
            raw += m;
        }
    }
    int operator()() const {
        return raw;
    }

    mint &operator+=(const mint &rhs) {
        raw += rhs.raw;
        if (raw >= m) {
            raw -= m;
        }
        return *this;
    }
    mint &operator-=(const mint &rhs) {
        raw -= rhs.raw;
        if (raw < 0) {
            raw += m;
        }
        return *this;
    }
    mint &operator*=(const mint &rhs) {
        raw = (i64)raw * rhs.raw % m;
        return *this;
    }
    mint &operator/=(const mint &rhs) {
        return *this *= qpow(rhs, m - 2);
    }

    friend mint operator+(const mint &lhs, const mint &rhs) {
        return mint{lhs} += rhs;
    }
    friend mint operator-(const mint &lhs, const mint &rhs) {
        return mint{lhs} -= rhs;
    }
    friend mint operator*(const mint &lhs, const mint &rhs) {
        return mint{lhs} *= rhs;
    }
    friend mint operator/(const mint &lhs, const mint &rhs) {
        return mint{lhs} /= rhs;
    }

    static mint qpow(mint a, i64 b) {
        mint res = 1;
        while (b) {
            if (b & 1) {
                res *= a;
            }
            a *= a, b >>= 1;
        }
        return res;
    }
};

using mint = ModInt<static_cast<int>(1e9 + 7)>;

int mod(std::string s) {
    int res = 0;
    for (char c : s) {
        res += (c - '0');
    }
    return res % 9;
}
mint val(std::string s) {
    mint res = 0;
    for (char c : s) {
        res = res * 10 + (c - '0');
    }
    return res;
}

void solve() {
    std::string s;
    std::cin >> s;

    int k, m;
    std::cin >> k >> m;

    if (k >= 10) {
        if (m > 9) {
            std::cout << "0\n";
        } else {
            m %= 9;
            mint ans = val(s);
            int p = mod(s);
            std::cout << ((ans - p) / 9 + (p >= m))() << '\n';
        }
        return;
    }

    int sum = 0;
    std::vector<mint> g;
    for (char c : s) {
        int d = c - '0';
        
        std::vector<mint> ng(std::max<int>(sum + d, g.size() + 10));
        for (int i = 0; i < d; ++i) {
            ng[sum + i] += 1;
        }
        for (int i = 0; i < 10; ++i) {
            for (int x = 0; x < g.size(); ++x) {
                ng[x + i] += g[x];
            }
        }
        sum += d;

        g.swap(ng);
        while (!g.empty() && g.back()() == 0) {
            g.pop_back();
        }
    }

    if (g.size() < sum + 1) {
        g.resize(sum + 1);
    }
    g[sum] += 1;
    g[0] -= 1;

    auto f = [](int x) {
        int res = 0;
        while (x) {
            res += x % 10;
            x /= 10;
        }
        return res;
    };
    for (int i = 1; i <= k - 1; ++i) {
        std::vector<mint> ng(g.size());

        for (int x = 0; x < g.size(); ++x) {
            ng[f(x)] += g[x];
        }

        g.swap(ng);
        while (!g.empty() && g.back()() == 0) {
            g.pop_back();
        }
    }

    if (g.size() < m + 1) {
        std::cout << "0\n";
    } else {
        std::cout << g[m]() << '\n';
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }
}