#include <bits/stdc++.h>
using namespace std;
template <typename T>
void _dbg(const char* _s, T _h) {
  cerr << _s << " = " << _h << "\n";
}
template <typename T, typename... Ts>
void _dbg(const char* _s, T _h, Ts... _t) {
  int _b = 0;
  while (((_b += *_s == '(') -= *_s == ')') != 0 || *_s != ',') cerr << *_s++;
  cerr << " = " << _h << ",";
  _dbg(_s + 1, _t...);
}
using ll = long long;
const ll INF = static_cast<ll>(1e9) + 7ll;
const ll LINF = INF * INF;
const int MAXN = static_cast<int>(1e6) + 17;
ll L, R, k, MOD = 998244353;
ll first[100][1 << 12], dp[100][1 << 12];
bool read() {
  if (!(cin >> L >> R >> k)) return false;
  return true;
}
ll add(ll a, ll b) {
  a += b;
  if (a >= MOD) a -= MOD;
  if (a >= MOD) a %= MOD;
  return a;
}
vector<int> tyoma_vklyuchi_v_v(ll R) {
  vector<int> vec;
  for (; R > 0; R /= 10) vec.emplace_back(R % 10);
  reverse(vec.begin(), vec.end());
  return vec;
}
ll calc_1(ll R) {
  if (R == 0) return 0;
  auto vec = tyoma_vklyuchi_v_v(R);
  int n = static_cast<int>((vec).size());
  int mask = 0;
  ll res = 0;
  ;
  ll pref = 0;
  ll ten = 1;
  for (ll i = 0; i < static_cast<ll>(n - 1); ++i) {
    ten = ten * 10ll;
  }
  for (int l = 0; l <= n && __builtin_popcount(mask) <= k; ++l) {
    if (l == n) {
      res = add(res, pref % MOD);
      break;
    } else {
      for (int c = (l == 0 ? 1 : 0); c < vec[l]; ++c) {
        if (__builtin_popcount(mask | (1 << c)) <= k) {
          for (int smask = 0; smask < (1 << 10); ++smask)
            if (__builtin_popcount((smask | mask | (1 << c))) <= k) {
              pref += c * (ten);
              ll cur = dp[n - l - 1][smask] * (pref % MOD) % MOD;
              pref -= c * (ten);
              cur = add(cur, first[n - l - 1][smask]);
              res = add(res, cur);
            }
        }
      }
    }
    mask |= (1 << vec[l]);
    pref += ten * vec[l];
    ten /= 10;
  };
  return res;
}
ll calc(ll R) {
  ll cur = 9;
  ll res = 0;
  for (;; cur = 10ll * cur + 9) {
    if (cur >= R) {
      res = add(res, calc_1(R));
      break;
    }
    res = add(res, calc_1(cur));
  };
  return res;
}
ll naivedp(int len, int mask) {
  ll res = 0;
  for (int i = 0;; ++i) {
    auto vec = tyoma_vklyuchi_v_v(i);
    if (static_cast<int>((vec).size()) > len) break;
    while (static_cast<int>((vec).size()) < len) vec.emplace_back(0);
    int smask = 0;
    for (auto i : vec) smask |= (1 << i);
    if (mask == smask) res += i;
  }
  return res;
}
void solve() {
  dp[0][0] = 1;
  first[0][0] = 0;
  ll ten = 1;
  for (int len = 0; len < 30; ++len, ten = ten * 10 % MOD) {
    for (int mask = 0; mask < (1 << 10); ++mask) {
      for (int c = 0; c < 10; ++c) {
        int smask = (mask | (1 << c));
        dp[len + 1][smask] = add(dp[len + 1][smask], dp[len][mask]);
        ll cur = ten * c % MOD;
        cur = cur * dp[len][mask] % MOD;
        cur = add(cur, first[len][mask]);
        first[len + 1][smask] = add(first[len + 1][smask], cur);
      }
    }
  }
  cout << (calc(R) - calc(L - 1) + MOD) % MOD << '\n';
}
int32_t main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  while (read()) solve();
  return 0;
}

### Prompt

Your challenge is to write a cpp solution to the following problem:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
void _dbg(const char* _s, T _h) {
  cerr << _s << " = " << _h << "\n";
}
template <typename T, typename... Ts>
void _dbg(const char* _s, T _h, Ts... _t) {
  int _b = 0;
  while (((_b += *_s == '(') -= *_s == ')') != 0 || *_s != ',') cerr << *_s++;
  cerr << " = " << _h << ",";
  _dbg(_s + 1, _t...);
}
using ll = long long;
const ll INF = static_cast<ll>(1e9) + 7ll;
const ll LINF = INF * INF;
const int MAXN = static_cast<int>(1e6) + 17;
ll L, R, k, MOD = 998244353;
ll first[100][1 << 12], dp[100][1 << 12];
bool read() {
  if (!(cin >> L >> R >> k)) return false;
  return true;
}
ll add(ll a, ll b) {
  a += b;
  if (a >= MOD) a -= MOD;
  if (a >= MOD) a %= MOD;
  return a;
}
vector<int> tyoma_vklyuchi_v_v(ll R) {
  vector<int> vec;
  for (; R > 0; R /= 10) vec.emplace_back(R % 10);
  reverse(vec.begin(), vec.end());
  return vec;
}
ll calc_1(ll R) {
  if (R == 0) return 0;
  auto vec = tyoma_vklyuchi_v_v(R);
  int n = static_cast<int>((vec).size());
  int mask = 0;
  ll res = 0;
  ;
  ll pref = 0;
  ll ten = 1;
  for (ll i = 0; i < static_cast<ll>(n - 1); ++i) {
    ten = ten * 10ll;
  }
  for (int l = 0; l <= n && __builtin_popcount(mask) <= k; ++l) {
    if (l == n) {
      res = add(res, pref % MOD);
      break;
    } else {
      for (int c = (l == 0 ? 1 : 0); c < vec[l]; ++c) {
        if (__builtin_popcount(mask | (1 << c)) <= k) {
          for (int smask = 0; smask < (1 << 10); ++smask)
            if (__builtin_popcount((smask | mask | (1 << c))) <= k) {
              pref += c * (ten);
              ll cur = dp[n - l - 1][smask] * (pref % MOD) % MOD;
              pref -= c * (ten);
              cur = add(cur, first[n - l - 1][smask]);
              res = add(res, cur);
            }
        }
      }
    }
    mask |= (1 << vec[l]);
    pref += ten * vec[l];
    ten /= 10;
  };
  return res;
}
ll calc(ll R) {
  ll cur = 9;
  ll res = 0;
  for (;; cur = 10ll * cur + 9) {
    if (cur >= R) {
      res = add(res, calc_1(R));
      break;
    }
    res = add(res, calc_1(cur));
  };
  return res;
}
ll naivedp(int len, int mask) {
  ll res = 0;
  for (int i = 0;; ++i) {
    auto vec = tyoma_vklyuchi_v_v(i);
    if (static_cast<int>((vec).size()) > len) break;
    while (static_cast<int>((vec).size()) < len) vec.emplace_back(0);
    int smask = 0;
    for (auto i : vec) smask |= (1 << i);
    if (mask == smask) res += i;
  }
  return res;
}
void solve() {
  dp[0][0] = 1;
  first[0][0] = 0;
  ll ten = 1;
  for (int len = 0; len < 30; ++len, ten = ten * 10 % MOD) {
    for (int mask = 0; mask < (1 << 10); ++mask) {
      for (int c = 0; c < 10; ++c) {
        int smask = (mask | (1 << c));
        dp[len + 1][smask] = add(dp[len + 1][smask], dp[len][mask]);
        ll cur = ten * c % MOD;
        cur = cur * dp[len][mask] % MOD;
        cur = add(cur, first[len][mask]);
        first[len + 1][smask] = add(first[len + 1][smask], cur);
      }
    }
  }
  cout << (calc(R) - calc(L - 1) + MOD) % MOD << '\n';
}
int32_t main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  while (read()) solve();
  return 0;
}

```