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;
const int MOD = 998244353;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long lcm(long long a, long long b) { return a * b / gcd(a, b); }
long long powers[20];
long long l, r;
int k;
pair<long long, long long> dp[20][1026][11];
pair<long long, long long> solve(int digitsCnt, int msk, int maxVal,
                                 int onesCntInMsk, vector<int>& v) {
  if (digitsCnt == v.size()) {
    return {0, 1};
  }
  pair<long long, long long>& ret = dp[digitsCnt][msk][maxVal];
  if (~ret.first && ~ret.second) return ret;
  long long ansSum = 0, ansCnt = 0;
  for (int i = 0; i <= min(maxVal, 9); i++) {
    int newMask = ((msk == 0 && i == 0) ? 0 : ((1 << i) | msk));
    int newMaxVal = (i == maxVal ? v[digitsCnt + 1] : 10);
    int newCnt = onesCntInMsk + (newMask > msk);
    if (newCnt > k) continue;
    pair<long long, long long> nxt =
        solve(digitsCnt + 1, newMask, newMaxVal, newCnt, v);
    long long sum = nxt.first, cnt = nxt.second;
    ansSum =
        ((ansSum + ((i * powers[v.size() - digitsCnt - 1]) % MOD * cnt) % MOD) %
             MOD +
         sum) %
        MOD;
    ansCnt = (ansCnt + cnt) % MOD;
  }
  return ret = {ansSum, ansCnt};
}
long long getSum(long long v) {
  memset(dp, -1, sizeof(dp));
  vector<int> arr;
  while (v) {
    arr.push_back(v % 10);
    v /= 10;
  }
  if (arr.size() == 0) arr.push_back(0);
  reverse(arr.begin(), arr.end());
  pair<long long, long long> ret = solve(0, 0, arr[0], 0, arr);
  return ret.first;
}
void init() {
  powers[0] = 1;
  for (int i = 1; i < 19; i++) powers[i] = powers[i - 1] * 10;
}
int main() {
  init();
  cin >> l >> r >> k;
  cout << (getSum(r) - getSum(l - 1) + MOD) % MOD << endl;
  return 0;
}
