#include <bits/stdc++.h>
using namespace std;
long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9')
    x = (x << 3) + (x << 1) + f * (c - '0'), c = getchar();
  return x;
}
const long long MAXN = 200 + 10, mod = 998244353;
long long l, r, k, len;
long long h[MAXN];
long long g[MAXN];
struct node {
  long long x, y;
};
node f[MAXN][2000];
long long b[200];
node dfs(long long pos, long long limit, long long lead, long long b) {
  if (!pos) {
    long long x = b;
    long long num = 0;
    while (x > 0) {
      if (x % 2 == 1) num++;
      x /= 2;
    }
    node p;
    p.x = 0;
    p.y = 0;
    if (num <= k) {
      p.x = 1;
      p.y = 0;
      return p;
    }
    return p;
  }
  if (limit == 0 && lead == 0 && f[pos][b].x != -1) return f[pos][b];
  long long maxn = 9;
  node res;
  res.x = 0;
  res.y = 0;
  if (limit == 1) maxn = h[pos];
  for (long long i = 0; i <= maxn; i++) {
    node p;
    long long x = b;
    if (lead == 1 && i == 0)
      x = 0;
    else
      x = b | (1 << i);
    p = dfs(pos - 1, limit && (i == maxn), lead && (i == 0), x);
    res.y = ((res.y + i * g[pos - 1] % mod * p.x % mod) % mod + p.y) % mod;
    res.x = (res.x + p.x) % mod;
  }
  if (limit == 0 && lead == 0) f[pos][b] = res;
  return res;
}
long long part(long long x) {
  len = 0;
  while (x > 0) {
    h[++len] = x % 10;
    x /= 10;
  }
  return dfs(len, 1, 1, 0).y % mod;
}
long long pd(long long x) {
  long long y = x;
  for (long long i = 0; i <= 9; i++) b[i] = 0;
  while (x > 0) {
    b[x % 10] = 1;
    x /= 10;
  }
  long long sum = 0;
  for (long long i = 0; i <= 9; i++) sum += b[i];
  if (sum <= k) return y;
  return 0;
}
signed main() {
  memset(f, -1, sizeof(f));
  g[0] = 1;
  for (long long i = 1; i <= MAXN - 10; i++) g[i] = g[i - 1] * 10 % mod;
  l = read();
  r = read();
  k = read();
  printf("%lld\n", (part(r) - part(l) + pd(l) + mod) % mod);
  return 0;
}

### Prompt

Create a solution in cpp for 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;
long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9')
    x = (x << 3) + (x << 1) + f * (c - '0'), c = getchar();
  return x;
}
const long long MAXN = 200 + 10, mod = 998244353;
long long l, r, k, len;
long long h[MAXN];
long long g[MAXN];
struct node {
  long long x, y;
};
node f[MAXN][2000];
long long b[200];
node dfs(long long pos, long long limit, long long lead, long long b) {
  if (!pos) {
    long long x = b;
    long long num = 0;
    while (x > 0) {
      if (x % 2 == 1) num++;
      x /= 2;
    }
    node p;
    p.x = 0;
    p.y = 0;
    if (num <= k) {
      p.x = 1;
      p.y = 0;
      return p;
    }
    return p;
  }
  if (limit == 0 && lead == 0 && f[pos][b].x != -1) return f[pos][b];
  long long maxn = 9;
  node res;
  res.x = 0;
  res.y = 0;
  if (limit == 1) maxn = h[pos];
  for (long long i = 0; i <= maxn; i++) {
    node p;
    long long x = b;
    if (lead == 1 && i == 0)
      x = 0;
    else
      x = b | (1 << i);
    p = dfs(pos - 1, limit && (i == maxn), lead && (i == 0), x);
    res.y = ((res.y + i * g[pos - 1] % mod * p.x % mod) % mod + p.y) % mod;
    res.x = (res.x + p.x) % mod;
  }
  if (limit == 0 && lead == 0) f[pos][b] = res;
  return res;
}
long long part(long long x) {
  len = 0;
  while (x > 0) {
    h[++len] = x % 10;
    x /= 10;
  }
  return dfs(len, 1, 1, 0).y % mod;
}
long long pd(long long x) {
  long long y = x;
  for (long long i = 0; i <= 9; i++) b[i] = 0;
  while (x > 0) {
    b[x % 10] = 1;
    x /= 10;
  }
  long long sum = 0;
  for (long long i = 0; i <= 9; i++) sum += b[i];
  if (sum <= k) return y;
  return 0;
}
signed main() {
  memset(f, -1, sizeof(f));
  g[0] = 1;
  for (long long i = 1; i <= MAXN - 10; i++) g[i] = g[i - 1] * 10 % mod;
  l = read();
  r = read();
  k = read();
  printf("%lld\n", (part(r) - part(l) + pd(l) + mod) % mod);
  return 0;
}

```