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;
long long int M = 998244353;
int d[20];
long long int pp[20];
long long int dp[20][1 << 10][2][10][2];
inline int setbit(int n, int i) { return (n | (1 << i)); }
pair<long long int, long long int> f(int i, int x, int k, int z,
                                     long long int m, long long int n) {
  if (__builtin_popcount(x) > z) return make_pair(0ll, 0ll);
  if (i < 0) return make_pair(1ll, m);
  if (dp[i][x][k][m][0] == -1) {
    int p = k ? d[i] : 9;
    long long int r = 0, w = 0, v = (m * pp[i + 1]) % M;
    pair<long long int, long long int> pr;
    for (long long int j = 0; j <= p; j++) {
      int q = (d[i] == j) ? k : 0;
      int y = (j == 0 && n == 0) ? 0 : setbit(x, j);
      pr = f(i - 1, y, q, z, j, n * 10 + j);
      w = (w + pr.first) % M;
      r = (r + pr.second) % M;
    }
    r = (r + (w * v) % M) % M;
    dp[i][x][k][m][0] = w;
    dp[i][x][k][m][1] = r;
  }
  pair<long long int, long long int> pr =
      make_pair(dp[i][x][k][m][0], dp[i][x][k][m][1]);
  return pr;
}
int getDigits(long long int n) {
  int i = 0;
  while (n) {
    d[i++] = n % 10;
    n /= 10;
  }
  return i;
}
void calc(int n) {
  pp[0] = 1;
  for (int i = 1; i <= n; i++) pp[i] = pp[i - 1] * 10;
  for (int i = 1; i <= n; i++) pp[i] %= M;
}
int main() {
  int k;
  long long int l, r;
  calc(18);
  cin >> l >> r >> k;
  int len = getDigits(r);
  memset(dp, -1, sizeof(dp));
  long long int y = 0, x = f(len - 1, 0, 1, k, 0, 0).second;
  if (l > 1) {
    len = getDigits(l - 1);
    memset(dp, -1, sizeof(dp));
    y = f(len - 1, 0, 1, k, 0, 0).second;
  }
  cout << (x - y + M) % M << endl;
  return 0;
}
