#include <bits/stdc++.h>
using namespace std;
signed long long L, R, K;
signed long long p10[20];
signed long long mo = 998244353;
signed long long S[20][2][1 << 10];
signed long long num[20][2][1 << 10];
void solve() {
  int i, j, k, l, r, x, y;
  string s;
  cin >> L >> R >> K;
  p10[0] = 1;
  for (i = 0; i < (19); i++) p10[i + 1] = p10[i] * 10;
  signed long long ret = 0;
  for (i = 0; i < (2); i++) {
    signed long long N = (i == 0) ? R : L - 1;
    memset(S, 0, sizeof(S));
    memset(num, 0, sizeof(num));
    num[19][1][0] = 1;
    for (j = 18; j >= 0; j--) {
      for (int mask = 0; mask < 1 << 10; mask++) {
        for (x = 0; x < (2); x++) {
          for (y = 0; y < (10); y++) {
            if (x && y > N / p10[j] % 10) continue;
            int nmask = mask | (1 << y);
            if (mask == 0 && y == 0) nmask = 0;
            int ty = x;
            if (x == 1 && y < N / p10[j] % 10) ty = 0;
            (num[j][ty][nmask] += num[j + 1][x][mask]) %= mo;
            (S[j][ty][nmask] +=
             S[j + 1][x][mask] + num[j + 1][x][mask] * y % mo * p10[j]) %= mo;
          }
        }
      }
    }
    for (int mask = 0; mask < 1 << 10; mask++)
      if (__builtin_popcount(mask) <= K) {
        if (i == 0)
          ret += S[0][0][mask] + S[0][1][mask];
        else
          ret -= S[0][0][mask] + S[0][1][mask];
      }
  }
  cout << (ret % mo + mo) % mo << endl;
}
int main(int argc, char** argv) {
  string s;
  int i;
  if (argc == 1) ios::sync_with_stdio(false), cin.tie(0);
  for (i = 0; i < (argc - 1); i++) s += argv[i + 1], s += '\n';
  for (i = 0; i < (s.size()); i++) ungetc(s[s.size() - 1 - i], stdin);
  cout.tie(0);
  solve();
  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;
signed long long L, R, K;
signed long long p10[20];
signed long long mo = 998244353;
signed long long S[20][2][1 << 10];
signed long long num[20][2][1 << 10];
void solve() {
  int i, j, k, l, r, x, y;
  string s;
  cin >> L >> R >> K;
  p10[0] = 1;
  for (i = 0; i < (19); i++) p10[i + 1] = p10[i] * 10;
  signed long long ret = 0;
  for (i = 0; i < (2); i++) {
    signed long long N = (i == 0) ? R : L - 1;
    memset(S, 0, sizeof(S));
    memset(num, 0, sizeof(num));
    num[19][1][0] = 1;
    for (j = 18; j >= 0; j--) {
      for (int mask = 0; mask < 1 << 10; mask++) {
        for (x = 0; x < (2); x++) {
          for (y = 0; y < (10); y++) {
            if (x && y > N / p10[j] % 10) continue;
            int nmask = mask | (1 << y);
            if (mask == 0 && y == 0) nmask = 0;
            int ty = x;
            if (x == 1 && y < N / p10[j] % 10) ty = 0;
            (num[j][ty][nmask] += num[j + 1][x][mask]) %= mo;
            (S[j][ty][nmask] +=
             S[j + 1][x][mask] + num[j + 1][x][mask] * y % mo * p10[j]) %= mo;
          }
        }
      }
    }
    for (int mask = 0; mask < 1 << 10; mask++)
      if (__builtin_popcount(mask) <= K) {
        if (i == 0)
          ret += S[0][0][mask] + S[0][1][mask];
        else
          ret -= S[0][0][mask] + S[0][1][mask];
      }
  }
  cout << (ret % mo + mo) % mo << endl;
}
int main(int argc, char** argv) {
  string s;
  int i;
  if (argc == 1) ios::sync_with_stdio(false), cin.tie(0);
  for (i = 0; i < (argc - 1); i++) s += argv[i + 1], s += '\n';
  for (i = 0; i < (s.size()); i++) ungetc(s[s.size() - 1 - i], stdin);
  cout.tie(0);
  solve();
  return 0;
}

```