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;
namespace IO {
void setIn(string s) { freopen(s.c_str(), "r", stdin); }
void setOut(string s) { freopen(s.c_str(), "w", stdout); }
void setIO(string s = "") {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin.exceptions(cin.failbit);
  if (s.size()) {
    setIn(s + ".inp");
    setOut(s + ".out");
  } else {
  }
}
}  // namespace IO
using namespace IO;
namespace Function {
template <typename T1, typename T2>
void amax(T1 &a, T2 b) {
  if (typeid(a).name() == typeid(int).name() &&
      typeid(b).name() == typeid(long long).name()) {
    cout << "Error on amax";
    exit(0);
  }
  if (a < b) a = b;
}
template <typename T1, typename T2>
void amin(T1 &a, T2 b) {
  if (a > b) a = b;
}
template <typename T>
void compress(vector<T> &a) {
  sort(a.begin(), a.end());
  a.resize(unique(a.begin(), a.end()) - a.begin());
}
template <typename T>
long long sqr(T x) {
  return 1LL * x * x;
}
template <typename T1, typename T2>
long long gcd(T1 a, T2 b) {
  return (b == 0 ? a : gcd(b, a % b));
}
template <typename T1, typename T2>
long long lcm(T1 a, T2 b) {
  return 1LL * a / gcd(a, b) * b;
}
}  // namespace Function
using namespace Function;
namespace Output {
void print(int x) { cout << x << "\n"; }
void print(unsigned int x) { cout << x << "\n"; }
void print(long unsigned int x) { cout << x << "\n"; }
void print(long long x) { cout << x << "\n"; }
void print(unsigned long long x) { cout << x << "\n"; }
void print(float x) { cout << x << "\n"; }
void print(double x) { cout << x << "\n"; }
void print(long double x) { cout << x << "\n"; }
void print(char x) { cout << x << "\n"; }
void print(const char *x) { cout << x << "\n"; }
void print(string x) { cout << x << "\n"; }
void print(bool x) { cout << x << "\n"; }
template <class T, class... Ts>
void print(T t, Ts... ts) {
  cout << t << " ";
  print(ts...);
}
template <typename T1, typename T2>
void print(pair<T1, T2> a) {
  print(a.first, a.second);
}
template <typename T>
void print(T a) {
  for (auto it : a) {
    print(it);
  }
}
template <class T, class... Ts>
void prine(T t, Ts... ts) {
  print(t, ts...);
  exit(0);
}
}  // namespace Output
using namespace Output;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
const int INF = 1e9;
const long long INFL = 1e18;
const int MOD = 998244353;
const int N = 1e5 + 10;
long long dp[20][(1 << 10) + 10][3][2];
int k;
long long calc(long long n) {
  if (n == 0) {
    return 0;
  }
  string s = to_string(n);
  memset(dp, 0, sizeof(dp));
  dp[0][0][1][1] = 1;
  for (int i = 0; i < s.size(); i++) {
    for (int mask = 0; mask < (1 << 10); mask++) {
      for (int sta = 0; sta < 3; sta++) {
        if (dp[i][mask][sta][1] > 0) {
          for (int k = (i == 0 ? 1 : 0); k < 10; k++) {
            int newsta;
            if (sta != 1) {
              newsta = sta;
            } else {
              if (k < s[i] - '0') {
                newsta = 0;
              } else if (k > s[i] - '0') {
                newsta = 2;
              } else {
                newsta = 1;
              }
            }
            int new_mask = mask | (1 << k);
            dp[i + 1][new_mask][newsta][0] +=
                dp[i][mask][sta][0] * 10 + dp[i][mask][sta][1] * k;
            dp[i + 1][new_mask][newsta][0] %= MOD;
            dp[i + 1][new_mask][newsta][1] += dp[i][mask][sta][1];
            dp[i + 1][new_mask][newsta][1] %= MOD;
          }
        }
      }
    }
  }
  long long res = 0;
  for (int i = 1; i <= s.size(); i++) {
    for (int mask = 1; mask < (1 << 10); mask++) {
      if (__builtin_popcount(mask) > k) {
        continue;
      }
      for (int sta = 0; sta < (i < s.size() ? 3 : 2); sta++) {
        res += dp[i][mask][sta][0];
        res %= MOD;
      }
    }
  }
  return res;
}
int main() {
  setIO();
  long long l, r;
  cin >> l >> r >> k;
  print((calc(r) - calc(l - 1) + MOD) % MOD);
  return 0;
}
