#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int n, p;
long long t, dp[20][1100], dp2[20][1100];
int lim;
long long len[20], l, r;
int a[100], al;
inline int bitcount(int x) {
  int cnt = 0;
  for (; x; x &= (x - 1)) ++cnt;
  return cnt;
}
long long dfs(int remain, int state, long long la, bool flag, bool z) {
  if (remain == 0) return la;
  if (!flag) {
    long long res = 0, cnt = 0;
    for (int i = 0; i < 1024; ++i) {
      int nextstate = i | state;
      if (bitcount(nextstate) <= p && (dp2[remain][i] + dp[remain][i])) {
        res = (res + dp[remain][i]) % MOD;
        cnt = (cnt + dp2[remain][i]) % MOD;
        if (la && bitcount(nextstate) == p && !((state & 1) || (i & 1))) {
          res = (res + MOD - dp[remain - 1][i]) % MOD;
          cnt = (cnt + MOD - dp2[remain - 1][i]) % MOD;
        }
      }
    }
    long long ans = cnt * (la * len[remain] % MOD) % MOD + res;
    return ans % MOD;
  }
  int id = a[al - remain];
  long long res = 0;
  for (int i = 0; i < id; ++i) {
    bool nz = z && i == 0;
    int nextstate = nz ? state : (state | (1 << i));
    if (bitcount(nextstate) <= p)
      res = (res + dfs(remain - 1, nextstate, la * 10 + i, false, nz)) % MOD;
  }
  bool nz = z && id == 0;
  int nextstate = nz ? state : (state | (1 << id));
  if (bitcount(nextstate) <= p)
    res = (res + dfs(remain - 1, nextstate, la * 10 + id, true, nz)) % MOD;
  return res;
}
long long solve(long long x) {
  if (!x) return 0;
  long long tmp = x;
  al = 0;
  while (tmp) {
    a[al++] = tmp % 10;
    tmp /= 10;
  }
  reverse(a, a + al);
  long long ans = dfs(al, 0, 0LL, true, true);
  return ans;
}
int main() {
  scanf("%I64d%I64d%d", &l, &r, &p);
  len[0] = 1;
  for (int i = 1; i <= 18; ++i) len[i] = len[i - 1] * 10;
  for (int i = 0; i < 10; ++i) dp[1][1 << i] = i, dp2[1][1 << i] = 1;
  for (int i = 2; i <= 18; ++i) {
    for (int j = 0; j < 1024; ++j) {
      for (int k = 0; k < 10; ++k) {
        int nextstate = j | (1 << k);
        if (j <= 1) nextstate = 1 << k;
        dp[i][nextstate] = (dp[i][nextstate] + dp[i - 1][j] * 10 % MOD +
                            k * dp2[i - 1][j] % MOD) %
                           MOD;
        dp2[i][nextstate] = (dp2[i][nextstate] + dp2[i - 1][j]) % MOD;
      }
    }
  }
  printf("%I64d\n", (solve(r) + MOD - solve(l - 1)) % 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>
using namespace std;
const int MOD = 998244353;
int n, p;
long long t, dp[20][1100], dp2[20][1100];
int lim;
long long len[20], l, r;
int a[100], al;
inline int bitcount(int x) {
  int cnt = 0;
  for (; x; x &= (x - 1)) ++cnt;
  return cnt;
}
long long dfs(int remain, int state, long long la, bool flag, bool z) {
  if (remain == 0) return la;
  if (!flag) {
    long long res = 0, cnt = 0;
    for (int i = 0; i < 1024; ++i) {
      int nextstate = i | state;
      if (bitcount(nextstate) <= p && (dp2[remain][i] + dp[remain][i])) {
        res = (res + dp[remain][i]) % MOD;
        cnt = (cnt + dp2[remain][i]) % MOD;
        if (la && bitcount(nextstate) == p && !((state & 1) || (i & 1))) {
          res = (res + MOD - dp[remain - 1][i]) % MOD;
          cnt = (cnt + MOD - dp2[remain - 1][i]) % MOD;
        }
      }
    }
    long long ans = cnt * (la * len[remain] % MOD) % MOD + res;
    return ans % MOD;
  }
  int id = a[al - remain];
  long long res = 0;
  for (int i = 0; i < id; ++i) {
    bool nz = z && i == 0;
    int nextstate = nz ? state : (state | (1 << i));
    if (bitcount(nextstate) <= p)
      res = (res + dfs(remain - 1, nextstate, la * 10 + i, false, nz)) % MOD;
  }
  bool nz = z && id == 0;
  int nextstate = nz ? state : (state | (1 << id));
  if (bitcount(nextstate) <= p)
    res = (res + dfs(remain - 1, nextstate, la * 10 + id, true, nz)) % MOD;
  return res;
}
long long solve(long long x) {
  if (!x) return 0;
  long long tmp = x;
  al = 0;
  while (tmp) {
    a[al++] = tmp % 10;
    tmp /= 10;
  }
  reverse(a, a + al);
  long long ans = dfs(al, 0, 0LL, true, true);
  return ans;
}
int main() {
  scanf("%I64d%I64d%d", &l, &r, &p);
  len[0] = 1;
  for (int i = 1; i <= 18; ++i) len[i] = len[i - 1] * 10;
  for (int i = 0; i < 10; ++i) dp[1][1 << i] = i, dp2[1][1 << i] = 1;
  for (int i = 2; i <= 18; ++i) {
    for (int j = 0; j < 1024; ++j) {
      for (int k = 0; k < 10; ++k) {
        int nextstate = j | (1 << k);
        if (j <= 1) nextstate = 1 << k;
        dp[i][nextstate] = (dp[i][nextstate] + dp[i - 1][j] * 10 % MOD +
                            k * dp2[i - 1][j] % MOD) %
                           MOD;
        dp2[i][nextstate] = (dp2[i][nextstate] + dp2[i - 1][j]) % MOD;
      }
    }
  }
  printf("%I64d\n", (solve(r) + MOD - solve(l - 1)) % MOD);
  return 0;
}

```