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 double eps = 1e-8;
int dcmp(double x) {
  if (x < -eps)
    return -1;
  else
    return x > eps;
}
const int N = 1050;
const int mod = 998244353;
int n;
int k;
long long lft, rht;
int cb[N];
long long cnt[20][N][2];
long long dp[20][N][2];
long long val[20];
int f[20];
long long calc(long long x) {
  int len = 0;
  while (x) {
    f[len++] = x % 10;
    x /= 10;
  }
  long long ans = 0;
  for (int i = 0; i < (int)(len); i++) {
    for (int st = 0; st < (int)((1 << 10)); st++) {
      if (cb[st] > k) continue;
      ans += dp[i][st][1];
      ans %= mod;
    }
  }
  long long p = 0;
  int st = 0;
  for (int i = (int)(len)-1; i >= 0; --i) {
    for (int v = 0; v < (int)(f[i]); v++) {
      if (i == len - 1 && v == 0) continue;
      long long pp = p + val[i] * v;
      pp %= mod;
      for (int tt = 0; tt < (int)((1 << 10)); tt++) {
        int ut = st | tt | (1 << v);
        if (cb[ut] > k) continue;
        long long tmp = pp * cnt[i][tt][0] + dp[i][tt][0];
        ans = (ans + tmp) % mod;
      }
    }
    p += val[i] * f[i];
    p %= mod;
    st |= (1 << f[i]);
  }
  if (cb[st] <= k) {
    ans += p;
    ans %= mod;
  }
  return ans;
}
long long solve() {
  cb[0] = 0;
  for (int i = (1); i < ((1 << 10)); ++i) {
    cb[i] = cb[i & (i - 1)] + 1;
  }
  val[0] = 1;
  for (int i = (1); i < (20); ++i) {
    val[i] = val[i - 1] * 10 % mod;
  }
  memset(dp, 0, sizeof(dp));
  memset(cnt, 0, sizeof(cnt));
  cnt[0][0][0] = 1;
  for (int i = 0; i < (int)(19); i++) {
    for (int st = 0; st < (int)((1 << 10)); st++) {
      if (cnt[i][st][0] == 0) {
        continue;
      }
      for (int b = 0; b < (int)(10); b++) {
        int tt = (st | (1 << b));
        dp[i + 1][tt][0] += val[i] * b * cnt[i][st][0];
        dp[i + 1][tt][0] += dp[i][st][0];
        dp[i + 1][tt][0] %= mod;
        cnt[i + 1][tt][0] += cnt[i][st][0];
        cnt[i + 1][tt][0] %= mod;
        if (b != 0) {
          dp[i + 1][tt][1] += val[i] * b * cnt[i][st][0];
          dp[i + 1][tt][1] += dp[i][st][0];
          dp[i + 1][tt][1] %= mod;
          cnt[i + 1][tt][1] += cnt[i][st][0];
          cnt[i + 1][tt][1] %= mod;
        }
      }
    }
  }
  long long ans = calc(rht) - calc(lft - 1);
  ans = (ans % mod + mod) % mod;
  return ans;
}
int main(int argc, char *argv[]) {
  while (scanf("%I64d"
               "%I64d"
               "%d",
               &lft, &rht, &k) != EOF) {
    long long ret = solve();
    printf(
        "%I64d"
        "\n",
        ret);
  }
  return 0;
}
