#include <bits/stdc++.h>
using namespace std;

constexpr int mod = 1'000'000'007;
constexpr int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
constexpr int sub(int a, int b) { return a - b < 0 ? a - b + mod : a - b; }
constexpr int mul(int64_t a, int64_t b) {
  return static_cast<int>(a * b % mod);
}

constexpr int C = 9001;

constexpr int L = 1000 + 5;

int cnt[C];

int f(int x) {
  int r = 0;
  while (x) {
    r += x % 10;
    x /= 10;
  }
  return r;
}

int dp[L][C];

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  dp[0][0] = 1;
  for (int i = 1; i < L; ++i) {
    for (int x = 0; x < 10; ++x) {
      for (int j = 0; j + x < C; ++j) {
        dp[i][j + x] = add(dp[i][j + x], dp[i - 1][j]);
      }
    }
  }

  int t;
  cin >> t;
  while (t--) {
    string N;
    int k, m;
    cin >> N >> k >> m;

    for (int s = 1; s < C; ++s) {
      cnt[s] = 0;
      int pre = 0;
      for (int i = 0; i < ssize(N); ++i) {
        for (int x = 0; x < N[i] - '0'; ++x) {
          int cur = pre + x;
          if (cur > s)
            break;
          cnt[s] = add(cnt[s], dp[ssize(N) - 1 - i][s - cur]);
        }
        pre += N[i] - '0';
        if (pre > s)
          break;
      }
    }
    int tot = 0;
    for (auto c : N)
      tot += c - '0';
    cnt[tot] = add(cnt[tot], 1);

    int ans = 0;
    if (k <= 4) {
      for (int i = 1; i < C; ++i) {
        int cur = i;
        for (int j = 1; j < k; ++j)
          cur = f(cur);
        if (cur == m)
          ans = add(ans, cnt[i]);
      }
    } else {
      for (int i = 1; i < C; ++i) {
        int cur = i % 9;
        if (cur == 0)
          cur = 9;
        if (cur == m)
          ans = add(ans, cnt[i]);
      }
    }
    cout << ans << '\n';
  }
  return 0;
}