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>
int debugnum = 0;
using namespace std;
const long long MOD = 998244353;
inline long long add(long long a, long long b) { return (a + b) % MOD; }
int toint(bitset<10> bs) {
  int ret = 0;
  for (int i = 9; i >= 0; i--) {
    ret = (ret << 1) | bs[i];
  }
  return ret;
}
long long chpow(long long a, long long b) {
  long long ret = 1;
  for (long long i = 1; i <= b; i <<= 1) {
    if (i & b) ret = ret * a % MOD;
    a = a * a % MOD;
  }
  return ret;
}
long long DP[20][10][1024];
long long sum[20][10][1024];
void init() {
  memset(DP, 0, sizeof DP);
  memset(sum, 0, sizeof sum);
  for (int i = (0); i < (10); i++) DP[0][i][1 << i] = 1;
  for (int i = (0); i < (10); i++) sum[0][i][1 << i] = i;
  for (int i = (1); i < (19); i++) {
    for (int j = (0); j < (10); j++) {
      for (int S = (0); S < (1024); S++) {
        long long &tmp = DP[i][j][S];
        long long &tmp2 = sum[i][j][S];
        bitset<10> bs = S, bs1;
        if (bs[j] == 0) continue;
        bs1 = bs;
        bs1[j] = 0;
        for (int j1 = (0); j1 < (10); j1++) {
          tmp += DP[i - 1][j1][S] + DP[i - 1][j1][toint(bs1)];
          tmp2 += sum[i - 1][j1][S] + sum[i - 1][j1][toint(bs1)];
          tmp %= MOD;
          tmp2 %= MOD;
        }
        tmp2 += tmp * (j * chpow(10, i) % MOD) % MOD;
        tmp2 %= MOD;
      }
    }
  }
}
long long solve(long long N, long long K, bitset<10> S0, long long extra = 0) {
  long long ret = 0;
  long long Ai = N, p = 1, i = 0;
  while (Ai >= 10) Ai /= 10, p *= 10, i++;
  if (i == 0) {
    long long cnt = 0;
    for (int i = (0); i < (Ai + 1); i++) {
      if ((S0 | bitset<10>(1 << i)).count() <= K) cnt += i + extra;
    }
    cnt %= MOD;
    return cnt;
  }
  if (S0.count() == 0) {
    unsigned long long p = 1;
    for (int i = (0); i < (19); i++) {
      for (int j = (1); j < (10); j++) {
        if ((1LL + j) * p > N) break;
        for (int S1 = (0); S1 < (1024); S1++) {
          bitset<10> S = S1;
          if (S.count() <= K) {
            ret += sum[i][j][S1];
            ret %= MOD;
          }
        }
      }
      p *= 10;
    }
  } else {
    for (int j = (0); j < (Ai); j++) {
      for (int S1 = (0); S1 < (1024); S1++) {
        bitset<10> S = bitset<10>(S1) | S0;
        if (S.count() <= K) {
          ret += DP[i][j][S1] * extra % MOD + sum[i][j][S1];
          ret %= MOD;
        }
      }
    }
  }
  S0[Ai] = 1;
  if ((N - Ai * p) * 10 < p) S0[0] = 1;
  if (N >= 10) ret += solve(N - Ai * p, K, S0, (extra + Ai * p % MOD) % MOD);
  ret %= MOD;
  return ret;
}
int main() {
  init();
  long long N, M, K;
  while (cin >> N >> M >> K) {
    N--;
    long long output = (MOD + solve(M, K, 0) - solve(N, K, 0)) % MOD;
    cout << output << endl;
  }
  return 0;
}
