#include <bits/stdc++.h>
using namespace std;
const int maxn = 100;
const int maxnum = (1 << 10);
const int mod = 998244353;
int k;
int cnt[maxnum + 5];
int dp1[maxn + 5][maxnum + 5];
int dp2[maxn + 5][maxnum + 5];
long long l, r;
int a[maxn + 5], pw[20];
int dfs1(int len, int st, bool zero, bool equ) {
  if (len <= 0) {
    return 1;
  }
  if (!zero && !equ && dp1[len][st] != -1) return dp1[len][st];
  int up = equ ? a[len] : 9;
  int ans = 0;
  for (int i = 0; i <= up; i++) {
    if (zero && !i)
      ans = (ans + dfs1(len - 1, st, true, equ & (i == up))) % mod;
    else {
      int nxt = (st | (1 << i));
      if (cnt[nxt] > k) continue;
      ans = (ans + dfs1(len - 1, nxt, false, equ & (i == up))) % mod;
    }
  }
  if (!zero && !equ) dp1[len][st] = ans;
  return ans;
}
int dfs2(int len, int st, bool zero, bool equ) {
  if (len <= 0) return 0;
  if (!zero && !equ && dp2[len][st] != -1) return dp2[len][st];
  int up = equ ? a[len] : 9;
  int ans = 0;
  for (int i = 0; i <= up; i++) {
    if (zero && !i)
      ans = (ans + dfs2(len - 1, st, true, equ & (i == up))) % mod;
    else {
      int nxt = (st | (1 << i));
      if (cnt[nxt] > k) continue;
      ans = (ans + dfs2(len - 1, nxt, false, equ & (i == up))) % mod;
      ans = (ans + 1LL * i * pw[len - 1] % mod *
                       dfs1(len - 1, nxt, false, equ & (i == up)) % mod) %
            mod;
    }
  }
  if (!zero && !equ) dp2[len][st] = ans;
  return ans;
}
int getCnt(int x) {
  int cnt = 0;
  while (x) {
    x = (x & (x - 1));
    cnt++;
  }
  return cnt;
}
void Init() {
  for (int i = 0; i <= maxnum; i++) cnt[i] = getCnt(i);
  pw[0] = 1;
  for (int i = 1; i < 20; i++) pw[i] = 1LL * pw[i - 1] * 10 % mod;
}
int calc(long long x) {
  int len = 0;
  while (x) {
    a[++len] = x % 10;
    x /= 10;
  }
  memset(dp1, -1, sizeof(dp1));
  memset(dp2, -1, sizeof(dp2));
  return dfs2(len, 0, true, true);
}
int main() {
  Init();
  scanf("%lld%lld%d", &l, &r, &k);
  int ans2 = calc(r);
  int ans1 = calc(l - 1);
  printf("%d\n", (ans2 - ans1 + mod) % mod);
  return 0;
}

### Prompt

Please formulate 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 maxn = 100;
const int maxnum = (1 << 10);
const int mod = 998244353;
int k;
int cnt[maxnum + 5];
int dp1[maxn + 5][maxnum + 5];
int dp2[maxn + 5][maxnum + 5];
long long l, r;
int a[maxn + 5], pw[20];
int dfs1(int len, int st, bool zero, bool equ) {
  if (len <= 0) {
    return 1;
  }
  if (!zero && !equ && dp1[len][st] != -1) return dp1[len][st];
  int up = equ ? a[len] : 9;
  int ans = 0;
  for (int i = 0; i <= up; i++) {
    if (zero && !i)
      ans = (ans + dfs1(len - 1, st, true, equ & (i == up))) % mod;
    else {
      int nxt = (st | (1 << i));
      if (cnt[nxt] > k) continue;
      ans = (ans + dfs1(len - 1, nxt, false, equ & (i == up))) % mod;
    }
  }
  if (!zero && !equ) dp1[len][st] = ans;
  return ans;
}
int dfs2(int len, int st, bool zero, bool equ) {
  if (len <= 0) return 0;
  if (!zero && !equ && dp2[len][st] != -1) return dp2[len][st];
  int up = equ ? a[len] : 9;
  int ans = 0;
  for (int i = 0; i <= up; i++) {
    if (zero && !i)
      ans = (ans + dfs2(len - 1, st, true, equ & (i == up))) % mod;
    else {
      int nxt = (st | (1 << i));
      if (cnt[nxt] > k) continue;
      ans = (ans + dfs2(len - 1, nxt, false, equ & (i == up))) % mod;
      ans = (ans + 1LL * i * pw[len - 1] % mod *
                       dfs1(len - 1, nxt, false, equ & (i == up)) % mod) %
            mod;
    }
  }
  if (!zero && !equ) dp2[len][st] = ans;
  return ans;
}
int getCnt(int x) {
  int cnt = 0;
  while (x) {
    x = (x & (x - 1));
    cnt++;
  }
  return cnt;
}
void Init() {
  for (int i = 0; i <= maxnum; i++) cnt[i] = getCnt(i);
  pw[0] = 1;
  for (int i = 1; i < 20; i++) pw[i] = 1LL * pw[i - 1] * 10 % mod;
}
int calc(long long x) {
  int len = 0;
  while (x) {
    a[++len] = x % 10;
    x /= 10;
  }
  memset(dp1, -1, sizeof(dp1));
  memset(dp2, -1, sizeof(dp2));
  return dfs2(len, 0, true, true);
}
int main() {
  Init();
  scanf("%lld%lld%d", &l, &r, &k);
  int ans2 = calc(r);
  int ans1 = calc(l - 1);
  printf("%d\n", (ans2 - ans1 + mod) % mod);
  return 0;
}

```