#include <bits/stdc++.h>
using namespace std;
template <typename T>
string to_string(const vector<T>& vc, int w) {
  if (vc.empty()) return "";
  if (w + 1 == vc.size()) return to_string(vc[w]);
  return to_string(vc[w]) + "," + to_string(vc, w + 1);
}
template <typename T>
string to_string(const vector<T>& vc) {
  return "{" + to_string(vc, 0) + "}";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
class DebugStream {
} LOG;
template <typename T>
DebugStream& operator<<(DebugStream& s, const T&) {
  return s;
}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e5 + 9, maxK = 12, MOD = 998244353, SQ = 335, lg = 20,
          bs = 10;
const int len = 20;
long long pot[len], frq[len][1 << bs], dp[len][1 << bs], edg[len][1 << bs], l,
    r;
int card[1 << bs], k;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> l >> r >> k;
  r++;
  for (int i = 1; i < (1 << bs); i++) card[i] = card[i - (i & -i)] + 1;
  pot[0] = 1;
  for (int i = 1; i < len; i++) pot[i] = pot[i - 1] * bs % MOD;
  frq[0][0] = 1;
  for (int i = 1; i < len; i++) {
    for (int j = 1; j < (1 << bs); j++) {
      for (int r = 0; r < bs; r++) {
        if (!(1 << r & j)) continue;
        frq[i][j] = (frq[i][j] + frq[i - 1][j] + frq[i - 1][1 << r ^ j]) % MOD;
        long long cur = (frq[i - 1][j] + frq[i - 1][1 << r ^ j]) * r % MOD *
                        pot[i - 1] % MOD;
        long long xx = (dp[i - 1][j] + dp[i - 1][1 << r ^ j] + cur) % MOD;
        dp[i][j] = (dp[i][j] + xx) % MOD;
        if (r) edg[i][j] = (edg[i][j] + xx) % MOD;
      }
    }
  }
  auto fn = [&](long long x) {
    string st = to_string(x);
    reverse(st.begin(), st.end());
    long long ret = 0, pref = 0;
    int bm = 0;
    for (int i = int(st.size()) - 1; i >= 0; i--) {
      for (int j = 0; j < st[i] - '0'; j++) {
        long long cpf = pref * bs + j;
        if (i + 1 == st.size() && !j) continue;
        for (int ot = 0; ot < (1 << bs); ot++) {
          int cbm = 1 << j | bm | ot;
          if (card[cbm] > k) continue;
          ret = (ret + dp[i][ot]) % MOD;
          ret = (ret + pot[i] * cpf % MOD * frq[i][ot]) % MOD;
        }
      }
      bm |= 1 << (st[i] - '0');
      pref = pref * bs + st[i] - '0';
    }
    42;
    for (int i = 1; i < st.size(); i++)
      for (int j = 0; j < (1 << bs); j++)
        if (card[j] <= k) ret = (ret + edg[i][j]) % MOD;
    return ret;
  };
  long long ans = (MOD + fn(r) - fn(l)) % MOD;
  cout << ans << '\n';
}

### 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;
template <typename T>
string to_string(const vector<T>& vc, int w) {
  if (vc.empty()) return "";
  if (w + 1 == vc.size()) return to_string(vc[w]);
  return to_string(vc[w]) + "," + to_string(vc, w + 1);
}
template <typename T>
string to_string(const vector<T>& vc) {
  return "{" + to_string(vc, 0) + "}";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
class DebugStream {
} LOG;
template <typename T>
DebugStream& operator<<(DebugStream& s, const T&) {
  return s;
}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e5 + 9, maxK = 12, MOD = 998244353, SQ = 335, lg = 20,
          bs = 10;
const int len = 20;
long long pot[len], frq[len][1 << bs], dp[len][1 << bs], edg[len][1 << bs], l,
    r;
int card[1 << bs], k;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> l >> r >> k;
  r++;
  for (int i = 1; i < (1 << bs); i++) card[i] = card[i - (i & -i)] + 1;
  pot[0] = 1;
  for (int i = 1; i < len; i++) pot[i] = pot[i - 1] * bs % MOD;
  frq[0][0] = 1;
  for (int i = 1; i < len; i++) {
    for (int j = 1; j < (1 << bs); j++) {
      for (int r = 0; r < bs; r++) {
        if (!(1 << r & j)) continue;
        frq[i][j] = (frq[i][j] + frq[i - 1][j] + frq[i - 1][1 << r ^ j]) % MOD;
        long long cur = (frq[i - 1][j] + frq[i - 1][1 << r ^ j]) * r % MOD *
                        pot[i - 1] % MOD;
        long long xx = (dp[i - 1][j] + dp[i - 1][1 << r ^ j] + cur) % MOD;
        dp[i][j] = (dp[i][j] + xx) % MOD;
        if (r) edg[i][j] = (edg[i][j] + xx) % MOD;
      }
    }
  }
  auto fn = [&](long long x) {
    string st = to_string(x);
    reverse(st.begin(), st.end());
    long long ret = 0, pref = 0;
    int bm = 0;
    for (int i = int(st.size()) - 1; i >= 0; i--) {
      for (int j = 0; j < st[i] - '0'; j++) {
        long long cpf = pref * bs + j;
        if (i + 1 == st.size() && !j) continue;
        for (int ot = 0; ot < (1 << bs); ot++) {
          int cbm = 1 << j | bm | ot;
          if (card[cbm] > k) continue;
          ret = (ret + dp[i][ot]) % MOD;
          ret = (ret + pot[i] * cpf % MOD * frq[i][ot]) % MOD;
        }
      }
      bm |= 1 << (st[i] - '0');
      pref = pref * bs + st[i] - '0';
    }
    42;
    for (int i = 1; i < st.size(); i++)
      for (int j = 0; j < (1 << bs); j++)
        if (card[j] <= k) ret = (ret + edg[i][j]) % MOD;
    return ret;
  };
  long long ans = (MOD + fn(r) - fn(l)) % MOD;
  cout << ans << '\n';
}

```