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 long long MOD = 998244353;
long long sum(long long x, long long y) {
  return x + y < MOD ? x + y : x + y - MOD;
}
long long &add(long long &x, long long y) { return x = sum(x, y); }
long long dif(long long x, long long y) {
  return x - y < 0 ? x - y + MOD : x - y;
}
long long &sub(long long &x, long long y) { return x = dif(x, y); }
long long mul(long long x, long long y) { return x * y % MOD; }
const long long D = 10;
map<pair<long long, long long>, pair<long long, long long>> kek;
pair<long long, long long> f(long long x, long long mask) {
  if (x == 0) {
    return {1, 0};
  }
  if (kek.count({x, mask})) {
    return kek[{x, mask}];
  }
  pair<long long, long long> &res = kek[{x, mask}] = {0, 0};
  long long p = 1;
  while (x / D >= p) {
    p *= D;
  }
  for (long long d = 0; p * d <= x; ++d) {
    if ((mask >> d & 1) && (x - p * d >= p / 10 || (mask & 1))) {
      auto rd = f(min(p - 1, x - p * d), mask);
      add(res.first, rd.first);
      add(res.second, mul(rd.first, mul(p, d)));
      add(res.second, rd.second);
    }
  }
  return res;
}
long long cnt_ones(long long x) {
  long long res = 0;
  while (x) {
    res += x & 1;
    x >>= 1;
  }
  return res;
}
long long dp[1 << D];
long long fd(long long x, long long k) {
  long long res = 0;
  for (long long mask = 0; ~mask >> D & 1; ++mask) {
    if (cnt_ones(mask) <= k) {
      if (mask & 1) {
        dp[mask] = f(x, mask).second;
      } else {
        dp[mask] = 0;
        for (long long p = 10; p / 10 <= x; p *= 10) {
          add(dp[mask], f(min(x, p - 1), mask).second);
        }
      }
      for (long long sm = mask - 1 & mask; sm; sm = sm - 1 & mask) {
        sub(dp[mask], dp[sm]);
      }
      add(res, dp[mask]);
    }
  }
  return res;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long l, r, k;
  cin >> l >> r >> k;
  cout << dif(fd(r, k), fd(l - 1, k)) << '\n';
  return 0;
}
