#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
long long dp[20][1024][2], ways[20][1024][2], p10[20], l, r, k, digs, num;
long long solve(int cur, int mask, int same) {
  if (dp[cur][mask][same] != -1) return dp[cur][mask][same];
  if (cur == digs + 1) {
    ways[cur][mask][same] = 1;
    return 0;
  }
  long long sum = 0, bound = 9, tways = 0;
  if (same) bound = num / (long long)pow(10, digs - cur) % 10;
  for (long long i = 0; i <= bound; i++) {
    if (__builtin_popcount(mask | (1 << i)) > k) continue;
    int p = same, nmask = mask;
    if (!(mask == 0 && i == 0)) nmask |= 1 << i;
    if (same && i < bound) p = 0;
    sum = (sum + solve(cur + 1, nmask, p)) % mod;
    sum = (sum + p10[digs - cur] * i * ways[cur + 1][nmask][p]) % mod;
    tways = (tways + ways[cur + 1][nmask][p]) % mod;
  }
  ways[cur][mask][same] = tways;
  return dp[cur][mask][same] = sum;
}
long long calc(long long to) {
  if (to == 0) return 0;
  digs = log10(to), num = to;
  memset(dp, -1, sizeof dp);
  return solve(0, 0, 1);
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0);
  p10[0] = 1;
  for (int i = 1; i < 20; i++) p10[i] = (10 * p10[i - 1]) % mod;
  cin >> l >> r >> k;
  cout << (calc(r) - calc(l - 1) + mod) % mod << "\n";
  return 0;
}

### Prompt

Generate 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 int mod = 998244353;
long long dp[20][1024][2], ways[20][1024][2], p10[20], l, r, k, digs, num;
long long solve(int cur, int mask, int same) {
  if (dp[cur][mask][same] != -1) return dp[cur][mask][same];
  if (cur == digs + 1) {
    ways[cur][mask][same] = 1;
    return 0;
  }
  long long sum = 0, bound = 9, tways = 0;
  if (same) bound = num / (long long)pow(10, digs - cur) % 10;
  for (long long i = 0; i <= bound; i++) {
    if (__builtin_popcount(mask | (1 << i)) > k) continue;
    int p = same, nmask = mask;
    if (!(mask == 0 && i == 0)) nmask |= 1 << i;
    if (same && i < bound) p = 0;
    sum = (sum + solve(cur + 1, nmask, p)) % mod;
    sum = (sum + p10[digs - cur] * i * ways[cur + 1][nmask][p]) % mod;
    tways = (tways + ways[cur + 1][nmask][p]) % mod;
  }
  ways[cur][mask][same] = tways;
  return dp[cur][mask][same] = sum;
}
long long calc(long long to) {
  if (to == 0) return 0;
  digs = log10(to), num = to;
  memset(dp, -1, sizeof dp);
  return solve(0, 0, 1);
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0);
  p10[0] = 1;
  for (int i = 1; i < 20; i++) p10[i] = (10 * p10[i - 1]) % mod;
  cin >> l >> r >> k;
  cout << (calc(r) - calc(l - 1) + mod) % mod << "\n";
  return 0;
}

```