#include <bits/stdc++.h>
using namespace std;
const int INF = 1000 * 1000 * 1000 + 47;
const long long LINF = (long long)INF * INF;
const int MAX = 2e5;
const int MOD = 998244353;
const double EPS = 1e-9;
const double PI = acos(-1.);
long long l, r;
int k;
pair<int, int> dpT[1 << 10][18][2][2];
int a[18];
long long power[18];
const int MAXA = 18;
pair<int, int> dp(int mask, int pos, int less, int was) {
  if (__builtin_popcount(mask) > k) return make_pair(0, 0);
  if (pos == MAXA) return make_pair(0, 1);
  if (dpT[mask][pos][less][was] != make_pair(-1, -1))
    return dpT[mask][pos][less][was];
  pair<int, int> ret = make_pair(0, 0);
  if (less) {
    for (int i = (0); i < (10); ++i) {
      int xx = 1;
      int yy = 1 << i;
      if (was == 0 && i == 0) {
        xx = 0;
        yy = 0;
      }
      ret.first += ((1LL * i * power[pos] % MOD) *
                    dp(mask | yy, pos + 1, less, xx).second) %
                   MOD;
      ret.first %= MOD;
      ret.first += dp(mask | yy, pos + 1, less, xx).first;
      ret.first %= MOD;
      ret.second += dp(mask | yy, pos + 1, less, xx).second;
      ret.second %= MOD;
    }
  } else {
    for (int i = (0); i < (a[pos]); ++i) {
      int xx = 1;
      int yy = 1 << i;
      if (was == 0 && i == 0) {
        xx = 0;
        yy = 0;
      }
      ret.first += ((1LL * i * power[pos] % MOD) *
                    dp(mask | yy, pos + 1, 1, xx).second) %
                   MOD;
      ret.first %= MOD;
      ret.first += dp(mask | yy, pos + 1, 1, xx).first;
      ret.first %= MOD;
      ret.second += dp(mask | yy, pos + 1, 1, xx).second;
      ret.second %= MOD;
    }
    int xx = 1;
    int yy = 1 << a[pos];
    if (was == 0 && a[pos] == 0) {
      xx = 0;
      yy = 0;
    }
    ret.first += ((1LL * a[pos] * power[pos] % MOD) *
                  dp(mask | yy, pos + 1, 0, xx).second) %
                 MOD;
    ret.first %= MOD;
    ret.first += dp(mask | yy, pos + 1, 0, xx).first;
    ret.first %= MOD;
    ret.second += dp(mask | yy, pos + 1, 0, xx).second;
    ret.second %= MOD;
  }
  return dpT[mask][pos][less][was] = ret;
}
int main() {
  ios_base::sync_with_stdio(0);
  power[MAXA - 1] = 1;
  for (int i = (MAXA - 1) - 1; i >= (0); --i) {
    power[i] = power[i + 1] * 10;
    power[i] %= MOD;
  }
  cin >> l >> r >> k;
  long long ans = 0;
  long long x;
  memset(dpT, -1, sizeof(dpT));
  memset(a, 0, sizeof(a));
  x = r;
  int pos = MAXA - 1;
  while (x) {
    a[pos] = x % 10;
    x /= 10;
    pos--;
  }
  ans += dp(0, 0, 0, 0).first;
  memset(dpT, -1, sizeof(dpT));
  memset(a, 0, sizeof(a));
  x = l - 1;
  pos = MAXA - 1;
  while (x) {
    a[pos] = x % 10;
    x /= 10;
    pos--;
  }
  ans -= dp(0, 0, 0, 0).first;
  ans %= MOD;
  if (ans < 0) {
    ans += MOD;
  }
  ans %= MOD;
  cout << ans << endl;
}

### Prompt

Please create a solution in CPP 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 INF = 1000 * 1000 * 1000 + 47;
const long long LINF = (long long)INF * INF;
const int MAX = 2e5;
const int MOD = 998244353;
const double EPS = 1e-9;
const double PI = acos(-1.);
long long l, r;
int k;
pair<int, int> dpT[1 << 10][18][2][2];
int a[18];
long long power[18];
const int MAXA = 18;
pair<int, int> dp(int mask, int pos, int less, int was) {
  if (__builtin_popcount(mask) > k) return make_pair(0, 0);
  if (pos == MAXA) return make_pair(0, 1);
  if (dpT[mask][pos][less][was] != make_pair(-1, -1))
    return dpT[mask][pos][less][was];
  pair<int, int> ret = make_pair(0, 0);
  if (less) {
    for (int i = (0); i < (10); ++i) {
      int xx = 1;
      int yy = 1 << i;
      if (was == 0 && i == 0) {
        xx = 0;
        yy = 0;
      }
      ret.first += ((1LL * i * power[pos] % MOD) *
                    dp(mask | yy, pos + 1, less, xx).second) %
                   MOD;
      ret.first %= MOD;
      ret.first += dp(mask | yy, pos + 1, less, xx).first;
      ret.first %= MOD;
      ret.second += dp(mask | yy, pos + 1, less, xx).second;
      ret.second %= MOD;
    }
  } else {
    for (int i = (0); i < (a[pos]); ++i) {
      int xx = 1;
      int yy = 1 << i;
      if (was == 0 && i == 0) {
        xx = 0;
        yy = 0;
      }
      ret.first += ((1LL * i * power[pos] % MOD) *
                    dp(mask | yy, pos + 1, 1, xx).second) %
                   MOD;
      ret.first %= MOD;
      ret.first += dp(mask | yy, pos + 1, 1, xx).first;
      ret.first %= MOD;
      ret.second += dp(mask | yy, pos + 1, 1, xx).second;
      ret.second %= MOD;
    }
    int xx = 1;
    int yy = 1 << a[pos];
    if (was == 0 && a[pos] == 0) {
      xx = 0;
      yy = 0;
    }
    ret.first += ((1LL * a[pos] * power[pos] % MOD) *
                  dp(mask | yy, pos + 1, 0, xx).second) %
                 MOD;
    ret.first %= MOD;
    ret.first += dp(mask | yy, pos + 1, 0, xx).first;
    ret.first %= MOD;
    ret.second += dp(mask | yy, pos + 1, 0, xx).second;
    ret.second %= MOD;
  }
  return dpT[mask][pos][less][was] = ret;
}
int main() {
  ios_base::sync_with_stdio(0);
  power[MAXA - 1] = 1;
  for (int i = (MAXA - 1) - 1; i >= (0); --i) {
    power[i] = power[i + 1] * 10;
    power[i] %= MOD;
  }
  cin >> l >> r >> k;
  long long ans = 0;
  long long x;
  memset(dpT, -1, sizeof(dpT));
  memset(a, 0, sizeof(a));
  x = r;
  int pos = MAXA - 1;
  while (x) {
    a[pos] = x % 10;
    x /= 10;
    pos--;
  }
  ans += dp(0, 0, 0, 0).first;
  memset(dpT, -1, sizeof(dpT));
  memset(a, 0, sizeof(a));
  x = l - 1;
  pos = MAXA - 1;
  while (x) {
    a[pos] = x % 10;
    x /= 10;
    pos--;
  }
  ans -= dp(0, 0, 0, 0).first;
  ans %= MOD;
  if (ans < 0) {
    ans += MOD;
  }
  ans %= MOD;
  cout << ans << endl;
}

```