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 P = 998244353;
vector<int> L, R;
pair<long long, long long> f[25][1500];
long long l, r, dx[25];
int k;
pair<long long, long long> dfs(vector<int> w, int pos, int mask, int cnt,
                               int op) {
  if (pos < 0) return make_pair(0, 0);
  if (!op && ~f[pos][mask].first) return f[pos][mask];
  long long mx = (op ? w[pos] : 9), res = 0, num = 0;
  if (!pos) {
    for (int i = 0; i <= mx; i++)
      if (mask & (1 << i))
        res += i, num++;
      else if (cnt < k)
        res += i, num++;
    if (!op) f[pos][mask] = make_pair(res, num);
    return make_pair(res, num);
  }
  for (int i = 0; i <= mx; i++)
    if (mask & (1 << i) || cnt < k) {
      pair<long long, long long> p;
      if (mask & (1 << i) || !mask && !i)
        p = dfs(w, pos - 1, mask, cnt, op & (i == mx));
      else
        p = dfs(w, pos - 1, mask | (1 << i), cnt + 1, op & (i == mx));
      res = ((long long)i * dx[pos] % P * p.second % P + res + p.first) % P;
      num = (num + p.second) % P;
    }
  if (!op) f[pos][mask] = make_pair(res, num);
  return make_pair(res, num);
}
int main() {
  dx[0] = 1;
  for (int i = 1; i <= 18; i++) dx[i] = (dx[i - 1] * 10) % P;
  scanf("%lld%lld%d", &l, &r, &k);
  l--;
  while (l) L.push_back(l % 10), l /= 10;
  while (r) R.push_back(r % 10), r /= 10;
  memset(f, -1, sizeof(f));
  pair<long long, long long> ansL = dfs(L, L.size() - 1, 0, 0, 1);
  pair<long long, long long> ansR = dfs(R, R.size() - 1, 0, 0, 1);
  printf("%lld\n", (ansR.first - ansL.first + P) % P);
  return 0;
}
