#include <bits/stdc++.h>
using namespace std;
string a, b, c;
int k;
long long T[20];
pair<long long, long long> dp[20][2][2][2][1030];
bool vis[20][2][2][2][1030];
pair<long long, long long> solve(int pos, int choto, int boro, int shuru,
                                 int mask, long long sum) {
  int cnt = __builtin_popcount(mask);
  if (pos == b.size()) return {0, 1};
  pair<long long, long long> &ret = dp[pos][choto][boro][shuru][mask];
  if (vis[pos][choto][boro][shuru][mask]) return ret;
  int lo = 0, hi = 9;
  if (!choto) hi = b[pos] - '0';
  if (!boro) lo = a[pos] - '0';
  pair<long long, long long> rt;
  long long s = 0, way = 0;
  for (int i = lo; i <= hi; i++) {
    if ((mask & (1 << i)) || cnt < k) {
      rt = solve(pos + 1, choto | (i < hi), boro | (i > lo), shuru | (i > 0),
                 (shuru || i > 0) ? mask | (1 << i) : mask,
                 ((sum * 10) + i) % 998244353);
      s += (T[b.size() - pos - 1] * i * rt.second) % 998244353 + rt.first;
      s %= 998244353;
      way += rt.second;
      way %= 998244353;
    }
  }
  vis[pos][choto][boro][shuru][mask] = true;
  return ret = {s, way};
}
int main() {
  T[0] = 1;
  for (int i = 1; i < 20; i++) T[i] = (T[i - 1] * 10) % 998244353;
  cin >> a >> b >> k;
  for (int i = 0; i < b.size() - a.size(); i++) c += '0';
  a = c + a;
  memset(vis, false, sizeof(vis));
  cout << solve(0, 0, 0, 0, 0, 0).first << endl;
  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;
string a, b, c;
int k;
long long T[20];
pair<long long, long long> dp[20][2][2][2][1030];
bool vis[20][2][2][2][1030];
pair<long long, long long> solve(int pos, int choto, int boro, int shuru,
                                 int mask, long long sum) {
  int cnt = __builtin_popcount(mask);
  if (pos == b.size()) return {0, 1};
  pair<long long, long long> &ret = dp[pos][choto][boro][shuru][mask];
  if (vis[pos][choto][boro][shuru][mask]) return ret;
  int lo = 0, hi = 9;
  if (!choto) hi = b[pos] - '0';
  if (!boro) lo = a[pos] - '0';
  pair<long long, long long> rt;
  long long s = 0, way = 0;
  for (int i = lo; i <= hi; i++) {
    if ((mask & (1 << i)) || cnt < k) {
      rt = solve(pos + 1, choto | (i < hi), boro | (i > lo), shuru | (i > 0),
                 (shuru || i > 0) ? mask | (1 << i) : mask,
                 ((sum * 10) + i) % 998244353);
      s += (T[b.size() - pos - 1] * i * rt.second) % 998244353 + rt.first;
      s %= 998244353;
      way += rt.second;
      way %= 998244353;
    }
  }
  vis[pos][choto][boro][shuru][mask] = true;
  return ret = {s, way};
}
int main() {
  T[0] = 1;
  for (int i = 1; i < 20; i++) T[i] = (T[i - 1] * 10) % 998244353;
  cin >> a >> b >> k;
  for (int i = 0; i < b.size() - a.size(); i++) c += '0';
  a = c + a;
  memset(vis, false, sizeof(vis));
  cout << solve(0, 0, 0, 0, 0, 0).first << endl;
  return 0;
}

```