#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
const long long mod = 998244353;
long long l, r;
int k;
long long dp[21][11][1 << 10], dp2[21][11][1 << 10];
int f[1 << 10];
long long play(long long x) {
  if (x == 0) return 0;
  if (x < 10) return x * (x + 1) / 2;
  int i;
  long long now = 1, ans = 0, w = 0, num = 1, w2 = 0;
  while (now * 10 <= x) {
    for (i = 1; i <= 9; i++) {
      for (int j = 0; j < 1 << 10; j++)
        if (f[j] <= k) ans += dp2[num][i][j];
    }
    num++;
    now *= 10;
  }
  ans %= mod;
  for (int i = 0; i < (1 << 10); i++)
    if (f[i] <= k) ans -= dp2[num][0][i];
  while (now) {
    for (i = 0;; i++) {
      if (now != 1) {
        if ((i + 1) * now > x) break;
      } else if (i > x)
        break;
      for (int j = 0; j < 1 << 10; j++)
        if (f[j | w] <= k) {
          ans += dp2[num][i][j] + dp[num][i][j] * (w2 % mod);
          ans %= mod;
        }
    }
    x %= now;
    w |= 1 << i;
    w2 += i * now;
    num--;
    now /= 10;
  }
  return ans;
}
int main() {
  scanf("%lld%lld%d", &l, &r, &k);
  int i, j, k, a, b;
  memset(dp2, 0, sizeof(dp2));
  dp[0][10][0] = 1;
  dp2[0][10][0] = 0;
  for (i = 0; i < 1 << 10; i++) {
    a = 0;
    for (j = 0; j < 10; j++)
      if (i & (1 << j)) a++;
    f[i] = a;
  }
  long long qaq = 1;
  for (i = 1; i <= 18; i++) {
    for (j = 0; j < 10; j++) {
      for (k = 0; k < (1 << 10); k++) {
        if (dp[i - 1][10][k] == 0) continue;
        dp[i][j][k | 1 << j] += dp[i - 1][10][k];
        dp[i][j][k | 1 << j] %= mod;
        dp2[i][j][k | 1 << j] +=
            dp2[i - 1][10][k] + qaq % mod * j % mod * dp[i - 1][10][k];
        dp2[i][j][k | 1 << j] %= mod;
        dp[i][10][k | 1 << j] += dp[i - 1][10][k];
        dp[i][10][k | 1 << j] %= mod;
        dp2[i][10][k | 1 << j] +=
            dp2[i - 1][10][k] + qaq % mod * j % mod * dp[i - 1][10][k];
        dp2[i][10][k | 1 << j] %= mod;
      }
    }
    qaq *= 10;
  }
  long long ans = play(r) - play(l - 1);
  printf("%lld\n", (ans % mod + mod) % mod);
}

### Prompt

Create a solution in CPP for 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 namespace std;
const int maxn = 2e5 + 5;
const long long mod = 998244353;
long long l, r;
int k;
long long dp[21][11][1 << 10], dp2[21][11][1 << 10];
int f[1 << 10];
long long play(long long x) {
  if (x == 0) return 0;
  if (x < 10) return x * (x + 1) / 2;
  int i;
  long long now = 1, ans = 0, w = 0, num = 1, w2 = 0;
  while (now * 10 <= x) {
    for (i = 1; i <= 9; i++) {
      for (int j = 0; j < 1 << 10; j++)
        if (f[j] <= k) ans += dp2[num][i][j];
    }
    num++;
    now *= 10;
  }
  ans %= mod;
  for (int i = 0; i < (1 << 10); i++)
    if (f[i] <= k) ans -= dp2[num][0][i];
  while (now) {
    for (i = 0;; i++) {
      if (now != 1) {
        if ((i + 1) * now > x) break;
      } else if (i > x)
        break;
      for (int j = 0; j < 1 << 10; j++)
        if (f[j | w] <= k) {
          ans += dp2[num][i][j] + dp[num][i][j] * (w2 % mod);
          ans %= mod;
        }
    }
    x %= now;
    w |= 1 << i;
    w2 += i * now;
    num--;
    now /= 10;
  }
  return ans;
}
int main() {
  scanf("%lld%lld%d", &l, &r, &k);
  int i, j, k, a, b;
  memset(dp2, 0, sizeof(dp2));
  dp[0][10][0] = 1;
  dp2[0][10][0] = 0;
  for (i = 0; i < 1 << 10; i++) {
    a = 0;
    for (j = 0; j < 10; j++)
      if (i & (1 << j)) a++;
    f[i] = a;
  }
  long long qaq = 1;
  for (i = 1; i <= 18; i++) {
    for (j = 0; j < 10; j++) {
      for (k = 0; k < (1 << 10); k++) {
        if (dp[i - 1][10][k] == 0) continue;
        dp[i][j][k | 1 << j] += dp[i - 1][10][k];
        dp[i][j][k | 1 << j] %= mod;
        dp2[i][j][k | 1 << j] +=
            dp2[i - 1][10][k] + qaq % mod * j % mod * dp[i - 1][10][k];
        dp2[i][j][k | 1 << j] %= mod;
        dp[i][10][k | 1 << j] += dp[i - 1][10][k];
        dp[i][10][k | 1 << j] %= mod;
        dp2[i][10][k | 1 << j] +=
            dp2[i - 1][10][k] + qaq % mod * j % mod * dp[i - 1][10][k];
        dp2[i][10][k | 1 << j] %= mod;
      }
    }
    qaq *= 10;
  }
  long long ans = play(r) - play(l - 1);
  printf("%lld\n", (ans % mod + mod) % mod);
}

```