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;
pair<long long, long long> dp[1100][20];
int bitcnt[1100];
long long p10[21];
string a;
int n, k;
pair<long long, long long> dfs(int bi, int pos, int flag, int leading) {
  if (pos == -1) return make_pair(0, 1);
  if (dp[bi][pos].second != -1 && !flag && !leading) {
    return dp[bi][pos];
  }
  long long ans = 0;
  long long cnt = 0;
  int upper = (flag ? a[n - pos - 1] - '0' : 9);
  for (int i = 0; i <= upper; i++) {
    int nextstate = (bi | (1 << i));
    if ((bi & (1 << i)) == 0 && !(leading && i == 0)) {
      if (bitcnt[nextstate] > k) continue;
      pair<long long, long long> p =
          dfs(nextstate, pos - 1, flag && (i == upper), leading && (i == 0));
      cnt = (cnt + p.second) % 998244353;
      ans = (ans +
             ((((p.second * i) % 998244353) * p10[pos]) % 998244353 + p.first) %
                 998244353) %
            998244353;
    } else {
      pair<long long, long long> p =
          dfs(bi, pos - 1, flag && (i == upper), leading && (i == 0));
      cnt = (cnt + p.second) % 998244353;
      ans = (ans +
             ((((p.second * i) % 998244353) * p10[pos]) % 998244353 + p.first) %
                 998244353) %
            998244353;
    }
  }
  if (!flag && !leading) {
    dp[bi][pos] = make_pair(ans % 998244353, cnt % 998244353);
  }
  return make_pair(ans % 998244353, cnt % 998244353);
}
long long solve(long long num) {
  a = to_string(num);
  n = (int)a.length();
  pair<long long, long long> p = dfs(0, n - 1, 1, 1);
  return p.first % 998244353;
}
int main() {
  long long l, r;
  int i, j;
  p10[0] = 1;
  for (i = 1; i <= 20; i++) {
    p10[i] = (p10[i - 1] * 10) % 998244353;
  }
  for (i = 0; i < 1100; i++) {
    for (j = 0; j < 20; j++) {
      dp[i][j] = make_pair(0, -1);
    }
  }
  bitcnt[0] = 0;
  bitcnt[1] = 1;
  for (i = 2; i < 1100; i++) bitcnt[i] = bitcnt[i - (i & -i)] + 1;
  cin >> l >> r >> k;
  cout << (solve(r) - solve(l - 1) + 998244353) % 998244353 << endl;
  return 0;
}
