#include <bits/stdc++.h>
using namespace std;
inline long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
int month[15] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int dir[8][2] = {{-1, 0},  {1, 0}, {0, -1}, {0, 1},
                 {-1, -1}, {1, 1}, {1, -1}, {-1, 1}};
const int MAXN = 2e5 + 5;
const int INF = 1 << 30;
const long long mod = 998244353;
const double eps = 1e-8;
const long long inff = 0x3f3f3f3f3f3f3f3f;
long long dp[25][1030][12];
long long d[25][1030];
long long t[25];
int a[25];
int f[25];
int k[1030];
int p;
struct num {
  long long a, b;
} s;
num dfs(int pos, int now, int sta, int limit) {
  if (pos == 0) {
    return (num){1, now};
  }
  if (!limit && dp[pos][sta][now] != -1) {
    return (num){d[pos][sta], dp[pos][sta][now]};
  }
  int up = limit ? a[pos] : 9, g;
  long long ans = 0, cnt = 0;
  for (int i = 0; i <= up; i++) {
    if (sta == 0 && i == 0) {
      s = dfs(pos - 1, i, sta, limit && i == up);
      cnt += s.a;
      ans += s.b;
      cnt %= mod;
      ans %= mod;
    } else {
      g = sta | f[i];
      if (k[g] <= p) {
        s = dfs(pos - 1, i, g, limit && i == up);
        cnt += s.a;
        ans += s.b;
        cnt %= mod;
        ans %= mod;
      }
    }
  }
  ans = (ans + cnt * t[pos] % mod * (long long)now % mod) % mod;
  if (!limit) d[pos][sta] = cnt, dp[pos][sta][now] = ans;
  return (num){cnt, ans};
}
long long solve(long long x) {
  if (x == 0) return 0;
  int pos = 0;
  while (x) {
    a[++pos] = x % 10;
    x /= 10;
  }
  a[pos + 1] = 0;
  return dfs(pos, 0, 0, 1).b;
}
int main() {
  long long n, m;
  f[0] = 1, t[0] = 1;
  for (int i = 1; i <= 18; i++)
    f[i] = f[i - 1] * 2, t[i] = t[i - 1] * 10, t[i] %= mod;
  for (int i = 0; i <= 1024; i++) {
    int j = i, cnt = 0;
    while (j) {
      cnt += j % 2;
      j /= 2;
    }
    k[i] = cnt;
  }
  for (int i = 0; i <= 20; i++)
    for (int j = 0; j <= 1024; j++) {
      d[i][j] = -1;
      for (int I = 0; I <= 9; I++) dp[i][j][I] = -1;
    }
  {
    scanf("%lld%lld%d", &n, &m, &p);
    n = solve(n - 1);
    m = solve(m);
    printf("%lld\n", (m - n + mod) % mod);
  }
  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;
inline long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
int month[15] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int dir[8][2] = {{-1, 0},  {1, 0}, {0, -1}, {0, 1},
                 {-1, -1}, {1, 1}, {1, -1}, {-1, 1}};
const int MAXN = 2e5 + 5;
const int INF = 1 << 30;
const long long mod = 998244353;
const double eps = 1e-8;
const long long inff = 0x3f3f3f3f3f3f3f3f;
long long dp[25][1030][12];
long long d[25][1030];
long long t[25];
int a[25];
int f[25];
int k[1030];
int p;
struct num {
  long long a, b;
} s;
num dfs(int pos, int now, int sta, int limit) {
  if (pos == 0) {
    return (num){1, now};
  }
  if (!limit && dp[pos][sta][now] != -1) {
    return (num){d[pos][sta], dp[pos][sta][now]};
  }
  int up = limit ? a[pos] : 9, g;
  long long ans = 0, cnt = 0;
  for (int i = 0; i <= up; i++) {
    if (sta == 0 && i == 0) {
      s = dfs(pos - 1, i, sta, limit && i == up);
      cnt += s.a;
      ans += s.b;
      cnt %= mod;
      ans %= mod;
    } else {
      g = sta | f[i];
      if (k[g] <= p) {
        s = dfs(pos - 1, i, g, limit && i == up);
        cnt += s.a;
        ans += s.b;
        cnt %= mod;
        ans %= mod;
      }
    }
  }
  ans = (ans + cnt * t[pos] % mod * (long long)now % mod) % mod;
  if (!limit) d[pos][sta] = cnt, dp[pos][sta][now] = ans;
  return (num){cnt, ans};
}
long long solve(long long x) {
  if (x == 0) return 0;
  int pos = 0;
  while (x) {
    a[++pos] = x % 10;
    x /= 10;
  }
  a[pos + 1] = 0;
  return dfs(pos, 0, 0, 1).b;
}
int main() {
  long long n, m;
  f[0] = 1, t[0] = 1;
  for (int i = 1; i <= 18; i++)
    f[i] = f[i - 1] * 2, t[i] = t[i - 1] * 10, t[i] %= mod;
  for (int i = 0; i <= 1024; i++) {
    int j = i, cnt = 0;
    while (j) {
      cnt += j % 2;
      j /= 2;
    }
    k[i] = cnt;
  }
  for (int i = 0; i <= 20; i++)
    for (int j = 0; j <= 1024; j++) {
      d[i][j] = -1;
      for (int I = 0; I <= 9; I++) dp[i][j][I] = -1;
    }
  {
    scanf("%lld%lld%d", &n, &m, &p);
    n = solve(n - 1);
    m = solve(m);
    printf("%lld\n", (m - n + mod) % mod);
  }
  return 0;
}

```