#include <bits/stdc++.h>
using namespace std;
long long mod = 998244353;
vector<int> reduce(vector<int> v, int mask) {
  int mi = 9, ma = 0;
  for (int j = 0; j < 10; j++) {
    if (mask >> j & 1) {
      mi = min(mi, j);
      ma = max(ma, j);
    }
  }
  int loan = 0;
  for (int i = 0; i < v.size(); i++) {
    v[i] -= loan;
    loan = 0;
    if (v[i] < mi) {
      for (int j = 0; j <= i; j++) v[j] = ma;
      loan = 1;
    } else if (mask >> v[i] & 1) {
    } else {
      while (!(mask >> v[i] & 1)) v[i]--;
      for (int j = 0; j < i; j++) v[j] = ma;
    }
  }
  if (loan) v.pop_back();
  while (v.size() && !*v.rbegin()) v.pop_back();
  return v;
}
vector<int> digits(long long n) {
  vector<int> v;
  long long base = 1;
  while (n) {
    long long d = n % 10;
    v.push_back(d);
    n /= 10;
  }
  return v;
}
long long num(vector<int> v) {
  long long m = 1, r = 0;
  for (int i : v) {
    r += m * i;
    m *= 10;
  }
  return r;
}
vector<int> safereduce(long long n, int mask) {
  while (1) {
    int ok = 1;
    for (int i : digits(n))
      if (!(mask >> i & 1)) ok = 0;
    if (ok) break;
    n--;
  }
  return digits(n);
}
long long sum(vector<int> v, int mask) {
  int ind[10], mi = 9, ma = 0, pop = 0;
  for (int j = 0; j < 10; j++) {
    ind[j] = (j ? ind[j - 1] : -1) + (mask >> j & 1);
    if (mask >> j & 1) {
      mi = min(mi, j);
      ma = max(ma, j);
      pop++;
    }
  }
  long long ans = 0;
  long long right = 1, rval = 0, p10 = 1;
  for (int i = 0; i < v.size(); i++) {
    long long left = 0;
    for (int j = v.size() - 1; j > i; j--)
      left = (left * pop + ind[v[j]]) % mod;
    long long mul = !(mask & 1);
    for (int j = i + 1; j < v.size(); j++) {
      left = (left + mul) % mod;
      mul = mul * pop % mod;
    }
    for (int j = 1; j < 10; j++)
      if (mask >> j & 1) {
        (ans += left * right % mod * j % mod * p10) %= mod;
        if (j < v[i])
          (ans += right * j % mod * p10) %= mod;
        else if (j == v[i])
          (ans += (rval + 1) * v[i] % mod * p10) %= mod;
      }
    rval = (rval + right * ind[v[i]]) % mod;
    right = right * pop % mod;
    p10 = p10 * 10 % mod;
  }
  return ans;
}
long long safesum(long long n, int mask) {
  long long ans = 0;
  for (int i = 1; i <= n; i++) {
    int ok = 1;
    for (int i : digits(i))
      if (!(mask >> i & 1)) ok = 0;
    ans += ok * i;
  }
  return ans;
}
long long dp[1 << 10], dp2[1 << 10];
long long f(long long n, int k) {
  vector<int> v = digits(n);
  for (int mask = 1; mask < 1 << 10; mask++)
    dp[mask] = sum(reduce(v, mask), mask);
  for (int i = 1; i < 1 << 10; i++) {
    dp2[i] = 0;
    for (int j = 1; j < 1 << 10; j++)
      if ((j & i) == j) {
        int k = i ^ j;
        int pop = 0;
        while (k) k -= k & -k, pop++;
        (dp2[i] += (pop % 2 ? -1 : 1) * dp[j]) %= mod;
      }
  }
  long long ans = 0;
  for (int mask = 1; mask < 1 << 10; mask++) {
    int pop = 0;
    int i = mask;
    while (i) i -= i & -i, pop++;
    if (pop > k) continue;
    (ans += dp2[mask]) %= mod;
  }
  return (ans + mod) % mod;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long l, r, k;
  cin >> l >> r >> k;
  cout << (f(r, k) - f(l - 1, k) + mod) % mod << endl;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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;
long long mod = 998244353;
vector<int> reduce(vector<int> v, int mask) {
  int mi = 9, ma = 0;
  for (int j = 0; j < 10; j++) {
    if (mask >> j & 1) {
      mi = min(mi, j);
      ma = max(ma, j);
    }
  }
  int loan = 0;
  for (int i = 0; i < v.size(); i++) {
    v[i] -= loan;
    loan = 0;
    if (v[i] < mi) {
      for (int j = 0; j <= i; j++) v[j] = ma;
      loan = 1;
    } else if (mask >> v[i] & 1) {
    } else {
      while (!(mask >> v[i] & 1)) v[i]--;
      for (int j = 0; j < i; j++) v[j] = ma;
    }
  }
  if (loan) v.pop_back();
  while (v.size() && !*v.rbegin()) v.pop_back();
  return v;
}
vector<int> digits(long long n) {
  vector<int> v;
  long long base = 1;
  while (n) {
    long long d = n % 10;
    v.push_back(d);
    n /= 10;
  }
  return v;
}
long long num(vector<int> v) {
  long long m = 1, r = 0;
  for (int i : v) {
    r += m * i;
    m *= 10;
  }
  return r;
}
vector<int> safereduce(long long n, int mask) {
  while (1) {
    int ok = 1;
    for (int i : digits(n))
      if (!(mask >> i & 1)) ok = 0;
    if (ok) break;
    n--;
  }
  return digits(n);
}
long long sum(vector<int> v, int mask) {
  int ind[10], mi = 9, ma = 0, pop = 0;
  for (int j = 0; j < 10; j++) {
    ind[j] = (j ? ind[j - 1] : -1) + (mask >> j & 1);
    if (mask >> j & 1) {
      mi = min(mi, j);
      ma = max(ma, j);
      pop++;
    }
  }
  long long ans = 0;
  long long right = 1, rval = 0, p10 = 1;
  for (int i = 0; i < v.size(); i++) {
    long long left = 0;
    for (int j = v.size() - 1; j > i; j--)
      left = (left * pop + ind[v[j]]) % mod;
    long long mul = !(mask & 1);
    for (int j = i + 1; j < v.size(); j++) {
      left = (left + mul) % mod;
      mul = mul * pop % mod;
    }
    for (int j = 1; j < 10; j++)
      if (mask >> j & 1) {
        (ans += left * right % mod * j % mod * p10) %= mod;
        if (j < v[i])
          (ans += right * j % mod * p10) %= mod;
        else if (j == v[i])
          (ans += (rval + 1) * v[i] % mod * p10) %= mod;
      }
    rval = (rval + right * ind[v[i]]) % mod;
    right = right * pop % mod;
    p10 = p10 * 10 % mod;
  }
  return ans;
}
long long safesum(long long n, int mask) {
  long long ans = 0;
  for (int i = 1; i <= n; i++) {
    int ok = 1;
    for (int i : digits(i))
      if (!(mask >> i & 1)) ok = 0;
    ans += ok * i;
  }
  return ans;
}
long long dp[1 << 10], dp2[1 << 10];
long long f(long long n, int k) {
  vector<int> v = digits(n);
  for (int mask = 1; mask < 1 << 10; mask++)
    dp[mask] = sum(reduce(v, mask), mask);
  for (int i = 1; i < 1 << 10; i++) {
    dp2[i] = 0;
    for (int j = 1; j < 1 << 10; j++)
      if ((j & i) == j) {
        int k = i ^ j;
        int pop = 0;
        while (k) k -= k & -k, pop++;
        (dp2[i] += (pop % 2 ? -1 : 1) * dp[j]) %= mod;
      }
  }
  long long ans = 0;
  for (int mask = 1; mask < 1 << 10; mask++) {
    int pop = 0;
    int i = mask;
    while (i) i -= i & -i, pop++;
    if (pop > k) continue;
    (ans += dp2[mask]) %= mod;
  }
  return (ans + mod) % mod;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long l, r, k;
  cin >> l >> r >> k;
  cout << (f(r, k) - f(l - 1, k) + mod) % mod << endl;
}

```