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 gcd(long long a, long long b) {
  if (a == 0LL) return b;
  if (b == 0LL) return a;
  return gcd(b, a % b);
}
const int N = 20;
long long dp[2][N][1 << 10];
long long sum[2][N][1 << 10];
long long pw10[N];
string s;
int k;
pair<long long, long long> solve1(bool flag, bool flag1, int pos, int mask) {
  if (__builtin_popcount(mask) > k) return make_pair(0, 0);
  if (pos == s.size()) return make_pair(1, 0);
  if (dp[flag][pos][mask] != -1)
    return make_pair(dp[flag][pos][mask], sum[flag][pos][mask]);
  int up;
  if (flag)
    up = s[pos] - '0';
  else
    up = 9;
  long long ans = 0LL, ans1 = 0LL;
  pair<long long, long long> val;
  long long dig;
  for (int i = 0; i <= up; i++) {
    dig = pw10[s.size() - pos - 1];
    dig = (dig * ((long long)i)) % 998244353LL;
    if (flag1 && i == 0) {
      val = solve1(flag & (i == up), true, pos + 1, mask);
      ans = (ans + val.first) % 998244353LL;
      ans1 = (ans1 + val.first * dig + val.second) % 998244353LL;
      continue;
    }
    val = solve1(flag & (i == up), false, pos + 1, mask | (1 << i));
    ans = (ans + val.first) % 998244353LL;
    ans1 = (ans1 + val.first * dig + val.second) % 998244353LL;
  }
  dp[flag][pos][mask] = ans;
  sum[flag][pos][mask] = ans1;
  return make_pair(ans, ans1);
}
long long isValid(string L) {
  bool mark[10];
  for (int i = 0; i < 10; i++) mark[i] = false;
  long long num = 0LL;
  for (int i = 0; i < L.size(); i++) {
    mark[L[i] - '0'] = true;
    num = num * 10LL + (long long)(L[i] - '0');
  }
  num = num % 998244353LL;
  int cnt = 0;
  for (int i = 0; i < 10; i++) cnt += mark[i];
  if (cnt > k) return 0LL;
  return num;
}
void solve() {
  pw10[0] = 1LL;
  for (int i = 1; i < N; i++) pw10[i] = (pw10[i - 1] * 10LL) % 998244353LL;
  string L, R;
  cin >> L >> R >> k;
  memset(dp, -1, sizeof(dp));
  s = R;
  pair<long long, long long> val;
  val = solve1(true, true, 0, 0);
  long long ans = val.second;
  memset(dp, -1, sizeof(dp));
  s = L;
  val = solve1(true, true, 0, 0);
  ans = (ans - val.second + 2LL * 998244353LL) % 998244353LL;
  ans = ans + isValid(L);
  ans = ans % 998244353LL;
  cout << ans << "\n";
  return;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  clock_t clk = clock();
  int t = 1;
  for (int tests = 1; tests <= t; tests++) {
    solve();
  }
  clk = clock() - clk;
  cerr << "Time Elapsed: " << fixed << setprecision(10)
       << ((long double)clk) / CLOCKS_PER_SEC << "\n";
  return 0;
}
