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;
long long power[11][20];
long long contributesToAnswer[1 << 10];
string getNthString(long long n, vector<int> digits, int length) {
  string answer = "";
  for (int i = length - 1; i >= 0; i--) {
    long long perDigit = power[digits.size()][i];
    long long thisDigit = n / perDigit;
    answer += digits[thisDigit] + '0';
    n %= perDigit;
  }
  return answer;
}
long long getPosition(string s, vector<int> digits) {
  long long answer = 0;
  for (int i = 0; i < s.size(); i++) {
    for (int j = 0; j < digits.size(); j++) {
      if (digits[j] == s[i] - '0') {
        answer += j * power[digits.size()][s.size() - i - 1];
        answer %= 998244353LL;
        break;
      }
    }
  }
  return answer;
}
long long findSumUpTo(string s, vector<int> digits) {
  long long answer = 0;
  long long prevPossible = 0;
  for (int i = 0; i < s.size(); i++) {
    long long multBelow = power[digits.size()][s.size() - i - 1] % 998244353LL;
    for (int j = 0; j < digits.size(); j++) {
      answer += (((digits[j] * prevPossible) % 998244353LL * multBelow) %
                 998244353LL) *
                (power[10][s.size() - i - 1] % 998244353LL);
      answer %= 998244353LL;
    }
    int index = 0;
    for (int j = digits[index]; j < s[i] - '0'; j = digits[++index]) {
      answer += ((multBelow * j) % 998244353LL) *
                (power[10][s.size() - i - 1] % 998244353LL);
      answer %= 998244353LL;
    }
    prevPossible *= digits.size();
    prevPossible += index;
    prevPossible %= 998244353LL;
    answer += (((s[i] - '0') *
                getPosition(s.substr(i + 1, s.size() - (i + 1)), digits)) %
               998244353LL) *
              (power[10][s.size() - i - 1] % 998244353LL);
    answer %= 998244353LL;
  }
  answer += stoll(s);
  answer %= 998244353LL;
  return answer;
}
long long binarySearch(string target, vector<int> digits) {
  long long first = 0;
  if (digits[0] == 0) {
    first = power[digits.size()][target.size() - 1];
  }
  long long start = first;
  long long end = power[digits.size()][target.size()] - 1;
  while (start <= end) {
    long long mid = (start + end) / 2;
    string s = getNthString(mid, digits, target.size());
    if (s < target) {
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }
  if (end < 0) return 0;
  return findSumUpTo(getNthString(end, digits, target.size()), digits);
}
string l, r;
int k;
int main() {
  if (fopen("FILENAME.in", "r")) {
    freopen("FILENAME.in", "r", stdin);
    freopen("FILENAME.out", "w", stdout);
  }
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  for (int i = 1; i <= 10; i++) {
    power[i][0] = 1;
    for (int j = 1; j < 19; j++) {
      power[i][j] = power[i][j - 1] * i;
    }
    power[i][19] = power[i][18] * 2;
  }
  long long a, b;
  cin >> a >> b;
  l = to_string(a);
  r = to_string(b + 1);
  cin >> k;
  long long answer = 0;
  for (int i = 2; i < (1 << 10); i++) {
    vector<int> digits;
    for (int j = 0; j < 10; j++) {
      if ((i & (1 << j))) {
        digits.push_back(j);
      }
    }
    if (digits.size() > k) continue;
    long long beforeAnswer = answer;
    if (l.size() == r.size()) {
      answer += binarySearch(r, digits) - binarySearch(l, digits);
      answer %= 998244353LL;
    } else {
      answer += findSumUpTo(getNthString(power[digits.size()][l.size()] - 1,
                                         digits, l.size()),
                            digits) -
                binarySearch(l, digits);
      answer %= 998244353LL;
      for (int i = l.size() + 1; i <= r.size() - 1; i++) {
        long long prev = answer;
        answer +=
            findSumUpTo(getNthString(power[digits.size()][i] - 1, digits, i),
                        digits) -
            (digits[0] == 0
                 ? (findSumUpTo(
                       getNthString(power[digits.size()][i - 1] - 1, digits, i),
                       digits))
                 : 0);
        answer %= 998244353LL;
      }
      answer += binarySearch(r, digits) -
                (digits[0] == 0
                     ? findSumUpTo(
                           getNthString(power[digits.size()][r.size() - 1] - 1,
                                        digits, r.size()),
                           digits)
                     : 0);
      answer %= 998244353LL;
    }
    for (int j = 0; j < (1 << 10); j++) {
      bool bad = false;
      for (int m = 0; m < 10; m++) {
        if (((j & (1 << m)) > 0) && ((i & (1 << m)) == 0)) {
          bad = true;
          break;
        }
      }
      if (bad) continue;
      answer -= contributesToAnswer[j];
      answer %= 998244353LL;
      answer += 998244353LL;
      answer %= 998244353LL;
    }
    contributesToAnswer[i] =
        (((answer - beforeAnswer) % 998244353LL) + 998244353LL) % 998244353LL;
  }
  cout << answer << endl;
}
