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 mod = 998244353;
inline int read() {
  int w = 1, s = 0;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return w * s;
}
long long f[21][1 << 12], g[21][1 << 12];
long long l, r, k, mi[100];
int bit[100010];
inline long long DFS2(int pos, int Sta, int app, int lim) {
  if (!pos) {
    int tmp = __builtin_popcount(Sta);
    if (tmp <= k && app)
      return 1;
    else
      return 0;
  }
  if (~f[pos][Sta] && (!lim)) return f[pos][Sta];
  int Mx = 9;
  if (lim) Mx = bit[pos];
  long long res = 0;
  for (register int i = 0; i <= Mx; ++i) {
    int nwSta = Sta;
    if (app) nwSta |= (1 << i);
    if (i) nwSta |= (1 << i);
    res += 1ll * DFS2(pos - 1, nwSta, app | (i != 0), lim & (i == Mx)) % mod;
  }
  if (!lim) f[pos][Sta] = res;
  return res;
}
inline long long DFS1(int pos, int Sta, int app, int lim) {
  if (!pos) {
    int tmp = __builtin_popcount(Sta);
    return 0;
  }
  if (~g[pos][Sta] && (!lim)) return g[pos][Sta];
  int Mx = 9;
  if (lim) Mx = bit[pos];
  long long res = 0;
  for (register int i = 0; i <= Mx; ++i) {
    int nwSta = Sta;
    if (app) nwSta |= (1 << i);
    if (i) nwSta |= (1 << i);
    res += 1ll * DFS2(pos - 1, nwSta, app | (i != 0), lim & (i == Mx)) * i %
           mod * mi[pos - 1] % mod;
    res %= mod;
    res += DFS1(pos - 1, nwSta, app | (i != 0), lim & (i == Mx));
    res %= mod;
  }
  if (!lim) g[pos][Sta] = res;
  return res;
}
inline long long Solve(long long now) {
  int cnt = 0;
  while (now) {
    bit[++cnt] = now % 10;
    now /= 10;
  }
  return DFS1(cnt, 0, 0, 1);
}
int main() {
  memset(f, -1, sizeof(f));
  memset(g, -1, sizeof(g));
  cin >> l >> r >> k;
  mi[0] = 1;
  for (register int i = 1; i <= 21; ++i) mi[i] = 1ll * mi[i - 1] * 10 % mod;
  cout << ((Solve(r) - Solve(l - 1)) % mod + mod) % mod;
  return 0;
}
