#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353;
const int MAXL = 1033, MAXN = 20;
long long dp[MAXN][MAXL], cnt[MAXN][MAXL];
long long cal(long long x, int k) {
  memset(dp, 0, sizeof(dp));
  memset(cnt, 0, sizeof(cnt));
  if (x == 0) {
    return 0;
  }
  int len = 0;
  long long tmp = x;
  vector<int> digits;
  while (tmp) {
    digits.push_back(tmp % 10);
    len++;
    tmp /= 10;
  }
  reverse(digits.begin(), digits.end());
  vector<bitset<10> > masks(len + 1);
  vector<long long> firstNums(len + 1);
  masks[0] = bitset<10>(0);
  for (int i = 1; i <= len; i++) {
    masks[i] = masks[i - 1];
    masks[i].set(digits[i - 1]);
  }
  firstNums[0] = 0;
  firstNums[len] = x;
  for (int i = len - 1; i >= 1; i--) {
    firstNums[i] = firstNums[i + 1] / 10;
  }
  for (int i = 1; i <= len; i++) {
    firstNums[i] %= MOD;
  }
  cnt[0][0] = 1;
  for (int i = 1; i <= len; i++) {
    cnt[i][0] = 1;
    for (int j = 0; j < 1024; j++) {
      bitset<10> dig(j);
      int digLen = dig.count();
      if (digLen > i) {
        continue;
      }
      if (dig == masks[i - 1]) {
        if (cnt[i - 1][j] > 1) {
          for (int k = 0; k < 10; k++) {
            if (dig[k]) {
              dp[i][j] = ((dp[i][j] + (dp[i - 1][j] - firstNums[i - 1]) * 10 +
                           k * (cnt[i - 1][j] - 1)) %
                              MOD +
                          MOD) %
                         MOD;
              cnt[i][j] = (cnt[i][j] + cnt[i - 1][j] - 1) % MOD;
            } else {
              if (j == 0 && k == 0) {
                continue;
              }
              dig[k] = true;
              dp[i][dig.to_ulong()] = ((dp[i][dig.to_ulong()] +
                                        (dp[i - 1][j] - firstNums[i - 1]) * 10 +
                                        k * (cnt[i - 1][j] - 1)) %
                                           MOD +
                                       MOD) %
                                      MOD;
              cnt[i][dig.to_ulong()] =
                  (cnt[i][dig.to_ulong()] + cnt[i - 1][j] - 1) % MOD;
              dig[k] = false;
            }
          }
        }
        if (cnt[i - 1][j]) {
          for (int k = 0; k <= digits[i - 1]; k++) {
            if (dig[k]) {
              dp[i][j] =
                  ((dp[i][j] + firstNums[i - 1] * 10 + k) % MOD + MOD) % MOD;
              cnt[i][j]++;
            } else {
              if (j == 0 && k == 0) {
                continue;
              }
              dig[k] = true;
              dp[i][dig.to_ulong()] =
                  ((dp[i][dig.to_ulong()] + firstNums[i - 1] * 10 + k) % MOD +
                   MOD) %
                  MOD;
              cnt[i][dig.to_ulong()]++;
              dig[k] = false;
            }
          }
        }
      } else {
        for (int k = 0; k < 10; k++) {
          if (dig[k]) {
            dp[i][j] = (dp[i][j] + dp[i - 1][j] * 10 + k * cnt[i - 1][j]) % MOD;
            cnt[i][j] = (cnt[i][j] + cnt[i - 1][j]) % MOD;
          } else {
            if (j == 0 && k == 0) {
              continue;
            }
            dig[k] = true;
            dp[i][dig.to_ulong()] = (dp[i][dig.to_ulong()] + dp[i - 1][j] * 10 +
                                     k * cnt[i - 1][j]) %
                                    MOD;
            cnt[i][dig.to_ulong()] =
                (cnt[i][dig.to_ulong()] + cnt[i - 1][j]) % MOD;
            dig[k] = false;
          }
        }
      }
    }
  }
  long long res = 0;
  for (int j = 0; j < 1024; j++) {
    if (dp[len][j]) {
    }
    if (bitset<10>(j).count() <= k) {
      res = (res + dp[len][j]) % MOD;
    }
  }
  res = (res % MOD + MOD) % MOD;
  return res;
}
int main() {
  long long a, b;
  int k;
  cin >> a >> b >> k;
  cout << ((cal(b, k) - cal(a - 1, k)) % MOD + MOD) % MOD << endl;
  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;
const long long MOD = 998244353;
const int MAXL = 1033, MAXN = 20;
long long dp[MAXN][MAXL], cnt[MAXN][MAXL];
long long cal(long long x, int k) {
  memset(dp, 0, sizeof(dp));
  memset(cnt, 0, sizeof(cnt));
  if (x == 0) {
    return 0;
  }
  int len = 0;
  long long tmp = x;
  vector<int> digits;
  while (tmp) {
    digits.push_back(tmp % 10);
    len++;
    tmp /= 10;
  }
  reverse(digits.begin(), digits.end());
  vector<bitset<10> > masks(len + 1);
  vector<long long> firstNums(len + 1);
  masks[0] = bitset<10>(0);
  for (int i = 1; i <= len; i++) {
    masks[i] = masks[i - 1];
    masks[i].set(digits[i - 1]);
  }
  firstNums[0] = 0;
  firstNums[len] = x;
  for (int i = len - 1; i >= 1; i--) {
    firstNums[i] = firstNums[i + 1] / 10;
  }
  for (int i = 1; i <= len; i++) {
    firstNums[i] %= MOD;
  }
  cnt[0][0] = 1;
  for (int i = 1; i <= len; i++) {
    cnt[i][0] = 1;
    for (int j = 0; j < 1024; j++) {
      bitset<10> dig(j);
      int digLen = dig.count();
      if (digLen > i) {
        continue;
      }
      if (dig == masks[i - 1]) {
        if (cnt[i - 1][j] > 1) {
          for (int k = 0; k < 10; k++) {
            if (dig[k]) {
              dp[i][j] = ((dp[i][j] + (dp[i - 1][j] - firstNums[i - 1]) * 10 +
                           k * (cnt[i - 1][j] - 1)) %
                              MOD +
                          MOD) %
                         MOD;
              cnt[i][j] = (cnt[i][j] + cnt[i - 1][j] - 1) % MOD;
            } else {
              if (j == 0 && k == 0) {
                continue;
              }
              dig[k] = true;
              dp[i][dig.to_ulong()] = ((dp[i][dig.to_ulong()] +
                                        (dp[i - 1][j] - firstNums[i - 1]) * 10 +
                                        k * (cnt[i - 1][j] - 1)) %
                                           MOD +
                                       MOD) %
                                      MOD;
              cnt[i][dig.to_ulong()] =
                  (cnt[i][dig.to_ulong()] + cnt[i - 1][j] - 1) % MOD;
              dig[k] = false;
            }
          }
        }
        if (cnt[i - 1][j]) {
          for (int k = 0; k <= digits[i - 1]; k++) {
            if (dig[k]) {
              dp[i][j] =
                  ((dp[i][j] + firstNums[i - 1] * 10 + k) % MOD + MOD) % MOD;
              cnt[i][j]++;
            } else {
              if (j == 0 && k == 0) {
                continue;
              }
              dig[k] = true;
              dp[i][dig.to_ulong()] =
                  ((dp[i][dig.to_ulong()] + firstNums[i - 1] * 10 + k) % MOD +
                   MOD) %
                  MOD;
              cnt[i][dig.to_ulong()]++;
              dig[k] = false;
            }
          }
        }
      } else {
        for (int k = 0; k < 10; k++) {
          if (dig[k]) {
            dp[i][j] = (dp[i][j] + dp[i - 1][j] * 10 + k * cnt[i - 1][j]) % MOD;
            cnt[i][j] = (cnt[i][j] + cnt[i - 1][j]) % MOD;
          } else {
            if (j == 0 && k == 0) {
              continue;
            }
            dig[k] = true;
            dp[i][dig.to_ulong()] = (dp[i][dig.to_ulong()] + dp[i - 1][j] * 10 +
                                     k * cnt[i - 1][j]) %
                                    MOD;
            cnt[i][dig.to_ulong()] =
                (cnt[i][dig.to_ulong()] + cnt[i - 1][j]) % MOD;
            dig[k] = false;
          }
        }
      }
    }
  }
  long long res = 0;
  for (int j = 0; j < 1024; j++) {
    if (dp[len][j]) {
    }
    if (bitset<10>(j).count() <= k) {
      res = (res + dp[len][j]) % MOD;
    }
  }
  res = (res % MOD + MOD) % MOD;
  return res;
}
int main() {
  long long a, b;
  int k;
  cin >> a >> b >> k;
  cout << ((cal(b, k) - cal(a - 1, k)) % MOD + MOD) % MOD << endl;
  return 0;
}

```