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 = (long long)998244353;
const long double PI = 3.141592653589793238462643383279502884197;
long long fac[1] = {1}, inv[1] = {1};
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long mp(long long a, long long b) {
  long long ret = 1;
  while (b) {
    if (b & 1) ret = ret * a % MOD;
    a = a * a % MOD;
    b >>= 1;
  }
  return ret;
}
long long cmb(long long r, long long c) {
  return fac[r] * inv[c] % MOD * inv[r - c] % MOD;
}
priority_queue<int, vector<int>, greater<int>> pq;
vector<int> v;
long long rotn[19][3][2][1024];
long long dp[19][3][2][1024];
long long two[19];
char s[19];
int n;
int k;
long long aa = 0;
long long ggo(int o, int ti, int ff, int bit) {
  if (o >= n) return 0;
  if (o == -1) {
    int cnt = __builtin_popcount(bit);
    return ti <= 1 && cnt <= k;
  }
  if (rotn[o][ti][ff][bit] != -1) return rotn[o][ti][ff][bit];
  long long ret = 0;
  for (int i = ff; i < 10; i++) {
    int ne = ti;
    if (ti == 1) {
      if (i > s[o])
        ne = 2;
      else if (i < s[o])
        ne = 0;
    }
    ret += ggo(o - 1, ne, 0, bit | (1 << i));
    aa %= MOD;
  }
  return rotn[o][ti][ff][bit] = ret % MOD;
}
long long cal(long long a) {
  n = 0;
  aa = 0;
  while (a) {
    s[n++] = a % 10;
    a /= 10;
  }
  memset(rotn, -1, sizeof(rotn));
  memset(dp, 0, sizeof(dp));
  long long ret = 0;
  for (int o = n - 1; o >= 0; o--) {
    dp[o][o == n - 1][1][0] = 1;
    for (int ti = 0; ti < 3; ti++) {
      for (int ff = 0; ff < 2; ff++) {
        for (int bit = 0; bit < 1024; bit++) {
          for (int i = ff; i < 10; i++) {
            int ne = ti;
            if (ti == 1) {
              if (i > s[o])
                ne = 2;
              else if (i < s[o])
                ne = 0;
            }
            if (o)
              dp[o - 1][ne][0][bit | (1 << i)] =
                  (dp[o][ti][ff][bit] + dp[o - 1][ne][0][bit | (1 << i)]) % MOD;
            ret += ggo(o - 1, ne, 0, bit | (1 << i)) * dp[o][ti][ff][bit] %
                   MOD * two[o] % MOD * i % MOD;
            ret %= MOD;
          }
        }
      }
    }
  }
  return ret;
}
int main() {
  two[0] = 1;
  for (int i = 1; i < 19; i++) two[i] = two[i - 1] * 10 % MOD;
  long long l, r;
  scanf("%lld %lld %d", &l, &r, &k);
  printf("%lld\n", (cal(r) - cal(l - 1) + MOD) % MOD);
}
