#include <bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr int N = 1e5 + 5;
constexpr int MOD = 998244353;
constexpr int INF = 1e9;
int k;
LL p10[20];
LL cache1[20][2][1050];
int cache[20][2][1050];
vector<int> num;
int SZ;
LL check(int pos, int smaller, int mask) {
  if (mask == 1) mask = 0;
  if (pos == SZ) {
    return __builtin_popcount(mask) <= k;
  }
  LL &v = cache1[pos][smaller][mask];
  if (v != -1) return v;
  v = 0;
  if (smaller) {
    for (int i = 0; i <= 9; i++) {
      v += check(pos + 1, 1, mask | (1 << i));
      v %= MOD;
    }
  } else {
    for (int i = 0; i <= num[pos]; i++) {
      v += check(pos + 1, i < num[pos], mask | (1 << i));
      v %= MOD;
    }
  }
  return v;
}
int dp(int pos, int smaller, int mask) {
  if (mask == 1) mask = 0;
  if (pos == SZ) {
    return 0;
  }
  int &rv = cache[pos][smaller][mask];
  if (~rv) return rv;
  rv = 0;
  if (smaller) {
    for (int i = 0; i <= 9; i++) {
      rv += (check(pos + 1, 1, mask | (1 << i)) * i * 1LL * p10[SZ - pos - 1] +
             dp(pos + 1, 1, mask | (1 << i))) %
            MOD;
      rv %= MOD;
    }
  } else {
    for (int i = 0; i <= num[pos]; i++) {
      rv += (check(pos + 1, i < num[pos], mask | (1 << i)) * i * 1LL *
                 p10[SZ - pos - 1] +
             dp(pos + 1, i < num[pos], mask | (1 << i))) %
            MOD;
      rv %= MOD;
    }
  }
  return rv;
}
int solve(LL val) {
  num.clear();
  while (val) {
    num.push_back(val % 10);
    val /= 10;
  }
  reverse(begin(num), end(num));
  SZ = num.size();
  memset(cache1, -1, sizeof cache1);
  memset(cache, -1, sizeof cache);
  return dp(0, 0, 0);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  p10[0] = 1;
  for (int i = 1; i < 20; i++) {
    p10[i] = p10[i - 1] * 10 % MOD;
  }
  LL L, R;
  cin >> L >> R >> k;
  int res = solve(R);
  res = (res + MOD - solve(L - 1)) % MOD;
  cout << res << 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;
using LL = long long;
constexpr int N = 1e5 + 5;
constexpr int MOD = 998244353;
constexpr int INF = 1e9;
int k;
LL p10[20];
LL cache1[20][2][1050];
int cache[20][2][1050];
vector<int> num;
int SZ;
LL check(int pos, int smaller, int mask) {
  if (mask == 1) mask = 0;
  if (pos == SZ) {
    return __builtin_popcount(mask) <= k;
  }
  LL &v = cache1[pos][smaller][mask];
  if (v != -1) return v;
  v = 0;
  if (smaller) {
    for (int i = 0; i <= 9; i++) {
      v += check(pos + 1, 1, mask | (1 << i));
      v %= MOD;
    }
  } else {
    for (int i = 0; i <= num[pos]; i++) {
      v += check(pos + 1, i < num[pos], mask | (1 << i));
      v %= MOD;
    }
  }
  return v;
}
int dp(int pos, int smaller, int mask) {
  if (mask == 1) mask = 0;
  if (pos == SZ) {
    return 0;
  }
  int &rv = cache[pos][smaller][mask];
  if (~rv) return rv;
  rv = 0;
  if (smaller) {
    for (int i = 0; i <= 9; i++) {
      rv += (check(pos + 1, 1, mask | (1 << i)) * i * 1LL * p10[SZ - pos - 1] +
             dp(pos + 1, 1, mask | (1 << i))) %
            MOD;
      rv %= MOD;
    }
  } else {
    for (int i = 0; i <= num[pos]; i++) {
      rv += (check(pos + 1, i < num[pos], mask | (1 << i)) * i * 1LL *
                 p10[SZ - pos - 1] +
             dp(pos + 1, i < num[pos], mask | (1 << i))) %
            MOD;
      rv %= MOD;
    }
  }
  return rv;
}
int solve(LL val) {
  num.clear();
  while (val) {
    num.push_back(val % 10);
    val /= 10;
  }
  reverse(begin(num), end(num));
  SZ = num.size();
  memset(cache1, -1, sizeof cache1);
  memset(cache, -1, sizeof cache);
  return dp(0, 0, 0);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  p10[0] = 1;
  for (int i = 1; i < 20; i++) {
    p10[i] = p10[i - 1] * 10 % MOD;
  }
  LL L, R;
  cin >> L >> R >> k;
  int res = solve(R);
  res = (res + MOD - solve(L - 1)) % MOD;
  cout << res << endl;
}

```