#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double PI = acos(-1.0);
const double EPS = 1e-9;
struct Scanner {
  bool hasNext = 1;
  bool hasRead = 1;
  int nextInt() {
    hasRead = 0;
    int res = 0;
    char flag = 1, ch = getchar();
    while (ch != EOF && !isdigit(ch)) {
      hasRead = 1;
      flag = (ch == '-') ? -flag : flag;
      ch = getchar();
    }
    while (ch != EOF && isdigit(ch)) {
      hasRead = 1;
      res = res * 10 + (ch - '0');
      ch = getchar();
    }
    if (ch == EOF) hasNext = 0;
    return res * flag;
  }
  long long nextLL() {
    hasRead = 0;
    long long res = 0;
    char flag = 1, ch = getchar();
    while (ch != EOF && !isdigit(ch)) {
      hasRead = 1;
      flag = (ch == '-') ? -flag : flag;
      ch = getchar();
    }
    while (ch != EOF && isdigit(ch)) {
      hasRead = 1;
      res = res * 10 + (ch - '0');
      ch = getchar();
    }
    if (ch == EOF) hasNext = 0;
    return res * flag;
  }
  char nextChar() {
    hasRead = 0;
    char ch = getchar();
    while (ch != EOF && isspace(ch)) {
      hasRead = 1;
      ch = getchar();
    }
    if (ch == EOF) hasNext = 0;
    return ch;
  }
  int nextString(char *str) {
    hasRead = 0;
    int len = 0;
    char ch = getchar();
    while (ch != EOF && isspace(ch)) {
      hasRead = 1;
      ch = getchar();
    }
    while (ch != EOF && !isspace(ch)) {
      hasRead = 1;
      str[++len] = ch;
      ch = getchar();
    }
    str[len + 1] = 0;
    if (ch == EOF) hasNext = 0;
    return len;
  }
} sc;
void rd(int &x) { x = sc.nextInt(); }
void rd(long long &x) { x = sc.nextLL(); }
void rd(char &x) { x = sc.nextChar(); }
void rd(char *x) { sc.nextString(x); }
template <typename T1, typename T2>
void rd(pair<T1, T2> &x) {
  rd(x.first);
  rd(x.second);
}
template <typename T>
void rd(T *x, int n) {
  for (int i = 1; i <= n; ++i) rd(x[i]);
}
struct Printer {
  void printInt(int x) {
    if (x < 0) {
      putchar('-');
      x = -x;
    }
    if (x >= 10) printInt(x / 10);
    putchar('0' + x % 10);
  }
  void printLL(long long x) {
    if (x < 0) {
      putchar('-');
      x = -x;
    }
    if (x >= 10) printLL(x / 10);
    putchar('0' + x % 10);
  }
} printer;
void pr(int x, char ch = '\n') {
  printer.printInt(x);
  putchar(ch);
}
void pr(long long x, char ch = '\n') {
  printer.printLL(x);
  putchar(ch);
}
template <typename T1, typename T2>
void pr(pair<T1, T2> x, char ch = '\n') {
  pr(x.first, ' ');
  pr(x.second, ch);
}
template <typename T>
void pr(T *x, int n) {
  for (int i = 1; i <= n; ++i) pr(x[i], " \n"[i == n]);
}
template <typename T>
void pr(vector<T> &x) {
  int n = x.size();
  for (int i = 1; i <= n; ++i) pr(x[i - 1], " \n"[i == n]);
}
template <typename T>
void cmin(T &x, T y) {
  if (y < x) x = y;
}
template <typename T>
void cmax(T &x, T y) {
  if (y > x) x = y;
}
const int MOD = 1e9 + 7;
struct Matrix {
  static const int MOD = 1e9 + 7;
  static const int MAXK = 11;
  int k, A[MAXK][MAXK];
  void Init(int k) {
    this->k = k;
    memset(A, 0, sizeof(A));
  }
  Matrix operator+(const Matrix &ma) const {
    Matrix res;
    res.Init(k);
    for (int i = 1; i <= k; ++i) {
      for (int j = 1; j <= k; ++j) {
        res.A[i][j] = A[i][j] + ma.A[i][j];
        if (res.A[i][j] >= MOD) res.A[i][j] -= MOD;
      }
    }
    return res;
  }
  Matrix operator-(const Matrix &ma) const {
    Matrix res;
    res.Init(k);
    for (int i = 1; i <= k; ++i) {
      for (int j = 1; j <= k; ++j) {
        res.A[i][j] = A[i][j] - ma.A[i][j];
        if (res.A[i][j] < 0) res.A[i][j] += MOD;
      }
    }
    return res;
  }
  Matrix operator*(const Matrix &ma) const {
    Matrix res;
    res.Init(k);
    for (int i = 1; i <= k; ++i) {
      for (int t = 1; t <= k; ++t) {
        for (int j = 1, T = A[i][t]; j <= k; ++j) {
          res.A[i][j] += 1LL * T * ma.A[t][j] % MOD;
          if (res.A[i][j] >= MOD) res.A[i][j] -= MOD;
        }
      }
    }
    return res;
  }
  Matrix pow(long long n) const {
    Matrix res, x;
    res.Init(k), x.Init(k);
    for (int i = 1; i <= k; ++i) {
      res.A[i][i] = 1;
      for (int j = 1; j <= k; ++j) x.A[i][j] = A[i][j];
    }
    while (n) {
      if (n & 1) res = res * x;
      x = x * x;
      n >>= 1;
    }
    return res;
  }
  void Show() {
    for (int i = 1; i <= k; ++i) {
      for (int j = 1; j <= k; ++j) printf("%d%c", A[i][j], " \n"[j == k]);
    }
  }
} m1, ma[200005];
int n, m;
int cnt[10];
struct Solver {
  void InitOnce() {
    int t = sc.nextInt();
    cerr << "t"
            " = "
         << (t) << endl;
    m1.Init(10);
    m1.A[0 + 1][9 + 1] = 1;
    m1.A[1 + 1][0 + 1] = 1;
    m1.A[1 + 1][9 + 1] = 1;
    for (int i = 2; i <= 9; ++i) m1.A[i + 1][i - 1 + 1] = 1;
    ma[0].Init(10);
    for (int i = 0; i <= 9; ++i) ma[0].A[i + 1][i + 1] = 1;
    for (int i = 1; i <= 200000; ++i) ma[i] = m1 * ma[i - 1];
  }
  void Read() {
    rd(n);
    rd(m);
  }
  void Solve() {
    memset(cnt, 0, sizeof(cnt));
    int x = n;
    while (x) {
      cnt[x % 10] += 1;
      x /= 10;
    }
    long long ans = 0;
    for (int i = 0; i <= 9; ++i) {
      for (int j = 0; j <= 9; ++j) ans += ma[m].A[i + 1][j + 1] * cnt[j];
    }
    ans %= MOD;
    pr(ans);
  }
} solver;
int main() {
  solver.InitOnce();
  while (1) {
    solver.Read();
    if (!sc.hasRead) break;
    solver.Solve();
    if (!sc.hasNext) break;
  }
  return 0;
}
