#include <bits/stdc++.h>
using namespace std;
pair<int, int> dp[3][20][2 + (1 << 10)];
int arr[20];
long long powr[22];
pair<int, int> call(int cmp, int i, int mask, int k) {
  if (k < 0 || cmp == 2) return make_pair(0, 0);
  if (i < 0) {
    if (cmp > 0) return make_pair(0, 0);
    return make_pair(0, 1);
  }
  if (dp[cmp][i][mask].first != -1) return dp[cmp][i][mask];
  dp[cmp][i][mask].first = dp[cmp][i][mask].second = 0;
  int cmp1;
  pair<int, int> p;
  for (int j = 0; j < 10; j++) {
    long long dig = (j * powr[i]) % (998244353);
    if (j < arr[i])
      cmp1 = cmp * 0;
    else if (j == arr[i])
      cmp1 = cmp;
    else
      cmp1 = 2 * cmp;
    if ((mask & (1 << j)) != 0 || (j == 0 && mask == 0)) {
      p = call(cmp1, i - 1, mask, k);
    } else {
      p = call(cmp1, i - 1, mask | (1 << j), k - 1);
    }
    p.first += ((p.second * dig) % (998244353));
    if (p.first >= (998244353)) p.first -= (998244353);
    dp[cmp][i][mask].first += p.first;
    dp[cmp][i][mask].second += p.second;
    if (dp[cmp][i][mask].first >= (998244353))
      dp[cmp][i][mask].first -= (998244353);
    if (dp[cmp][i][mask].second >= (998244353))
      dp[cmp][i][mask].second -= (998244353);
  }
  return dp[cmp][i][mask];
}
int main() {
  long long l, r;
  int i, k, n, ans;
  powr[0] = 1;
  for (i = 1; i < 20; i++) powr[i] = (powr[i - 1] * 10) % (998244353);
  scanf("%lld %lld %d", &l, &r, &k);
  memset(dp, -1, sizeof dp);
  r++;
  for (i = 0; r > 0; i++) {
    arr[i] = r % 10;
    r /= 10;
  }
  n = i - 1;
  ans = call(1, n, 0, k).first;
  memset(dp, -1, sizeof dp);
  for (i = 0; l > 0; i++) {
    arr[i] = l % 10;
    l /= 10;
  }
  n = i - 1;
  ans -= call(1, n, 0, k).first;
  if (ans < 0) ans += (998244353);
  printf("%d\n", ans);
  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;
pair<int, int> dp[3][20][2 + (1 << 10)];
int arr[20];
long long powr[22];
pair<int, int> call(int cmp, int i, int mask, int k) {
  if (k < 0 || cmp == 2) return make_pair(0, 0);
  if (i < 0) {
    if (cmp > 0) return make_pair(0, 0);
    return make_pair(0, 1);
  }
  if (dp[cmp][i][mask].first != -1) return dp[cmp][i][mask];
  dp[cmp][i][mask].first = dp[cmp][i][mask].second = 0;
  int cmp1;
  pair<int, int> p;
  for (int j = 0; j < 10; j++) {
    long long dig = (j * powr[i]) % (998244353);
    if (j < arr[i])
      cmp1 = cmp * 0;
    else if (j == arr[i])
      cmp1 = cmp;
    else
      cmp1 = 2 * cmp;
    if ((mask & (1 << j)) != 0 || (j == 0 && mask == 0)) {
      p = call(cmp1, i - 1, mask, k);
    } else {
      p = call(cmp1, i - 1, mask | (1 << j), k - 1);
    }
    p.first += ((p.second * dig) % (998244353));
    if (p.first >= (998244353)) p.first -= (998244353);
    dp[cmp][i][mask].first += p.first;
    dp[cmp][i][mask].second += p.second;
    if (dp[cmp][i][mask].first >= (998244353))
      dp[cmp][i][mask].first -= (998244353);
    if (dp[cmp][i][mask].second >= (998244353))
      dp[cmp][i][mask].second -= (998244353);
  }
  return dp[cmp][i][mask];
}
int main() {
  long long l, r;
  int i, k, n, ans;
  powr[0] = 1;
  for (i = 1; i < 20; i++) powr[i] = (powr[i - 1] * 10) % (998244353);
  scanf("%lld %lld %d", &l, &r, &k);
  memset(dp, -1, sizeof dp);
  r++;
  for (i = 0; r > 0; i++) {
    arr[i] = r % 10;
    r /= 10;
  }
  n = i - 1;
  ans = call(1, n, 0, k).first;
  memset(dp, -1, sizeof dp);
  for (i = 0; l > 0; i++) {
    arr[i] = l % 10;
    l /= 10;
  }
  n = i - 1;
  ans -= call(1, n, 0, k).first;
  if (ans < 0) ans += (998244353);
  printf("%d\n", ans);
  return 0;
}

```