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.
#include <bits/stdc++.h>
using namespace std;
void read(long long &number) {
  bool negative = false;
  long long c;
  number = 0;
  c = getchar();
  while (c == ' ' || c == '\n') c = getchar();
  if (c == '-') {
    negative = true;
    c = getchar();
  }
  for (; (c > 47 && c < 58); c = getchar()) number = number * 10 + c - 48;
  if (negative) number = -number;
}
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &a) {
  return os << '(' << a.first << ", " << a.second << ')';
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) {
  os << '[';
  for (unsigned long long i = 0; i < a.size(); i++)
    os << a[i] << (i < a.size() - 1 ? ", " : "");
  os << ']';
  return os;
}
template <class T>
ostream &operator<<(ostream &os, const set<T> &a) {
  os << '{';
  for (typename set<T>::iterator it = a.begin(); it != a.end(); it++) {
    typename set<T>::iterator jt = it;
    os << *it << (++jt != a.end() ? ", " : "");
  }
  os << '}';
  return os;
}
template <class T1, class T2>
ostream &operator<<(ostream &os, map<T1, T2> &a) {
  os << "{\n";
  for (typename map<T1, T2>::iterator it = a.begin(); it != a.end(); it++) {
    typename map<T1, T2>::iterator jt = it;
    os << "  " << it->first << ": " << it->second
       << (++jt != a.end() ? ",\n" : "\n");
  }
  os << '}';
  return os;
}
const long long mod = 998244353;
long long binPow(long long a, long long q) {
  long long ret = 1;
  while (q) {
    if (q & 1) ret = ret * a % mod;
    a = a * a % mod;
    q >>= 1LL;
  }
  return ret;
}
long long l, r, diff;
string L, R;
pair<long long, long long> dp[20][2][2][2][1024];
long long ans = 0;
pair<long long, long long> cal(long long pos, bool Lx, bool Rx, bool zer,
                               long long mask) {
  if (__builtin_popcountll(mask) > diff) return make_pair(0, 0);
  if (pos == R.size()) return make_pair(0, 1);
  auto &ret = dp[pos][Lx][Rx][zer][mask];
  if (ret.second != -1) return ret;
  ret = make_pair(0LL, 0LL);
  long long lo = 0, hi = 9;
  if (Lx) lo = L[pos] - '0';
  if (Rx) hi = R[pos] - '0';
  for (long long i = (long long)(lo); i <= (long long)(hi); i++) {
    long long nmask = mask;
    if (zer == 0 || (zer == 1 && i)) {
      nmask |= (1 << i);
    }
    auto rec = cal(pos + 1, min(Lx, i == lo), min(Rx, i == hi),
                   min(zer, (i == 0)), nmask);
    ret.second = (ret.second + rec.second) % mod;
    ret.first = (ret.first + rec.first +
                 binPow(10, R.size() - pos - 1) * i % mod * rec.second % mod) %
                mod;
  }
  return ret;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> l >> r >> diff;
  while (l) {
    L += char(l % 10 + '0');
    l /= 10;
  }
  while (r) {
    R += char(r % 10 + '0');
    r /= 10;
  }
  reverse(L.begin(), L.end());
  reverse(R.begin(), R.end());
  while (L.size() < R.size()) L = "0" + L;
  memset(dp, -1, sizeof(dp));
  cout << cal(0, 1, 1, 1, 0).first << '\n';
}
