#include <bits/stdc++.h>
using namespace std;
const long long int mod = 998244353LL;
long long int dp[1050][20][3];
long long int ct[1050][20][3];
long long int l, r, k;
long long int dig[20];
long long int p10[20];
pair<long long int, long long int> get(long long int mask, long long int pos,
                                       long long int safe) {
  if (ct[mask][pos][safe] != -1)
    return {dp[mask][pos][safe], ct[mask][pos][safe]};
  long long int& rdp = dp[mask][pos][safe];
  long long int& cdp = ct[mask][pos][safe];
  rdp = cdp = 0;
  if (pos == 0) {
    long long int bc = __builtin_popcountll(mask);
    if (bc == 0 || bc > k) {
      rdp = cdp = 0;
      return {rdp, cdp};
    } else {
      rdp = 0;
      cdp = 1;
      return {rdp, cdp};
    }
  }
  for (long long int cd = 0; cd <= 9; ++cd) {
    if (!safe && cd > dig[pos]) continue;
    long long int nxsafe = 1;
    if (!safe && cd == dig[pos]) nxsafe = 0;
    long long int nxmask = mask;
    if (mask > 0 || cd) nxmask |= (1LL << cd);
    auto xp = get(nxmask, pos - 1, nxsafe);
    long long int val = xp.first, cnt = xp.second;
    cdp = (cdp + cnt) % mod;
    rdp = (rdp + val) % mod;
    rdp = (rdp + ((cnt * cd) % mod * p10[pos - 1]) % mod) % mod;
  }
  return {rdp, cdp};
}
long long int solve(long long int n) {
  if (n == 0) return 0;
  vector<long long int> cdig;
  while (n) {
    cdig.push_back(n % 10);
    n /= 10;
  }
  while (cdig.size() < 18) cdig.push_back(0);
  for (long long int i = 1; i <= 18; ++i) {
    dig[i] = cdig[i - 1];
  }
  for (long long int i = 0; i <= 18; ++i) {
    for (long long int mask = 0; mask <= 1025; ++mask)
      for (long long int safe = 0; safe <= 1; ++safe) {
        ct[mask][i][safe] = -1;
      }
  }
  return get(0, 18, 0).first;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  p10[0] = 1;
  for (long long int i = 1; i <= 18; ++i) {
    p10[i] = (p10[i - 1] * 10LL) % mod;
  }
  cin >> l >> r >> k;
  cout << ((solve(r) - solve(l - 1)) % mod + mod) % mod << '\n';
}

### Prompt

Your task is to create a CPP solution 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 long long int mod = 998244353LL;
long long int dp[1050][20][3];
long long int ct[1050][20][3];
long long int l, r, k;
long long int dig[20];
long long int p10[20];
pair<long long int, long long int> get(long long int mask, long long int pos,
                                       long long int safe) {
  if (ct[mask][pos][safe] != -1)
    return {dp[mask][pos][safe], ct[mask][pos][safe]};
  long long int& rdp = dp[mask][pos][safe];
  long long int& cdp = ct[mask][pos][safe];
  rdp = cdp = 0;
  if (pos == 0) {
    long long int bc = __builtin_popcountll(mask);
    if (bc == 0 || bc > k) {
      rdp = cdp = 0;
      return {rdp, cdp};
    } else {
      rdp = 0;
      cdp = 1;
      return {rdp, cdp};
    }
  }
  for (long long int cd = 0; cd <= 9; ++cd) {
    if (!safe && cd > dig[pos]) continue;
    long long int nxsafe = 1;
    if (!safe && cd == dig[pos]) nxsafe = 0;
    long long int nxmask = mask;
    if (mask > 0 || cd) nxmask |= (1LL << cd);
    auto xp = get(nxmask, pos - 1, nxsafe);
    long long int val = xp.first, cnt = xp.second;
    cdp = (cdp + cnt) % mod;
    rdp = (rdp + val) % mod;
    rdp = (rdp + ((cnt * cd) % mod * p10[pos - 1]) % mod) % mod;
  }
  return {rdp, cdp};
}
long long int solve(long long int n) {
  if (n == 0) return 0;
  vector<long long int> cdig;
  while (n) {
    cdig.push_back(n % 10);
    n /= 10;
  }
  while (cdig.size() < 18) cdig.push_back(0);
  for (long long int i = 1; i <= 18; ++i) {
    dig[i] = cdig[i - 1];
  }
  for (long long int i = 0; i <= 18; ++i) {
    for (long long int mask = 0; mask <= 1025; ++mask)
      for (long long int safe = 0; safe <= 1; ++safe) {
        ct[mask][i][safe] = -1;
      }
  }
  return get(0, 18, 0).first;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  p10[0] = 1;
  for (long long int i = 1; i <= 18; ++i) {
    p10[i] = (p10[i - 1] * 10LL) % mod;
  }
  cin >> l >> r >> k;
  cout << ((solve(r) - solve(l - 1)) % mod + mod) % mod << '\n';
}

```