#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int l[18], r[18];
int k;
int f[2][1 << 10][2][2], g[2][1 << 10][2][2];
int add(int x, int y) {
  x += y;
  return x >= mod ? x - mod : x;
}
int sub(int x, int y) {
  x -= y;
  return x < 0 ? x + mod : x;
}
int mul(int x, int y) { return 1ll * x * y % mod; }
void turn(long long x, int* a) {
  while (x) {
    a[0] = x % 10;
    x /= 10;
    a += 1;
  }
}
int main() {
  long long x, y;
  scanf("%lld %lld %d", &x, &y, &k);
  turn(x, l);
  turn(y, r);
  bool bz = 0, bz1 = 1;
  bool all_zerol = 1, all_zeror = 1;
  for (int i = 17; i >= 0; i--, swap(bz, bz1)) {
    for (int j = 1; j < 10; j++) {
      if ((all_zerol && j < l[i]) || !all_zerol) continue;
      if (all_zeror && j > r[i]) continue;
      f[bz1][1 << j][all_zerol && j == l[i]][all_zeror && j == r[i]] = 1;
      g[bz1][1 << j][all_zerol && j == l[i]][all_zeror && j == r[i]] = j;
    }
    all_zerol &= !l[i];
    all_zeror &= !r[i];
    for (int j = 0; j < (1 << 10); j++)
      for (int upl = 0; upl < 2; upl++)
        for (int upr = 0; upr < 2; upr++) {
          int v = f[bz][j][upl][upr], vv = g[bz][j][upl][upr];
          f[bz][j][upl][upr] = 0;
          g[bz][j][upl][upr] = 0;
          for (int k = 0; k < 10; k++) {
            if (upl && k < l[i]) continue;
            if (upr && k > r[i]) continue;
            f[bz1][j | (1 << k)][upl && k == l[i]][upr && k == r[i]] = add(
                f[bz1][j | (1 << k)][upl && k == l[i]][upr && k == r[i]], v);
            if (v) {
              int yy;
              yy = 0;
            }
            g[bz1][j | (1 << k)][upl && k == l[i]][upr && k == r[i]] =
                add(g[bz1][j | (1 << k)][upl && k == l[i]][upr && k == r[i]],
                    add(mul(vv, 10), mul(v, k)));
          }
        }
  }
  int ans = 0;
  for (int i = 0; i < (1 << 10); i++) {
    int x = i;
    int y = 0;
    while (x) {
      y++;
      x -= x & -x;
    }
    if (y > k) continue;
    for (int j = 0; j < 4; j++) ans = add(ans, g[bz][i][j & 1][j >> 1]);
  }
  printf("%d\n", ans);
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int l[18], r[18];
int k;
int f[2][1 << 10][2][2], g[2][1 << 10][2][2];
int add(int x, int y) {
  x += y;
  return x >= mod ? x - mod : x;
}
int sub(int x, int y) {
  x -= y;
  return x < 0 ? x + mod : x;
}
int mul(int x, int y) { return 1ll * x * y % mod; }
void turn(long long x, int* a) {
  while (x) {
    a[0] = x % 10;
    x /= 10;
    a += 1;
  }
}
int main() {
  long long x, y;
  scanf("%lld %lld %d", &x, &y, &k);
  turn(x, l);
  turn(y, r);
  bool bz = 0, bz1 = 1;
  bool all_zerol = 1, all_zeror = 1;
  for (int i = 17; i >= 0; i--, swap(bz, bz1)) {
    for (int j = 1; j < 10; j++) {
      if ((all_zerol && j < l[i]) || !all_zerol) continue;
      if (all_zeror && j > r[i]) continue;
      f[bz1][1 << j][all_zerol && j == l[i]][all_zeror && j == r[i]] = 1;
      g[bz1][1 << j][all_zerol && j == l[i]][all_zeror && j == r[i]] = j;
    }
    all_zerol &= !l[i];
    all_zeror &= !r[i];
    for (int j = 0; j < (1 << 10); j++)
      for (int upl = 0; upl < 2; upl++)
        for (int upr = 0; upr < 2; upr++) {
          int v = f[bz][j][upl][upr], vv = g[bz][j][upl][upr];
          f[bz][j][upl][upr] = 0;
          g[bz][j][upl][upr] = 0;
          for (int k = 0; k < 10; k++) {
            if (upl && k < l[i]) continue;
            if (upr && k > r[i]) continue;
            f[bz1][j | (1 << k)][upl && k == l[i]][upr && k == r[i]] = add(
                f[bz1][j | (1 << k)][upl && k == l[i]][upr && k == r[i]], v);
            if (v) {
              int yy;
              yy = 0;
            }
            g[bz1][j | (1 << k)][upl && k == l[i]][upr && k == r[i]] =
                add(g[bz1][j | (1 << k)][upl && k == l[i]][upr && k == r[i]],
                    add(mul(vv, 10), mul(v, k)));
          }
        }
  }
  int ans = 0;
  for (int i = 0; i < (1 << 10); i++) {
    int x = i;
    int y = 0;
    while (x) {
      y++;
      x -= x & -x;
    }
    if (y > k) continue;
    for (int j = 0; j < 4; j++) ans = add(ans, g[bz][i][j & 1][j >> 1]);
  }
  printf("%d\n", ans);
  return 0;
}

```