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 N = 2012345;
const int mod = 998244353;
template <class num>
inline void rd(num &x) {
  char c;
  while (isspace(c = getchar()))
    ;
  bool neg = false;
  if (!isdigit(c))
    neg = (c == '-'), x = 0;
  else
    x = c - '0';
  while (isdigit(c = getchar())) x = (x << 3) + (x << 1) + c - '0';
  if (neg) x = -x;
}
vector<int> v;
long long l, r, k;
int fixo, d;
long long dp[20][2][1 << 11][2];
int vis[20][2][1 << 11][2], viscnt;
long long solve(int pos, int menor, int mask, int flag) {
  if (__builtin_popcount(mask) > k) return 0;
  if (pos == -1) return flag;
  if (vis[pos][menor][mask][flag] == viscnt) return dp[pos][menor][mask][flag];
  vis[pos][menor][mask][flag] = viscnt;
  long long &ret = dp[pos][menor][mask][flag];
  ret = 0;
  if (fixo == pos) {
    if (menor)
      ret += solve(pos - 1, true, mask | (1 << d), true);
    else if (d < v[pos])
      ret += solve(pos - 1, true, mask | (1 << d), true);
    else if (d == v[pos])
      ret += solve(pos - 1, false, mask | (1 << d), true);
    return ret %= mod;
  }
  if (menor) {
    for (int i = 0; i < 10; i++)
      if (i or flag)
        ret += solve(pos - 1, true, mask | (1 << i), true);
      else
        ret += solve(pos - 1, true, mask, false);
    return ret %= mod;
  } else {
    for (int i = 0; i < v[pos]; i++)
      if (i or flag)
        ret += solve(pos - 1, true, mask | (1 << i), true);
      else
        ret += solve(pos - 1, true, mask, false);
    ret += solve(pos - 1, false, mask | (1 << v[pos]), true);
    return ret %= mod;
  }
}
long long pot[20];
long long solve(long long xd) {
  if (!xd) return 0;
  v.clear();
  long long qd = xd;
  while (xd) {
    v.push_back(xd % 10);
    xd /= 10;
  }
  long long ans = 0;
  for (fixo = 0; fixo < v.size(); fixo++) {
    for (d = 1; d <= 9; d++) {
      viscnt++;
      ans = ans + pot[fixo] * d * solve(v.size() - 1, 0, 0, 0) % mod;
      ans %= mod;
    }
  }
  return ans;
}
int main(void) {
  pot[0] = 1;
  for (int i = 1; i < 20; i++) pot[i] = pot[i - 1] * 10 % mod;
  rd(l);
  rd(r);
  rd(k);
  cout << (solve(r) - solve(l - 1) + mod) % mod << endl;
  return 0;
}
