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>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")
#pragma comment(linker, "/STACK:256000000")
#pragma warning(disable : 4996)
using namespace std;
const int inf = 1e9;
const long long llinf = 1e18, mod = 998244353;
const long double pi =
    3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825;
template <typename T>
bool uin(T &a, T b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename T>
bool uax(T &a, T b) {
  if (b > a) {
    a = b;
    return 1;
  }
  return 0;
}
template <class iterator>
void output(iterator begin, iterator end, char p = ' ', ostream &out = cout) {
  while (begin != end) {
    out << (*begin) << p;
    begin++;
  }
  out << '\n';
}
template <class T>
void output(T x, char p = ' ', ostream &out = cout) {
  output(x.begin(), x.end(), p, out);
}
mt19937 rnd(time(NULL));
long long dp[19][10][1024], cnt[19][10][1024];
vector<long long> st(19, 1);
long long qq;
long long solve(long long r) {
  if (!r) return 0ll;
  long long ans = 0ll;
  vector<long long> rr;
  while (r > 0) {
    rr.push_back(r % 10);
    r /= 10;
  }
  reverse(rr.begin(), rr.end());
  vector<bool> t(10), p(10);
  long long cur = 0ll;
  long long e = 1ll;
  for (long long i = 0; i < (long long)(long long)rr.size() - 1; ++i) e *= 10ll;
  e--;
  ans = solve(e);
  for (long long i = 0; i < (long long)rr.size(); ++i) {
    for (long long j = 0; j < (long long)rr[i]; ++j) {
      if (i == 0 && j == 0) continue;
      for (long long mask = 0; mask < (long long)1024; ++mask) {
        long long c = 0;
        for (long long k = 0; k < (long long)10; ++k) {
          t[k] = (mask & (1 << k));
          c += t[k] | p[k];
        }
        if (c > qq) continue;
        ans = (ans + dp[(long long)rr.size() - i][j][mask]) % mod;
        ans = (ans + cur * 1ll * cnt[(long long)rr.size() - i][j][mask]) % mod;
      }
    }
    p[rr[i]] = 1;
    cur = (cur + (rr[i] * 1ll * st[(long long)rr.size() - i - 1] % mod)) % mod;
  }
  long long c = 0;
  for (long long i = 0; i < (long long)10; ++i) c += p[i];
  if (c <= qq) {
    ans = (ans + cur) % mod;
  }
  return ans;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long l, r, k;
  cin >> l >> r >> k;
  qq = k;
  for (long long i = 1; i < (long long)19; ++i) st[i] = st[i - 1] * 10ll % mod;
  for (long long i = 0; i < (long long)10; ++i) {
    dp[1][i][1 << i] = i * 1ll;
    cnt[1][i][1 << i] = 1ll;
  }
  vector<bool> tmp(10);
  for (long long i = 2; i < 19; ++i) {
    for (long long j = 0; j < 10; ++j) {
      for (long long mask = 0; mask < 1024; ++mask) {
        if ((mask & (1 << j)) == 0) continue;
        for (long long r = 0; r < (long long)10; ++r) tmp[r] = mask & (1 << r);
        for (long long r = 0; r < (long long)10; ++r)
          if (tmp[r]) {
            dp[i][j][mask] = (dp[i][j][mask] + dp[i - 1][r][mask]) % mod;
            dp[i][j][mask] =
                (dp[i][j][mask] + dp[i - 1][r][mask - (1 << j)]) % mod;
            cnt[i][j][mask] = ((cnt[i][j][mask] + cnt[i - 1][r][mask]) % mod +
                               cnt[i - 1][r][mask - (1 << j)]) %
                              mod;
          }
        dp[i][j][mask] =
            (dp[i][j][mask] + (cnt[i][j][mask] * 1ll * st[i - 1] % mod) * j) %
            mod;
      }
    }
  }
  long long ans = 0ll;
  if (r == (long long)(1e18)) {
    r--;
    if (k >= 2) ans = st[18];
  }
  ans += (solve(r) - solve(l - 1)) % mod;
  ans = (ans % mod + mod) % mod;
  cout << ans;
  return 0;
}
