#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
long long dp[20][1 << 10][2], cnt[20][1 << 10][2];
long long L, R, K;
int gogogo(long long n) {
  memset(dp, 0, sizeof(dp));
  memset(cnt, 0, sizeof(cnt));
  vector<int> digit;
  vector<long long> row;
  for (long long i = n, d = 1; i; i /= 10, d = d * 10 % MOD)
    digit.push_back(i % 10), row.push_back(d);
  reverse(digit.begin(), digit.end());
  reverse(row.begin(), row.end());
  cnt[0][0][1] = 1;
  for (int i = 0; i < digit.size(); ++i) {
    for (int S = 0; S < (1 << 10); ++S) {
      for (int p = 0; p < 10; ++p) {
        int nS = S | (1 << p);
        if (S == 0 and p == 0) nS = 0;
        (dp[i + 1][nS][0] += dp[i][S][0] + row[i] * cnt[i][S][0] * p % MOD) %=
            MOD;
        (cnt[i + 1][nS][0] += cnt[i][S][0]) %= MOD;
        if (p < digit[i])
          (dp[i + 1][nS][0] += dp[i][S][1] + row[i] * cnt[i][S][1] * p % MOD) %=
              MOD,
              (cnt[i + 1][nS][0] += cnt[i][S][1]) %= MOD;
        else if (p == digit[i])
          (dp[i + 1][nS][1] += dp[i][S][1] + row[i] * cnt[i][S][1] * p % MOD) %=
              MOD,
              (cnt[i + 1][nS][1] += cnt[i][S][1]) %= MOD;
      }
    }
  }
  long long ans = 0;
  for (int S = 1; S < (1 << 10); ++S)
    if (__builtin_popcount(S) <= K) (ans += dp[digit.size()][S][0]) %= MOD;
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> L >> R >> K;
  long long ans = gogogo(R + 1) - gogogo(L);
  cout << (ans % MOD + MOD) % MOD << '\n';
}

### 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 int MOD = 998244353;
long long dp[20][1 << 10][2], cnt[20][1 << 10][2];
long long L, R, K;
int gogogo(long long n) {
  memset(dp, 0, sizeof(dp));
  memset(cnt, 0, sizeof(cnt));
  vector<int> digit;
  vector<long long> row;
  for (long long i = n, d = 1; i; i /= 10, d = d * 10 % MOD)
    digit.push_back(i % 10), row.push_back(d);
  reverse(digit.begin(), digit.end());
  reverse(row.begin(), row.end());
  cnt[0][0][1] = 1;
  for (int i = 0; i < digit.size(); ++i) {
    for (int S = 0; S < (1 << 10); ++S) {
      for (int p = 0; p < 10; ++p) {
        int nS = S | (1 << p);
        if (S == 0 and p == 0) nS = 0;
        (dp[i + 1][nS][0] += dp[i][S][0] + row[i] * cnt[i][S][0] * p % MOD) %=
            MOD;
        (cnt[i + 1][nS][0] += cnt[i][S][0]) %= MOD;
        if (p < digit[i])
          (dp[i + 1][nS][0] += dp[i][S][1] + row[i] * cnt[i][S][1] * p % MOD) %=
              MOD,
              (cnt[i + 1][nS][0] += cnt[i][S][1]) %= MOD;
        else if (p == digit[i])
          (dp[i + 1][nS][1] += dp[i][S][1] + row[i] * cnt[i][S][1] * p % MOD) %=
              MOD,
              (cnt[i + 1][nS][1] += cnt[i][S][1]) %= MOD;
      }
    }
  }
  long long ans = 0;
  for (int S = 1; S < (1 << 10); ++S)
    if (__builtin_popcount(S) <= K) (ans += dp[digit.size()][S][0]) %= MOD;
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> L >> R >> K;
  long long ans = gogogo(R + 1) - gogogo(L);
  cout << (ans % MOD + MOD) % MOD << '\n';
}

```