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;
int mem[1 << 12][20][2][2], mem1[1 << 12][20][2][2], k;
long long mod = 998244353, pwr[20];
vector<long long> a;
long long dp(int x, int msk, int l, int nm, bool f) {
  if (x == a.size()) {
    mem1[msk][x][l][f] = 0;
    return nm <= k;
  }
  if (nm > k) {
    mem1[msk][x][l][f] = 0;
    return 0;
  }
  if (mem[msk][x][l][f] != -1) {
    return mem[msk][x][l][f];
  }
  long long res = 0, tmp, ans1 = 0, tmp1;
  if (l) {
    if (f) {
      tmp = dp(x + 1, msk, 0, nm, 1);
      tmp1 = mem1[msk][x + 1][0][1];
      ans1 += tmp1;
      res += tmp;
      res %= mod;
    } else {
      tmp = dp(x + 1, msk | (1ll << 0), a[x] == 0,
               nm + ((msk & (1ll << 0)) == 0), 0);
      tmp1 = mem1[msk | (1ll << 0)][x + 1][a[x] == 0][0];
      ans1 += tmp1;
      res += tmp;
      res %= mod;
    }
    for (long long i = 1; i < a[x]; ++i) {
      tmp = dp(x + 1, msk | (1ll << i), 0, nm + ((msk & (1ll << i)) == 0), 0);
      tmp1 = mem1[msk | (1ll << i)][x + 1][0][0];
      res += tmp;
      ans1 += i * (pwr[a.size() - x - 1] * tmp % mod) + tmp1;
      res %= mod;
      ans1 %= mod;
    }
    if (a[x] != 0) {
      tmp = dp(x + 1, msk | (1ll << a[x]), 1, nm + ((msk & (1ll << a[x])) == 0),
               0);
      tmp1 = mem1[msk | (1ll << a[x])][x + 1][1][0];
      res += tmp;
      ans1 += a[x] * (pwr[a.size() - x - 1] * tmp % mod) + tmp1;
      res %= mod;
      ans1 %= mod;
    }
  } else {
    if (f) {
      tmp = dp(x + 1, msk, 0, nm, 1);
      tmp1 = mem1[msk][x + 1][0][1];
      ans1 += tmp1;
      res += tmp;
      res %= mod;
    } else {
      tmp = dp(x + 1, msk | (1ll << 0), 0, nm + ((msk & (1ll << 0)) == 0), 0);
      tmp1 = mem1[msk | (1ll << 0)][x + 1][0][0];
      ans1 += tmp1;
      res += tmp;
      res %= mod;
    }
    for (long long i = 1; i < 10; ++i) {
      tmp = dp(x + 1, msk | (1ll << i), 0, nm + ((msk & (1ll << i)) == 0), 0);
      tmp1 = mem1[msk | (1ll << i)][x + 1][0][0];
      res += tmp;
      ans1 += i * (pwr[a.size() - x - 1] * tmp % mod) + tmp1;
      res %= mod;
      ans1 %= mod;
    }
  }
  res %= mod;
  mem[msk][x][l][f] = res;
  mem1[msk][x][l][f] = ans1;
  return res;
}
int main() {
  pwr[0] = 1;
  for (int i = 1; i < 20; ++i) {
    pwr[i] = (pwr[i - 1] * 10) % mod;
  }
  long long x, y;
  cin >> x >> y >> k;
  a.clear();
  for (int i = 19; i >= 0; --i) {
    a.push_back(y % 10);
    y /= 10;
    if (!y) break;
  }
  reverse(a.begin(), a.end());
  memset(mem, -1, sizeof mem);
  dp(0, 0, 1, 0, 1);
  long long ans1 = mem1[0][0][1][1];
  --x;
  if (x == 0) {
    cout << ans1 << endl;
    return 0;
  }
  a.clear();
  for (int i = 19; i >= 0; --i) {
    a.push_back(x % 10);
    x /= 10;
    if (!x) break;
  }
  reverse(a.begin(), a.end());
  memset(mem, -1, sizeof mem);
  memset(mem1, 0, sizeof mem1);
  dp(0, 0, 1, 0, 1);
  ans1 -= mem1[0][0][1][1];
  ans1 %= mod;
  if (ans1 < 0) ans1 += mod;
  cout << ans1 << endl;
  return 0;
}
