#include <bits/stdc++.h>
const long long mod = 998244353;
const int N = 22, M = 1 << 10;
std::pair<long long, long long> dp[N][M];
int a[N], top, cnt[M], k;
long long l, r, ten[N];
bool vis[N][M];
std::pair<long long, long long> dfs(int p, int sta, bool zero, bool lim) {
  if (p < 0)
    return cnt[sta] <= k && !zero ? std::pair<long long, long long>(0, 1)
                                  : std::pair<long long, long long>(0, 0);
  if (!zero && !lim && vis[p][sta]) return dp[p][sta];
  std::pair<long long, long long> ans(0, 0);
  int up = lim ? a[p] : 9;
  for (int i = 0; i <= up; i++) {
    std::pair<long long, long long> c =
        dfs(p - 1, zero && !i ? 0 : (sta | 1 << i), zero && !i, lim && i == up);
    ans.second += c.second;
    ans.first += c.first;
    ans.first += c.second * i * ten[p] % mod;
    ans.first %= mod;
    ans.second %= mod;
  }
  if (!zero && !lim) vis[p][sta] = 1, dp[p][sta] = ans;
  return ans;
}
long long solve(long long x) {
  if (!x) return 0;
  top = 0;
  while (x) a[top++] = x % 10, x /= 10;
  return dfs(top - 1, 0, 1, 1).first;
}
int main() {
  ten[0] = 1;
  for (int i = 1; i < N; i++) ten[i] = ten[i - 1] * 10 % mod;
  for (int i = 0; i < 1 << 10; i++)
    for (int j = i; j; j -= j & -j) cnt[i]++;
  scanf("%lld%lld%d", &l, &r, &k);
  printf("%lld\n", (solve(r) - solve(l - 1) + mod) % mod);
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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>
const long long mod = 998244353;
const int N = 22, M = 1 << 10;
std::pair<long long, long long> dp[N][M];
int a[N], top, cnt[M], k;
long long l, r, ten[N];
bool vis[N][M];
std::pair<long long, long long> dfs(int p, int sta, bool zero, bool lim) {
  if (p < 0)
    return cnt[sta] <= k && !zero ? std::pair<long long, long long>(0, 1)
                                  : std::pair<long long, long long>(0, 0);
  if (!zero && !lim && vis[p][sta]) return dp[p][sta];
  std::pair<long long, long long> ans(0, 0);
  int up = lim ? a[p] : 9;
  for (int i = 0; i <= up; i++) {
    std::pair<long long, long long> c =
        dfs(p - 1, zero && !i ? 0 : (sta | 1 << i), zero && !i, lim && i == up);
    ans.second += c.second;
    ans.first += c.first;
    ans.first += c.second * i * ten[p] % mod;
    ans.first %= mod;
    ans.second %= mod;
  }
  if (!zero && !lim) vis[p][sta] = 1, dp[p][sta] = ans;
  return ans;
}
long long solve(long long x) {
  if (!x) return 0;
  top = 0;
  while (x) a[top++] = x % 10, x /= 10;
  return dfs(top - 1, 0, 1, 1).first;
}
int main() {
  ten[0] = 1;
  for (int i = 1; i < N; i++) ten[i] = ten[i - 1] * 10 % mod;
  for (int i = 0; i < 1 << 10; i++)
    for (int j = i; j; j -= j & -j) cnt[i]++;
  scanf("%lld%lld%d", &l, &r, &k);
  printf("%lld\n", (solve(r) - solve(l - 1) + mod) % mod);
  return 0;
}

```