You are given two integers l and r (l ≤ r). Your task is to calculate the sum of numbers from l to r (including l and r) such that each number contains at most k different digits, and print this sum modulo 998244353.

For example, if k = 1 then you have to calculate all numbers from l to r such that each number is formed using only one digit. For l = 10, r = 50 the answer is 11 + 22 + 33 + 44 = 110.

Input

The only line of the input contains three integers l, r and k (1 ≤ l ≤ r < 10^{18}, 1 ≤ k ≤ 10) — the borders of the segment and the maximum number of different digits.

Output

Print one integer — the sum of numbers from l to r such that each number contains at most k different digits, modulo 998244353.

Examples

Input

10 50 2


Output

1230


Input

1 2345 10


Output

2750685


Input

101 154 2


Output

2189

Note

For the first example the answer is just the sum of numbers from l to r which equals to (50 ⋅ 51)/(2) - (9 ⋅ 10)/(2) = 1230. This example also explained in the problem statement but for k = 1.

For the second example the answer is just the sum of numbers from l to r which equals to (2345 ⋅ 2346)/(2) = 2750685.

For the third example the answer is 101 + 110 + 111 + 112 + 113 + 114 + 115 + 116 + 117 + 118 + 119 + 121 + 122 + 131 + 133 + 141 + 144 + 151 = 2189.
#include <bits/stdc++.h>
namespace SPLAY {
long long n, root, i, tot, opt, x;
long long father[100000], count[100000], data[100000], value[100000];
long long son[100000][3];
inline void Rotate(long long x, long long w) {
  long long y;
  y = father[x];
  count[y] = count[y] - count[x] + count[son[x][w]];
  count[x] = count[x] - count[son[x][w]] + count[y];
  son[y][3 - w] = son[x][w];
  if (son[x][w]) father[son[x][w]] = y;
  father[x] = father[y];
  if (father[y])
    if (y == son[father[y]][1])
      son[father[y]][1] = x;
    else
      son[father[y]][2] = x;
  father[y] = x;
  son[x][w] = y;
}
inline void splay(long long x) {
  long long y;
  while (father[x]) {
    y = father[x];
    if (!father[y])
      if (x == son[y][1])
        Rotate(x, 2);
      else
        Rotate(x, 1);
    else if (y == son[father[y]][1])
      if (x == son[y][1]) {
        Rotate(y, 2);
        Rotate(x, 2);
      } else {
        Rotate(x, 1);
        Rotate(x, 2);
      }
    else if (x == son[y][2]) {
      Rotate(y, 1);
      Rotate(x, 1);
    } else {
      Rotate(x, 2);
      Rotate(x, 1);
    }
  }
  root = x;
}
inline long long search(long long x, long long w) {
  while (data[x] != w) {
    if (w == data[x]) return x;
    if (w < data[x]) {
      if (!son[x][1]) break;
      x = son[x][1];
    } else {
      if (son[x][2] == 0) break;
      x = son[x][2];
    }
  }
  return x;
}
inline void insert(long long w) {
  long long k, kk;
  bool flag;
  if (!tot) {
    tot = 1;
    father[1] = 0;
    count[1] = 1;
    data[1] = w;
    root = 1;
    value[1] = 1;
    return;
  }
  k = search(root, w);
  if (data[k] == w) {
    value[k]++;
    kk = k;
    flag = true;
  } else {
    tot++;
    data[tot] = w;
    father[tot] = k;
    count[tot] = 1;
    value[tot] = 1;
    if (data[k] > w)
      son[k][1] = tot;
    else
      son[k][2] = tot;
    flag = 0;
  }
  while (k) {
    count[k]++;
    k = father[k];
  }
  if (flag)
    splay(kk);
  else
    splay(tot);
}
inline long long Extreme(long long x, long long w) {
  const long long lala[3] = {0, 2147483647, -2147483647};
  long long k, tmp;
  k = search(x, lala[w]);
  tmp = data[k];
  splay(k);
  return tmp;
}
inline void del(long long x) {
  long long k, y;
  k = search(root, x);
  if (data[k] != x)
    splay(k);
  else {
    splay(k);
    if (value[k] > 1) {
      value[k]--;
      count[k]--;
    } else if (!son[k][1]) {
      y = son[k][2];
      son[k][2] = 0;
      count[k] = 0;
      data[k] = 0;
      value[k] = 0;
      root = y;
      father[root] = 0;
    } else {
      father[son[k][1]] = 0;
      y = Extreme(son[k][1], 1);
      son[root][2] = son[k][2];
      count[root] = count[root] + count[son[k][2]];
      if (son[root][2] != 0) father[son[root][2]] = root;
      data[k] = 0;
      son[k][1];
      son[k][2] = 0;
      value[k] = 0;
    }
  }
}
inline long long pred(long long x) {
  long long k;
  k = search(root, x);
  splay(k);
  if (data[k] < x) return data[k];
  return Extreme(son[k][1], 1);
}
inline long long succ(long long x) {
  long long k;
  k = search(root, x);
  splay(k);
  if (data[k] > x) return data[k];
  return Extreme(son[k][2], 2);
}
inline long long kth(long long x, long long w) {
  long long i, tmp;
  i = root;
  while (!((x >= count[son[i][w]] + 1) && (x <= count[son[i][w]] + value[i])) &&
         (i != 0)) {
    if (x > count[son[i][w]] + value[i]) {
      x = x - count[son[i][w]] - value[i];
      i = son[i][3 - w];
    } else
      i = son[i][w];
  }
  tmp = i;
  splay(i);
  return tmp;
}
inline long long findnum(long long x) {
  long long k;
  k = search(root, x);
  splay(k);
  root = k;
  return count[son[k][1]] + 1;
}
}  // namespace SPLAY
using namespace std;
inline long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -f;
  for (; isdigit(ch); ch = getchar()) x = 10 * x + ch - '0';
  return x * f;
}
const long long maxn = 23, mod = 998244353;
long long l, r, k;
long long p10[maxn];
long long stk[maxn];
pair<long long, long long> dp[maxn][(1 << 10) + 5];
pair<long long, long long> dfs(long long pos, long long mask, long long qd_zero,
                               long long lim) {
  if (pos == 0) {
    return make_pair((__builtin_popcount(mask) <= k), 0);
  }
  if (!lim && !qd_zero && ~dp[pos][mask].first) return dp[pos][mask];
  pair<long long, long long> ans;
  ans.first = ans.second = 0;
  long long Lim = lim ? stk[pos] : 9;
  for (long long i = 0; i <= Lim; i++) {
    long long curmask = mask | (1 << i);
    if (i == 0 && qd_zero) curmask = mask;
    pair<long long, long long> cur =
        dfs(pos - 1, curmask, qd_zero && i == 0, lim && i == stk[pos]);
    (ans.first += cur.first) %= mod;
    (ans.second +=
     (cur.second + ((p10[pos - 1] * i) % mod) * cur.first % mod) % mod) %= mod;
  }
  if (!lim && !qd_zero) dp[pos][mask] = ans;
  return ans;
}
long long solve(long long x) {
  for (long long i = 0; i <= 22; i++)
    for (long long j = 0; j <= (1 << 10) + 4; j++) dp[i][j].first = -1;
  long long top = 0;
  while (x) {
    stk[++top] = x % 10;
    x = x / 10;
  }
  return dfs(top, 0, 1, 1).second;
}
signed main() {
  l = read(), r = read(), k = read();
  p10[0] = 1;
  for (long long i = 1; i <= 18; i++) p10[i] = (p10[i - 1] * 10) % mod;
  printf("%I64d\n", ((solve(r) - solve(l - 1)) % mod + mod) % mod);
}
