#include <bits/stdc++.h>
using std::max;
long long l, r;
int k;
int f[1030][20][2], g[1030][20][2];
long long bin[19];
int dgt[19];
inline int calc(long long lm) {
  if (lm == 0) return 0;
  memset(dgt, 0, sizeof(dgt));
  int top = -1;
  long long temp = lm;
  while (temp) dgt[++top] = temp % 10, temp /= 10;
  memset(f, -1, sizeof(f));
  memset(g, 0, sizeof(g));
  f[0][0][1] = 0;
  g[0][0][1] = 1;
  int ii = 1;
  while (bin[18 - ii] > lm) f[0][ii][1] = 0, g[0][ii][1] = 1, ++ii;
  for (; ii <= 18; ++ii) f[0][ii][0] = 0, g[0][ii][0] = 1;
  for (int i = 1; i <= 18; ++i) {
    for (int d = 0; d <= 9; ++d) {
      if (1ll * d * bin[18 - i] > lm) break;
      for (int s = 0; s < 1024; ++s) {
        if (d == 0 && s == 0) continue;
        if (d == dgt[18 - i]) {
          if (f[s][i - 1][1] != -1) {
            if (f[s | (1 << d)][i][1] == -1)
              f[s | (1 << d)][i][1] = 0, g[s | (1 << d)][i][1] = 0;
            (f[s | (1 << d)][i][1] +=
             (f[s][i - 1][1] + 1ll * d * bin[17 - i + 1] % 998244353 *
                                   g[s][i - 1][1] % 998244353) %
             998244353) %= 998244353;
            (g[s | (1 << d)][i][1] += g[s][i - 1][1]) %= 998244353;
          }
          if (f[s][i - 1][0] != -1) {
            if (f[s | (1 << d)][i][0] == -1)
              f[s | (1 << d)][i][0] = 0, g[s | (1 << d)][i][0] = 0;
            (f[s | (1 << d)][i][0] +=
             (f[s][i - 1][0] + 1ll * d * bin[17 - i + 1] % 998244353 *
                                   g[s][i - 1][0] % 998244353) %
             998244353) %= 998244353;
            (g[s | (1 << d)][i][0] += g[s][i - 1][0]) %= 998244353;
          }
        }
        if (d > dgt[18 - i]) {
          if (f[s][i - 1][0] != -1) {
            if (f[s | (1 << d)][i][0] == -1)
              f[s | (1 << d)][i][0] = 0, g[s | (1 << d)][i][0] = 0;
            (f[s | (1 << d)][i][0] +=
             (f[s][i - 1][0] + 1ll * d * bin[17 - i + 1] % 998244353 *
                                   g[s][i - 1][0] % 998244353) %
             998244353) %= 998244353;
            (g[s | (1 << d)][i][0] += g[s][i - 1][0]) %= 998244353;
          }
        }
        if (d < dgt[18 - i]) {
          if (f[s][i - 1][1] != -1) {
            if (f[s | (1 << d)][i][0] == -1)
              f[s | (1 << d)][i][0] = 0, g[s | (1 << d)][i][0] = 0;
            (f[s | (1 << d)][i][0] +=
             (f[s][i - 1][1] + 1ll * d * bin[17 - i + 1] % 998244353 *
                                   g[s][i - 1][1] % 998244353) %
             998244353) %= 998244353;
            (g[s | (1 << d)][i][0] += g[s][i - 1][1]) %= 998244353;
          }
          if (f[s][i - 1][0] != -1) {
            if (f[s | (1 << d)][i][0] == -1)
              f[s | (1 << d)][i][0] = 0, g[s | (1 << d)][i][0] = 0;
            (f[s | (1 << d)][i][0] +=
             (f[s][i - 1][0] + 1ll * d * bin[17 - i + 1] % 998244353 *
                                   g[s][i - 1][0] % 998244353) %
             998244353) %= 998244353;
            (g[s | (1 << d)][i][0] += g[s][i - 1][0]) %= 998244353;
          }
        }
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < 1024; ++i) {
    if (__builtin_popcount(i) > k) continue;
    (ans += (max(0, f[i][18][1]) + max(0, f[i][18][0])) % 998244353) %=
        998244353;
  }
  return ans;
}
int main() {
  bin[0] = 1;
  for (int i = 1; i <= 17; ++i) bin[i] = bin[i - 1] * 10ll;
  scanf("%I64d%I64d", &l, &r);
  scanf("%d", &k);
  int ans = (calc(r) - calc(l - 1) + 998244353) % 998244353;
  printf("%d\n", ans);
  return 0;
}

### Prompt

Your task is to create a cpp solution to the following problem:

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 std::max;
long long l, r;
int k;
int f[1030][20][2], g[1030][20][2];
long long bin[19];
int dgt[19];
inline int calc(long long lm) {
  if (lm == 0) return 0;
  memset(dgt, 0, sizeof(dgt));
  int top = -1;
  long long temp = lm;
  while (temp) dgt[++top] = temp % 10, temp /= 10;
  memset(f, -1, sizeof(f));
  memset(g, 0, sizeof(g));
  f[0][0][1] = 0;
  g[0][0][1] = 1;
  int ii = 1;
  while (bin[18 - ii] > lm) f[0][ii][1] = 0, g[0][ii][1] = 1, ++ii;
  for (; ii <= 18; ++ii) f[0][ii][0] = 0, g[0][ii][0] = 1;
  for (int i = 1; i <= 18; ++i) {
    for (int d = 0; d <= 9; ++d) {
      if (1ll * d * bin[18 - i] > lm) break;
      for (int s = 0; s < 1024; ++s) {
        if (d == 0 && s == 0) continue;
        if (d == dgt[18 - i]) {
          if (f[s][i - 1][1] != -1) {
            if (f[s | (1 << d)][i][1] == -1)
              f[s | (1 << d)][i][1] = 0, g[s | (1 << d)][i][1] = 0;
            (f[s | (1 << d)][i][1] +=
             (f[s][i - 1][1] + 1ll * d * bin[17 - i + 1] % 998244353 *
                                   g[s][i - 1][1] % 998244353) %
             998244353) %= 998244353;
            (g[s | (1 << d)][i][1] += g[s][i - 1][1]) %= 998244353;
          }
          if (f[s][i - 1][0] != -1) {
            if (f[s | (1 << d)][i][0] == -1)
              f[s | (1 << d)][i][0] = 0, g[s | (1 << d)][i][0] = 0;
            (f[s | (1 << d)][i][0] +=
             (f[s][i - 1][0] + 1ll * d * bin[17 - i + 1] % 998244353 *
                                   g[s][i - 1][0] % 998244353) %
             998244353) %= 998244353;
            (g[s | (1 << d)][i][0] += g[s][i - 1][0]) %= 998244353;
          }
        }
        if (d > dgt[18 - i]) {
          if (f[s][i - 1][0] != -1) {
            if (f[s | (1 << d)][i][0] == -1)
              f[s | (1 << d)][i][0] = 0, g[s | (1 << d)][i][0] = 0;
            (f[s | (1 << d)][i][0] +=
             (f[s][i - 1][0] + 1ll * d * bin[17 - i + 1] % 998244353 *
                                   g[s][i - 1][0] % 998244353) %
             998244353) %= 998244353;
            (g[s | (1 << d)][i][0] += g[s][i - 1][0]) %= 998244353;
          }
        }
        if (d < dgt[18 - i]) {
          if (f[s][i - 1][1] != -1) {
            if (f[s | (1 << d)][i][0] == -1)
              f[s | (1 << d)][i][0] = 0, g[s | (1 << d)][i][0] = 0;
            (f[s | (1 << d)][i][0] +=
             (f[s][i - 1][1] + 1ll * d * bin[17 - i + 1] % 998244353 *
                                   g[s][i - 1][1] % 998244353) %
             998244353) %= 998244353;
            (g[s | (1 << d)][i][0] += g[s][i - 1][1]) %= 998244353;
          }
          if (f[s][i - 1][0] != -1) {
            if (f[s | (1 << d)][i][0] == -1)
              f[s | (1 << d)][i][0] = 0, g[s | (1 << d)][i][0] = 0;
            (f[s | (1 << d)][i][0] +=
             (f[s][i - 1][0] + 1ll * d * bin[17 - i + 1] % 998244353 *
                                   g[s][i - 1][0] % 998244353) %
             998244353) %= 998244353;
            (g[s | (1 << d)][i][0] += g[s][i - 1][0]) %= 998244353;
          }
        }
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < 1024; ++i) {
    if (__builtin_popcount(i) > k) continue;
    (ans += (max(0, f[i][18][1]) + max(0, f[i][18][0])) % 998244353) %=
        998244353;
  }
  return ans;
}
int main() {
  bin[0] = 1;
  for (int i = 1; i <= 17; ++i) bin[i] = bin[i - 1] * 10ll;
  scanf("%I64d%I64d", &l, &r);
  scanf("%d", &k);
  int ans = (calc(r) - calc(l - 1) + 998244353) % 998244353;
  printf("%d\n", ans);
  return 0;
}

```