#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int mod = 998244353;
int power(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1) {
      res = 1LL * res * a % mod;
    }
    a = 1LL * a * a % mod;
    b >>= 1;
  }
  return res;
}
long long pw[22], dig[22];
pair<long long int, long long int> dp[22][1 << 10];
bool mem[22][1 << 10];
pair<long long int, long long int> fun(int idx, int mask, int k) {
  if (k < 0) return {0, 0};
  pair<long long int, long long int> &ret = dp[idx][mask];
  if (mem[idx][mask]) return ret;
  mem[idx][mask] = 1;
  if (idx == 0) {
    if (k >= 0) return ret = {0, 1};
    return ret = {0, 0};
  }
  ret = {0, 0};
  for (int i = 0; i <= 9; i++) {
    ret.first +=
        1LL * i * pw[idx - 1] % mod *
        fun(idx - 1, mask | (1 << i), k - (mask & (1 << i) ? 0 : 1)).second %
        mod;
    ret.first %= mod;
    ret.first +=
        fun(idx - 1, mask | (1 << i), k - (mask & (1 << i) ? 0 : 1)).first;
    ret.first %= mod;
    ret.second +=
        fun(idx - 1, mask | (1 << i), k - (mask & (1 << i) ? 0 : 1)).second;
    ret.second %= mod;
  }
  return ret;
}
long long find(long long num, int k) {
  if (num == 0) return 0;
  long long td = 0, ans = 0, val = num % mod;
  long long mask = 0, tot = k;
  while (num) {
    dig[++td] = num % 10;
    num /= 10;
  }
  for (int i = 1; i <= td - 1; i++) {
    for (int j = 1; j <= 9; j++) {
      ans +=
          1LL * j * pw[i - 1] % mod * fun(i - 1, 1 << j, tot - 1).second % mod;
      ans %= mod;
      ans += fun(i - 1, 1 << j, tot - 1).first;
      ans %= mod;
    }
  }
  long long sum = 0;
  for (int i = td; i >= 1; i--) {
    int j = (i == td ? 1 : 0);
    for (; j < dig[i]; j++) {
      ans +=
          1LL * (sum + 1LL * j * pw[i - 1] % mod) % mod *
          fun(i - 1, mask | (1 << j), tot - (mask & (1 << j) ? 0 : 1)).second %
          mod;
      ans %= mod;
      ans += fun(i - 1, mask | (1 << j), tot - (mask & (1 << j) ? 0 : 1)).first;
    }
    sum += 1LL * dig[i] * pw[i - 1] % mod;
    sum %= mod;
    if (mask & (1 << dig[i])) {
      continue;
    } else {
      mask |= (1 << dig[i]);
      tot--;
    }
  }
  if (tot >= 0) ans += val;
  ans %= mod;
  return ans;
}
int main() {
  long long l, r;
  int k;
  pw[0] = 1;
  for (int i = 1; i <= 20; i++) {
    pw[i] = 1LL * pw[i - 1] * 10 % mod;
  }
  scanf("%lld %lld %d", &l, &r, &k);
  l--;
  printf("%d\n", (find(r, k) + mod - find(l, k)) % mod);
  return 0;
}

### Prompt

Your challenge is to write 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 namespace std;
const int N = 2e5 + 10;
const int mod = 998244353;
int power(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1) {
      res = 1LL * res * a % mod;
    }
    a = 1LL * a * a % mod;
    b >>= 1;
  }
  return res;
}
long long pw[22], dig[22];
pair<long long int, long long int> dp[22][1 << 10];
bool mem[22][1 << 10];
pair<long long int, long long int> fun(int idx, int mask, int k) {
  if (k < 0) return {0, 0};
  pair<long long int, long long int> &ret = dp[idx][mask];
  if (mem[idx][mask]) return ret;
  mem[idx][mask] = 1;
  if (idx == 0) {
    if (k >= 0) return ret = {0, 1};
    return ret = {0, 0};
  }
  ret = {0, 0};
  for (int i = 0; i <= 9; i++) {
    ret.first +=
        1LL * i * pw[idx - 1] % mod *
        fun(idx - 1, mask | (1 << i), k - (mask & (1 << i) ? 0 : 1)).second %
        mod;
    ret.first %= mod;
    ret.first +=
        fun(idx - 1, mask | (1 << i), k - (mask & (1 << i) ? 0 : 1)).first;
    ret.first %= mod;
    ret.second +=
        fun(idx - 1, mask | (1 << i), k - (mask & (1 << i) ? 0 : 1)).second;
    ret.second %= mod;
  }
  return ret;
}
long long find(long long num, int k) {
  if (num == 0) return 0;
  long long td = 0, ans = 0, val = num % mod;
  long long mask = 0, tot = k;
  while (num) {
    dig[++td] = num % 10;
    num /= 10;
  }
  for (int i = 1; i <= td - 1; i++) {
    for (int j = 1; j <= 9; j++) {
      ans +=
          1LL * j * pw[i - 1] % mod * fun(i - 1, 1 << j, tot - 1).second % mod;
      ans %= mod;
      ans += fun(i - 1, 1 << j, tot - 1).first;
      ans %= mod;
    }
  }
  long long sum = 0;
  for (int i = td; i >= 1; i--) {
    int j = (i == td ? 1 : 0);
    for (; j < dig[i]; j++) {
      ans +=
          1LL * (sum + 1LL * j * pw[i - 1] % mod) % mod *
          fun(i - 1, mask | (1 << j), tot - (mask & (1 << j) ? 0 : 1)).second %
          mod;
      ans %= mod;
      ans += fun(i - 1, mask | (1 << j), tot - (mask & (1 << j) ? 0 : 1)).first;
    }
    sum += 1LL * dig[i] * pw[i - 1] % mod;
    sum %= mod;
    if (mask & (1 << dig[i])) {
      continue;
    } else {
      mask |= (1 << dig[i]);
      tot--;
    }
  }
  if (tot >= 0) ans += val;
  ans %= mod;
  return ans;
}
int main() {
  long long l, r;
  int k;
  pw[0] = 1;
  for (int i = 1; i <= 20; i++) {
    pw[i] = 1LL * pw[i - 1] * 10 % mod;
  }
  scanf("%lld %lld %d", &l, &r, &k);
  l--;
  printf("%d\n", (find(r, k) + mod - find(l, k)) % mod);
  return 0;
}

```