#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
long long l, r;
int n, m, k;
int dp[2][2][20][1 << (10 + 2)], dpS[2][2][20][1026];
int digitsA[20], digitsB[20];
int countMask(int x) {
  int ans = 0;
  for (int i = 0; i <= 9; ++i) {
    if (x & (1 << i)) ++ans;
  }
  return ans;
}
int sum(int a, int b) { return (a % MOD + b % MOD) % MOD; }
int multp(long long a, long long b) { return (a % MOD * b % MOD) % MOD; }
int shiftPow(int i, int idx) {
  long long p = 1;
  for (int i = n; i > idx; --i) {
    p *= 10;
  }
  return multp(i, p);
}
int go(int low, int high, int idx, int mask) {
  if (dp[low][high][idx][mask] != -1) {
    return dp[low][high][idx][mask];
  }
  if (idx == n) {
    if (countMask(mask) <= k) {
      return dp[low][high][idx][mask] = 1;
    }
    return dp[low][high][idx][mask] = 0;
  }
  int res = 0;
  int l = 0, h = 9;
  if (low) l = digitsA[idx];
  if (high) h = digitsB[idx];
  for (int i = l; i <= h; ++i) {
    int nlow = (low && i == digitsA[idx]) ? 1 : 0;
    int nhigh = (high && i == digitsB[idx]) ? 1 : 0;
    int nmask = mask | (1 << i);
    if (countMask(nmask) <= k) {
      if (low && i == 0 && idx < n - m + 1) {
        nmask = 0;
      }
      res = sum(res, go(nlow, nhigh, idx + 1, nmask));
      dpS[low][high][idx][mask] =
          sum(dpS[low][high][idx][mask],
              multp(shiftPow(i, idx + 1), dp[nlow][nhigh][idx + 1][nmask]));
      dpS[low][high][idx][mask] =
          sum(dpS[low][high][idx][mask], dpS[nlow][nhigh][idx + 1][nmask]);
    }
  }
  if (idx == 0) {
    printf("%d\n", dpS[1][1][0][0]);
  }
  return dp[low][high][idx][mask] = res;
}
void setDigits(long long x, int digits[], int &sz) {
  vector<int> X;
  while (x) {
    X.push_back(x % 10);
    x /= 10;
  }
  sz = X.size();
  for (int i = 0; i < sz; ++i) {
    digits[sz - 1 - i] = X[i];
  }
}
int main() {
  scanf("%lld %lld %d", &l, &r, &k);
  setDigits(l, digitsA, m);
  setDigits(r, digitsB, n);
  if (m < n) {
    int tmp[20];
    memcpy(tmp, digitsA, sizeof(tmp));
    memset(digitsA, 0, sizeof(digitsA));
    for (int i = 0; i < m; ++i) {
      digitsA[n - m + i] = tmp[i];
    }
  }
  memset(dp, -1, sizeof(dp));
  go(1, 1, 0, 0);
  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>
using namespace std;
const int MOD = 998244353;
long long l, r;
int n, m, k;
int dp[2][2][20][1 << (10 + 2)], dpS[2][2][20][1026];
int digitsA[20], digitsB[20];
int countMask(int x) {
  int ans = 0;
  for (int i = 0; i <= 9; ++i) {
    if (x & (1 << i)) ++ans;
  }
  return ans;
}
int sum(int a, int b) { return (a % MOD + b % MOD) % MOD; }
int multp(long long a, long long b) { return (a % MOD * b % MOD) % MOD; }
int shiftPow(int i, int idx) {
  long long p = 1;
  for (int i = n; i > idx; --i) {
    p *= 10;
  }
  return multp(i, p);
}
int go(int low, int high, int idx, int mask) {
  if (dp[low][high][idx][mask] != -1) {
    return dp[low][high][idx][mask];
  }
  if (idx == n) {
    if (countMask(mask) <= k) {
      return dp[low][high][idx][mask] = 1;
    }
    return dp[low][high][idx][mask] = 0;
  }
  int res = 0;
  int l = 0, h = 9;
  if (low) l = digitsA[idx];
  if (high) h = digitsB[idx];
  for (int i = l; i <= h; ++i) {
    int nlow = (low && i == digitsA[idx]) ? 1 : 0;
    int nhigh = (high && i == digitsB[idx]) ? 1 : 0;
    int nmask = mask | (1 << i);
    if (countMask(nmask) <= k) {
      if (low && i == 0 && idx < n - m + 1) {
        nmask = 0;
      }
      res = sum(res, go(nlow, nhigh, idx + 1, nmask));
      dpS[low][high][idx][mask] =
          sum(dpS[low][high][idx][mask],
              multp(shiftPow(i, idx + 1), dp[nlow][nhigh][idx + 1][nmask]));
      dpS[low][high][idx][mask] =
          sum(dpS[low][high][idx][mask], dpS[nlow][nhigh][idx + 1][nmask]);
    }
  }
  if (idx == 0) {
    printf("%d\n", dpS[1][1][0][0]);
  }
  return dp[low][high][idx][mask] = res;
}
void setDigits(long long x, int digits[], int &sz) {
  vector<int> X;
  while (x) {
    X.push_back(x % 10);
    x /= 10;
  }
  sz = X.size();
  for (int i = 0; i < sz; ++i) {
    digits[sz - 1 - i] = X[i];
  }
}
int main() {
  scanf("%lld %lld %d", &l, &r, &k);
  setDigits(l, digitsA, m);
  setDigits(r, digitsB, n);
  if (m < n) {
    int tmp[20];
    memcpy(tmp, digitsA, sizeof(tmp));
    memset(digitsA, 0, sizeof(digitsA));
    for (int i = 0; i < m; ++i) {
      digitsA[n - m + i] = tmp[i];
    }
  }
  memset(dp, -1, sizeof(dp));
  go(1, 1, 0, 0);
  return 0;
}

```