#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
using namespace std;
const int MOD = 998244353;
template <class T>
T gcd(T a, T b) {
  return ((b == 0) ? a : gcd(b, a % b));
}
long long l, r, k;
int dp[20][2][1 << 11];
int dp1[20][1 << 11];
long long powt[20];
long long solve(long long g) {
  string s = to_string(g);
  int n = s.size();
  long long ans = 0LL;
  for (int p = (int)(1); p < (int)(n + 1); p++)
    for (int d = (int)(1); d < (int)(10); d++) {
      long long add = (1LL * d * powt[n - p]) % MOD;
      memset(dp, 0, sizeof(dp));
      dp[0][0][0] = 1;
      for (int i = (int)(1); i < (int)(n + 1); i++) {
        int le = 0, ri = 10;
        if (i == p) le = d, ri = d + 1;
        for (int j = 0; j < (int)(1 << 10); j++)
          for (int k = (int)(le); k < (int)(ri); k++)
            if (dp[i - 1][0][j] || dp[i - 1][1][j]) {
              if (i == 1 && !k) continue;
              int cr = s[i - 1] - '0';
              if (cr == k) {
                (dp[i][0][j | (1 << k)] += dp[i - 1][0][j]) %= MOD;
                (dp[i][1][j | (1 << k)] += dp[i - 1][1][j]) %= MOD;
              } else if (cr > k) {
                (dp[i][1][j | (1 << k)] += dp[i - 1][1][j]) %= MOD;
                (dp[i][1][j | (1 << k)] += dp[i - 1][0][j]) %= MOD;
              } else {
                (dp[i][1][j | (1 << k)] += dp[i - 1][1][j]) %= MOD;
              }
            }
      }
      for (int i = 0; i < (int)(1 << 10); i++) {
        if (__builtin_popcount(i) <= k) {
          (ans += (((dp[n][0][i] + dp[n][1][i]) % MOD) * add) % MOD) %= MOD;
        }
      }
    }
  for (int len = (int)(1); len < (int)(n); len++)
    for (int p = (int)(1); p < (int)(len + 1); p++)
      for (int d = (int)(1); d < (int)(10); d++) {
        long long add = (1LL * d * powt[len - p]) % MOD;
        memset(dp1, 0, sizeof(dp1));
        dp1[0][0] = 1;
        for (int i = (int)(1); i < (int)(len + 1); i++) {
          int le = 0, ri = 10;
          if (i == p) le = d, ri = d + 1;
          for (int j = 0; j < (int)(1 << 10); j++)
            for (int k = (int)(le); k < (int)(ri); k++)
              if (dp1[i - 1][j] || dp1[i - 1][j]) {
                if (i == 1 && !k) continue;
                (dp1[i][j | (1 << k)] += dp1[i - 1][j]) %= MOD;
              }
        }
        for (int i = 0; i < (int)(1 << 10); i++) {
          if (__builtin_popcount(i) <= k) {
            (ans += (dp1[len][i] * add) % MOD) %= MOD;
          }
        }
      }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> l >> r >> k;
  powt[0] = 1LL;
  for (int i = (int)(1); i < (int)(20); i++)
    powt[i] = (1LL * 10 * powt[i - 1]) % MOD;
  cout << (solve(r) - solve(l - 1) + MOD) % MOD << endl;
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
using namespace std;
const int MOD = 998244353;
template <class T>
T gcd(T a, T b) {
  return ((b == 0) ? a : gcd(b, a % b));
}
long long l, r, k;
int dp[20][2][1 << 11];
int dp1[20][1 << 11];
long long powt[20];
long long solve(long long g) {
  string s = to_string(g);
  int n = s.size();
  long long ans = 0LL;
  for (int p = (int)(1); p < (int)(n + 1); p++)
    for (int d = (int)(1); d < (int)(10); d++) {
      long long add = (1LL * d * powt[n - p]) % MOD;
      memset(dp, 0, sizeof(dp));
      dp[0][0][0] = 1;
      for (int i = (int)(1); i < (int)(n + 1); i++) {
        int le = 0, ri = 10;
        if (i == p) le = d, ri = d + 1;
        for (int j = 0; j < (int)(1 << 10); j++)
          for (int k = (int)(le); k < (int)(ri); k++)
            if (dp[i - 1][0][j] || dp[i - 1][1][j]) {
              if (i == 1 && !k) continue;
              int cr = s[i - 1] - '0';
              if (cr == k) {
                (dp[i][0][j | (1 << k)] += dp[i - 1][0][j]) %= MOD;
                (dp[i][1][j | (1 << k)] += dp[i - 1][1][j]) %= MOD;
              } else if (cr > k) {
                (dp[i][1][j | (1 << k)] += dp[i - 1][1][j]) %= MOD;
                (dp[i][1][j | (1 << k)] += dp[i - 1][0][j]) %= MOD;
              } else {
                (dp[i][1][j | (1 << k)] += dp[i - 1][1][j]) %= MOD;
              }
            }
      }
      for (int i = 0; i < (int)(1 << 10); i++) {
        if (__builtin_popcount(i) <= k) {
          (ans += (((dp[n][0][i] + dp[n][1][i]) % MOD) * add) % MOD) %= MOD;
        }
      }
    }
  for (int len = (int)(1); len < (int)(n); len++)
    for (int p = (int)(1); p < (int)(len + 1); p++)
      for (int d = (int)(1); d < (int)(10); d++) {
        long long add = (1LL * d * powt[len - p]) % MOD;
        memset(dp1, 0, sizeof(dp1));
        dp1[0][0] = 1;
        for (int i = (int)(1); i < (int)(len + 1); i++) {
          int le = 0, ri = 10;
          if (i == p) le = d, ri = d + 1;
          for (int j = 0; j < (int)(1 << 10); j++)
            for (int k = (int)(le); k < (int)(ri); k++)
              if (dp1[i - 1][j] || dp1[i - 1][j]) {
                if (i == 1 && !k) continue;
                (dp1[i][j | (1 << k)] += dp1[i - 1][j]) %= MOD;
              }
        }
        for (int i = 0; i < (int)(1 << 10); i++) {
          if (__builtin_popcount(i) <= k) {
            (ans += (dp1[len][i] * add) % MOD) %= MOD;
          }
        }
      }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> l >> r >> k;
  powt[0] = 1LL;
  for (int i = (int)(1); i < (int)(20); i++)
    powt[i] = (1LL * 10 * powt[i - 1]) % MOD;
  cout << (solve(r) - solve(l - 1) + MOD) % MOD << endl;
  return 0;
}

```