#include <bits/stdc++.h>
using namespace std;
const int MO = 998244353;
int ka, ig[20], num[2400], cnt;
long long l, r, f[27][1107][2], g[27][1107][2];
long long query(long long x) {
  long long xx = x, ans = 0;
  cnt = 0;
  while (xx) {
    ig[++cnt] = xx % 10;
    xx /= 10;
  }
  for (int i = cnt; i >= 1; i--) {
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    if (i == cnt)
      for (int j = 1; j <= ig[cnt]; ++j) {
        g[i][(1 << j)][(j == ig[cnt])] = 1;
        f[i][(1 << j)][(j == ig[cnt])] = j;
      }
    else
      for (int j = 1; j <= 9; ++j) {
        g[i][1 << j][0] = 1;
        f[i][1 << j][0] = j;
      }
    for (int j = i - 1; j >= 1; --j)
      for (int k = 0; k < (1 << 10); ++k) {
        for (int kk = 0; kk <= 9; ++kk) {
          g[j][k | (1 << kk)][0] =
              (g[j][k | (1 << kk)][0] + g[j + 1][k][0]) % MO;
          f[j][k | (1 << kk)][0] =
              ((f[j][k | (1 << kk)][0] + f[j + 1][k][0] * 10 % MO) % MO +
               g[j + 1][k][0] * kk % MO) %
              MO;
        }
        for (int kk = 0; kk <= ig[j]; kk++) {
          if (kk == ig[j]) {
            g[j][k | (1 << kk)][1] =
                (g[j + 1][k][1] + g[j][k | (1 << kk)][1]) % MO;
            f[j][k | (1 << kk)][1] =
                (f[j][k | (1 << kk)][1] + f[j + 1][k][1] * 10 % MO +
                 g[j + 1][k][1] * kk % MO) %
                MO;
          } else {
            g[j][k | (1 << kk)][0] =
                (g[j + 1][k][1] + g[j][k | (1 << kk)][0]) % MO;
            f[j][k | (1 << kk)][0] =
                (f[j][k | (1 << kk)][0] + f[j + 1][k][1] * 10 % MO +
                 g[j + 1][k][1] * kk % MO) %
                MO;
          }
        }
      }
    for (int j = 0; j <= (1 << 10) - 1; ++j)
      if (num[j] <= ka) ans = ((ans + f[1][j][0]) % MO + f[1][j][1]) % MO;
  }
  return ans;
}
int main() {
  scanf("%lld%lld%d", &l, &r, &ka);
  for (int i = 0; i < (1 << 10); ++i) num[i] = num[i >> 1] + (i & 1);
  printf("%lld\n", (query(r) - query(l - 1) + MO) % MO);
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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 MO = 998244353;
int ka, ig[20], num[2400], cnt;
long long l, r, f[27][1107][2], g[27][1107][2];
long long query(long long x) {
  long long xx = x, ans = 0;
  cnt = 0;
  while (xx) {
    ig[++cnt] = xx % 10;
    xx /= 10;
  }
  for (int i = cnt; i >= 1; i--) {
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    if (i == cnt)
      for (int j = 1; j <= ig[cnt]; ++j) {
        g[i][(1 << j)][(j == ig[cnt])] = 1;
        f[i][(1 << j)][(j == ig[cnt])] = j;
      }
    else
      for (int j = 1; j <= 9; ++j) {
        g[i][1 << j][0] = 1;
        f[i][1 << j][0] = j;
      }
    for (int j = i - 1; j >= 1; --j)
      for (int k = 0; k < (1 << 10); ++k) {
        for (int kk = 0; kk <= 9; ++kk) {
          g[j][k | (1 << kk)][0] =
              (g[j][k | (1 << kk)][0] + g[j + 1][k][0]) % MO;
          f[j][k | (1 << kk)][0] =
              ((f[j][k | (1 << kk)][0] + f[j + 1][k][0] * 10 % MO) % MO +
               g[j + 1][k][0] * kk % MO) %
              MO;
        }
        for (int kk = 0; kk <= ig[j]; kk++) {
          if (kk == ig[j]) {
            g[j][k | (1 << kk)][1] =
                (g[j + 1][k][1] + g[j][k | (1 << kk)][1]) % MO;
            f[j][k | (1 << kk)][1] =
                (f[j][k | (1 << kk)][1] + f[j + 1][k][1] * 10 % MO +
                 g[j + 1][k][1] * kk % MO) %
                MO;
          } else {
            g[j][k | (1 << kk)][0] =
                (g[j + 1][k][1] + g[j][k | (1 << kk)][0]) % MO;
            f[j][k | (1 << kk)][0] =
                (f[j][k | (1 << kk)][0] + f[j + 1][k][1] * 10 % MO +
                 g[j + 1][k][1] * kk % MO) %
                MO;
          }
        }
      }
    for (int j = 0; j <= (1 << 10) - 1; ++j)
      if (num[j] <= ka) ans = ((ans + f[1][j][0]) % MO + f[1][j][1]) % MO;
  }
  return ans;
}
int main() {
  scanf("%lld%lld%d", &l, &r, &ka);
  for (int i = 0; i < (1 << 10); ++i) num[i] = num[i >> 1] + (i & 1);
  printf("%lld\n", (query(r) - query(l - 1) + MO) % MO);
  return 0;
}

```