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 maxn = 1024;
using ll = long long;
int sum[maxn];
ll pow_of_ten[25];
const ll mod = 998244353;
ll digit[20];
pair<ll, ll> dp[25][maxn][15];
int get_digit_number(int now) {
  int res = 0;
  while (now) {
    if (now & 1) {
      res += 1;
    }
    now >>= 1;
  }
  return res;
}
pair<ll, ll> dfs(int now, bool flag, int ds, int k, bool zero) {
  if (!flag && dp[now][ds][k].first != -1 && dp[now][ds][k].second != -1) {
    return dp[now][ds][k];
  }
  if (!now) {
    pair<ll, ll> pa;
    if (sum[ds] <= k) {
      pa.first = 1;
      pa.second = 0;
      return pa;
    }
    pa.first = pa.second = 0;
    return pa;
  }
  int up;
  if (flag) {
    up = digit[now];
  } else
    up = 9;
  ll number = 0, sum = 0;
  for (int i = 0; i <= up; i++) {
    int nz = zero;
    if (i) {
      nz = 1;
    }
    int nds = ds;
    if (nz) {
      nds |= (1 << i);
    }
    pair<ll, ll> next_digit = dfs(now - 1, flag && (i == up), nds, k, nz);
    number = (number + next_digit.first) % mod;
    sum = (sum + (i * pow_of_ten[now - 1] % mod * next_digit.first % mod) +
           next_digit.second) %
          mod;
  }
  if (!flag) {
    dp[now][ds][k].first = number;
    dp[now][ds][k].second = sum;
  }
  return make_pair(number, sum);
}
ll getans(ll num, ll k) {
  if (num == 0) {
    return 0;
  }
  int cnt = 0;
  while (num) {
    digit[++cnt] = num % 10;
    num /= 10;
  }
  return dfs(cnt, 1, 0, k, 0).second;
}
void init() {
  for (int i = 0; i < maxn; i++) {
    sum[i] = get_digit_number(i);
  }
  pow_of_ten[0] = 1;
  for (int i = 1; i < 25; i++) {
    pow_of_ten[i] = pow_of_ten[i - 1] * 10 % mod;
  }
  for (int i = 0; i < 25; i++) {
    for (int j = 0; j < maxn; j++) {
      for (int k = 0; k <= 10; k++) {
        dp[i][j][k].first = dp[i][j][k].second = -1;
      }
    }
  }
}
int main() {
  ll l, r, k;
  init();
  scanf("%lld%lld%lld", &l, &r, &k);
  printf("%lld\n", (getans(r, k) - getans(l - 1, k) + mod) % mod);
}
