#include <bits/stdc++.h>
using namespace std;
const long double eps = 1e-9;
const long double PI = acos(-1);
const int INF = (int)1e9;
const long long INFF = (long long)1e18;
const int mod = 998244353;
const int MXN = (int)2e5 + 7;
int k;
long long dp[20][1037][2];
long long siz[20][1037][2];
int a[22];
int num[1037];
int len(long long v) {
  int res = 0;
  while (v) {
    res++;
    a[res] = v % 10;
    v /= 10;
  }
  reverse(a + 1, a + res + 1);
  return res;
}
inline void add(long long &v1, long long v2) {
  v1 = (v1 + v2) % mod;
  return;
}
long long bs[20];
long long sol(long long v) {
  long long res = 0;
  for (int i = 0; i < 1033; i++)
    for (int j = 0; j < 20; j++)
      for (int l = 0; l < 2; l++) dp[j][i][l] = siz[j][i][l] = 0;
  siz[0][0][0] = 1;
  int n = len(v);
  for (int i = 1; i < n + 1; i++) {
    siz[i][0][1] = 1;
    for (int j = 0; j < 10; j++) {
      for (int mask = 2; mask < 1024; mask++)
        if ((mask & (1 << j)) && num[mask] <= k) {
          long long &v = dp[i][mask][1];
          add(v, dp[i - 1][mask][1]);
          add(v, siz[i - 1][mask][1] * bs[n - i] % mod * j % mod);
          add(siz[i][mask][1], siz[i - 1][mask][1]);
          int tmp = mask ^ (1 << j);
          add(v, dp[i - 1][tmp][1]);
          add(v, siz[i - 1][tmp][1] * bs[n - i] % mod * j % mod);
          add(siz[i][mask][1], siz[i - 1][tmp][1]);
          long long &v2 = dp[i][mask][0];
          if (j < a[i]) {
            add(v, dp[i - 1][mask][0]);
            add(v, siz[i - 1][mask][0] * bs[n - i] % mod * j % mod);
            add(siz[i][mask][1], siz[i - 1][mask][0]);
            int tmp = mask ^ (1 << j);
            add(v, dp[i - 1][tmp][0]);
            add(v, siz[i - 1][tmp][0] * bs[n - i] % mod * j % mod);
            add(siz[i][mask][1], siz[i - 1][tmp][0]);
          } else if (j == a[i]) {
            add(v2, dp[i - 1][mask][0]);
            add(v2, siz[i - 1][mask][0] * bs[n - i] % mod * j % mod);
            add(siz[i][mask][0], siz[i - 1][mask][0]);
            int tmp = mask ^ (1 << j);
            add(v2, dp[i - 1][tmp][0]);
            add(v2, siz[i - 1][tmp][0] * bs[n - i] % mod * j % mod);
            add(siz[i][mask][0], siz[i - 1][tmp][0]);
          }
        }
    }
  }
  for (int i = 0; i < 1024; i++)
    if (num[i] <= k) {
      add(res, dp[n][i][0]);
      add(res, dp[n][i][1]);
    }
  return res;
}
int main(void) {
  for (int i = 1; i < 1033; i++) num[i] = __builtin_popcount(i);
  bs[0] = 1;
  for (int i = 1; i < 19; i++) bs[i] = bs[i - 1] * 10 % mod;
  long long ll, rr;
  scanf("%lld %lld %d", &ll, &rr, &k);
  long long v1 = sol(rr);
  long long v2 = sol(ll - 1);
  long long ans = (v1 - v2 + mod) % mod;
  printf("%lld\n", ans);
  return 0;
}

### Prompt

In Cpp, your task is to solve 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 double eps = 1e-9;
const long double PI = acos(-1);
const int INF = (int)1e9;
const long long INFF = (long long)1e18;
const int mod = 998244353;
const int MXN = (int)2e5 + 7;
int k;
long long dp[20][1037][2];
long long siz[20][1037][2];
int a[22];
int num[1037];
int len(long long v) {
  int res = 0;
  while (v) {
    res++;
    a[res] = v % 10;
    v /= 10;
  }
  reverse(a + 1, a + res + 1);
  return res;
}
inline void add(long long &v1, long long v2) {
  v1 = (v1 + v2) % mod;
  return;
}
long long bs[20];
long long sol(long long v) {
  long long res = 0;
  for (int i = 0; i < 1033; i++)
    for (int j = 0; j < 20; j++)
      for (int l = 0; l < 2; l++) dp[j][i][l] = siz[j][i][l] = 0;
  siz[0][0][0] = 1;
  int n = len(v);
  for (int i = 1; i < n + 1; i++) {
    siz[i][0][1] = 1;
    for (int j = 0; j < 10; j++) {
      for (int mask = 2; mask < 1024; mask++)
        if ((mask & (1 << j)) && num[mask] <= k) {
          long long &v = dp[i][mask][1];
          add(v, dp[i - 1][mask][1]);
          add(v, siz[i - 1][mask][1] * bs[n - i] % mod * j % mod);
          add(siz[i][mask][1], siz[i - 1][mask][1]);
          int tmp = mask ^ (1 << j);
          add(v, dp[i - 1][tmp][1]);
          add(v, siz[i - 1][tmp][1] * bs[n - i] % mod * j % mod);
          add(siz[i][mask][1], siz[i - 1][tmp][1]);
          long long &v2 = dp[i][mask][0];
          if (j < a[i]) {
            add(v, dp[i - 1][mask][0]);
            add(v, siz[i - 1][mask][0] * bs[n - i] % mod * j % mod);
            add(siz[i][mask][1], siz[i - 1][mask][0]);
            int tmp = mask ^ (1 << j);
            add(v, dp[i - 1][tmp][0]);
            add(v, siz[i - 1][tmp][0] * bs[n - i] % mod * j % mod);
            add(siz[i][mask][1], siz[i - 1][tmp][0]);
          } else if (j == a[i]) {
            add(v2, dp[i - 1][mask][0]);
            add(v2, siz[i - 1][mask][0] * bs[n - i] % mod * j % mod);
            add(siz[i][mask][0], siz[i - 1][mask][0]);
            int tmp = mask ^ (1 << j);
            add(v2, dp[i - 1][tmp][0]);
            add(v2, siz[i - 1][tmp][0] * bs[n - i] % mod * j % mod);
            add(siz[i][mask][0], siz[i - 1][tmp][0]);
          }
        }
    }
  }
  for (int i = 0; i < 1024; i++)
    if (num[i] <= k) {
      add(res, dp[n][i][0]);
      add(res, dp[n][i][1]);
    }
  return res;
}
int main(void) {
  for (int i = 1; i < 1033; i++) num[i] = __builtin_popcount(i);
  bs[0] = 1;
  for (int i = 1; i < 19; i++) bs[i] = bs[i - 1] * 10 % mod;
  long long ll, rr;
  scanf("%lld %lld %d", &ll, &rr, &k);
  long long v1 = sol(rr);
  long long v2 = sol(ll - 1);
  long long ans = (v1 - v2 + mod) % mod;
  printf("%lld\n", ans);
  return 0;
}

```