#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e12;
const int mod = 998244353;
int k;
pair<int, int> dp[20][1024];
int b[20], w;
int can[1024], p[30];
pair<int, int> dfs(int o, bool isTop, bool pre, int mask) {
  if (o < 0) return make_pair(can[mask], 0);
  if (!isTop && !pre && dp[o][mask].first != -1) return dp[o][mask];
  pair<int, int> ans;
  int tt = isTop ? b[o] : 9;
  for (int i = 0; i <= tt; ++i) {
    int nmask = mask;
    if (i || !pre) {
      nmask |= 1 << i;
    }
    pair<int, int> x = dfs(o - 1, isTop && i == tt, pre && !i, nmask);
    ans.first += x.first;
    if (ans.first >= mod) ans.first -= mod;
    ans.second += x.second;
    if (ans.second >= mod) ans.second -= mod;
    ans.second += 1LL * p[o] * i % mod * x.first % mod;
    if (ans.second >= mod) {
      ans.second -= mod;
    }
  }
  if (!isTop && !pre) {
    dp[o][mask] = ans;
  }
  return ans;
}
int cal(long long x) {
  w = 0;
  do {
    b[w++] = x % 10;
    x /= 10;
  } while (x);
  return dfs(w - 1, 1, 1, 0).second;
}
int main() {
  p[0] = 1;
  for (int i = 1; i < 29; ++i) {
    p[i] = 10LL * p[i - 1] % mod;
  }
  long long l, r;
  memset(dp, -1, sizeof(dp));
  scanf("%lld%lld%d", &l, &r, &k);
  for (int i = 0; i < 1024; ++i) {
    int cnt = 0;
    for (int j = 0; j < 10; ++j) {
      cnt += i >> j & 1;
    }
    can[i] = cnt <= k;
  }
  printf("%d\n", (cal(r) + mod - cal(l - 1)) % mod);
  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 long long inf = 1e12;
const int mod = 998244353;
int k;
pair<int, int> dp[20][1024];
int b[20], w;
int can[1024], p[30];
pair<int, int> dfs(int o, bool isTop, bool pre, int mask) {
  if (o < 0) return make_pair(can[mask], 0);
  if (!isTop && !pre && dp[o][mask].first != -1) return dp[o][mask];
  pair<int, int> ans;
  int tt = isTop ? b[o] : 9;
  for (int i = 0; i <= tt; ++i) {
    int nmask = mask;
    if (i || !pre) {
      nmask |= 1 << i;
    }
    pair<int, int> x = dfs(o - 1, isTop && i == tt, pre && !i, nmask);
    ans.first += x.first;
    if (ans.first >= mod) ans.first -= mod;
    ans.second += x.second;
    if (ans.second >= mod) ans.second -= mod;
    ans.second += 1LL * p[o] * i % mod * x.first % mod;
    if (ans.second >= mod) {
      ans.second -= mod;
    }
  }
  if (!isTop && !pre) {
    dp[o][mask] = ans;
  }
  return ans;
}
int cal(long long x) {
  w = 0;
  do {
    b[w++] = x % 10;
    x /= 10;
  } while (x);
  return dfs(w - 1, 1, 1, 0).second;
}
int main() {
  p[0] = 1;
  for (int i = 1; i < 29; ++i) {
    p[i] = 10LL * p[i - 1] % mod;
  }
  long long l, r;
  memset(dp, -1, sizeof(dp));
  scanf("%lld%lld%d", &l, &r, &k);
  for (int i = 0; i < 1024; ++i) {
    int cnt = 0;
    for (int j = 0; j < 10; ++j) {
      cnt += i >> j & 1;
    }
    can[i] = cnt <= k;
  }
  printf("%d\n", (cal(r) + mod - cal(l - 1)) % mod);
  return 0;
}

```