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>
const int mod = 998244353;
int cnt1[1024];
int f[20][1024], g[20][1024];
int F[20][1024], G[20][1024];
int p10[20];
void init() {
  p10[0] = 1;
  for (int i = 1; i < 20; ++i) p10[i] = p10[i - 1] * 10ll % mod;
  cnt1[0] = 0;
  for (int i = 1; i < 1024; ++i) cnt1[i] = cnt1[i >> 1] + (i & 1);
  for (int i = 0; i < 10; ++i)
    f[1][1 << i] = 1, g[1][1 << i] = 1, F[1][1 << i] = i, G[1][1 << i] = i;
  g[0][0] = 1;
  for (int i = 2; i <= 18; ++i) {
    for (int k = 0; k < 1024; ++k) {
      for (int j = 0; j < 10; ++j) {
        g[i][k | (1 << j)] = (g[i][k | (1 << j)] + g[i - 1][k]) % mod;
        G[i][k | (1 << j)] = (G[i][k | (1 << j)] + G[i - 1][k]) % mod;
        G[i][k | (1 << j)] = (G[i][k | (1 << j)] +
                              g[i - 1][k] * 1ll * j % mod * p10[i - 1] % mod) %
                             mod;
      }
      for (int j = 1; j < 10; ++j) {
        f[i][k | (1 << j)] = (f[i][k | (1 << j)] + g[i - 1][k]) % mod;
        F[i][k | (1 << j)] = (F[i][k | (1 << j)] + G[i - 1][k]) % mod;
        F[i][k | (1 << j)] = (F[i][k | (1 << j)] +
                              g[i - 1][k] * 1ll * j % mod * p10[i - 1] % mod) %
                             mod;
      }
    }
  }
}
int calc(long long lim, int c) {
  if (lim == (long long)(1e18)) {
    int ans = 0;
    for (int i = 1; i <= 18; ++i) {
      for (int k = 0; k < 1024; ++k) {
        if (cnt1[k] <= c) ans = (ans + F[i][k]) % mod;
      }
    }
    return ans;
  }
  int L[20], n = 0;
  while (lim) {
    L[++n] = lim % 10;
    lim /= 10;
  }
  int S = 0;
  int ans = 0;
  for (int i = 1; i <= n - 1; ++i) {
    for (int k = 0; k < 1024; ++k) {
      if (cnt1[k] <= c) ans = (ans + F[i][k]) % mod;
    }
  }
  int presum = 0;
  for (int i = n; i >= 1; --i) {
    int lo = (i == n) ? 1 : 0;
    for (int j = L[i] - 1; j >= lo; --j) {
      int tmp = (1 << j) | S;
      for (int k = 0; k < 1024; ++k) {
        if (cnt1[tmp | k] <= c) {
          ans = (ans +
                 g[i - 1][k] * 1ll * (presum * 10ll + j) % mod * p10[i - 1] %
                     mod +
                 G[i - 1][k]) %
                mod;
        }
      }
    }
    S |= (1 << L[i]);
    presum = (presum * 10ll + L[i]) % mod;
  }
  return ans;
}
int main() {
  init();
  long long L, R;
  int k;
  scanf("%lld%lld%d", &L, &R, &k);
  printf("%d\n", (calc(R + 1, k) - calc(L, k) + mod) % mod);
  return 0;
}
