#include <bits/stdc++.h>
using namespace std;
const long long INF = 998244353;
const int MAXN = 1e6 + 7;
const double EPS = 1e-8;
void add(long long &x, long long y) {
  x = (x + y) % INF;
  if (x < 0) x += INF;
}
vector<long long> st;
void init() {
  st.push_back(1);
  for (long long i = 1; i < 50; i++) {
    st.push_back(st.back() * 10LL % INF);
  }
}
long long calc1(long long len, long long k) {
  long long M = (1LL << 10);
  long long dp[len + 1][M];
  long long sums[len + 1][M];
  for (long long i = 0; i <= len; i++) {
    for (long long j = 0; j < M; j++) {
      dp[i][j] = 0;
      sums[i][j] = 0;
    }
  }
  for (long long i = 1; i <= 9; i++) {
    dp[1][1 << i] = 1;
    sums[1][1 << i] = st[len - 1] * i % INF;
  }
  for (long long len1 = 2; len1 <= len; len1++) {
    for (long long mask = 0; mask < M; mask++) {
      for (long long i = 0; i < 10; i++) {
        long long mask1 = mask | (1 << i);
        add(dp[len1][mask1], dp[len1 - 1][mask]);
        add(sums[len1][mask1],
            dp[len1 - 1][mask] * i % INF * st[len - len1] % INF);
        add(sums[len1][mask1], sums[len1 - 1][mask]);
      }
    }
  }
  long long res = 0;
  for (long long i = 0; i < M; i++) {
    long long d = __builtin_popcount(i);
    if (d <= k) {
      add(res, sums[len][i]);
    }
  }
  return res;
}
long long calc(long long r, long long k) {
  if (!r) return 0;
  long long res = 0;
  long long M = (1 << 10);
  long long cnt = 0;
  long long rt = r;
  vector<long long> num;
  while (rt) {
    cnt++;
    num.push_back(rt % 10);
    rt /= 10;
  }
  reverse(num.begin(), num.end());
  for (long long i = 1; i < cnt; i++) {
    add(res, calc1(i, k));
  }
  long long dp[cnt + 1][M][2];
  long long sums[cnt + 1][M][2];
  for (long long len = 0; len <= cnt; len++) {
    for (long long j = 0; j < M; j++) {
      for (long long p = 0; p < 2; p++) {
        dp[len][j][p] = 0;
        sums[len][j][p] = 0;
      }
    }
  }
  for (long long i = 1; i < num[0]; i++) {
    dp[1][1 << i][0] = 1;
    sums[1][1 << i][0] = i * st[cnt - 1] % INF;
  }
  dp[1][1 << num[0]][1] = 1;
  sums[1][1 << num[0]][1] = num[0] * st[cnt - 1] % INF;
  for (long long len = 2; len <= cnt; len++) {
    for (long long mask = 0; mask < M; mask++) {
      for (long long i = 0; i < 10; i++) {
        long long mask1 = mask | (1 << i);
        add(dp[len][mask1][0], dp[len - 1][mask][0]);
        add(sums[len][mask1][0], sums[len - 1][mask][0]);
        add(sums[len][mask1][0],
            dp[len - 1][mask][0] * i % INF * st[cnt - len] % INF);
        if (i < num[len - 1]) {
          add(dp[len][mask1][0], dp[len - 1][mask][1]);
          add(sums[len][mask1][0], sums[len - 1][mask][1]);
          add(sums[len][mask1][0],
              dp[len - 1][mask][1] * i % INF * st[cnt - len] % INF);
        } else if (i == num[len - 1]) {
          add(dp[len][mask1][1], dp[len - 1][mask][1]);
          add(sums[len][mask1][1], sums[len - 1][mask][1]);
          add(sums[len][mask1][1],
              dp[len - 1][mask][1] * i % INF * st[cnt - len] % INF);
        }
      }
    }
  }
  for (long long i = 0; i < M; i++) {
    long long d = __builtin_popcount(i);
    if (d <= k) {
      add(res, sums[cnt][i][0]);
      add(res, sums[cnt][i][1]);
    }
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  init();
  long long l, r, k;
  cin >> l >> r >> k;
  cout << (calc(r, k) - calc(l - 1, k) + INF) % INF << "\n";
}

### Prompt

Generate 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;
const long long INF = 998244353;
const int MAXN = 1e6 + 7;
const double EPS = 1e-8;
void add(long long &x, long long y) {
  x = (x + y) % INF;
  if (x < 0) x += INF;
}
vector<long long> st;
void init() {
  st.push_back(1);
  for (long long i = 1; i < 50; i++) {
    st.push_back(st.back() * 10LL % INF);
  }
}
long long calc1(long long len, long long k) {
  long long M = (1LL << 10);
  long long dp[len + 1][M];
  long long sums[len + 1][M];
  for (long long i = 0; i <= len; i++) {
    for (long long j = 0; j < M; j++) {
      dp[i][j] = 0;
      sums[i][j] = 0;
    }
  }
  for (long long i = 1; i <= 9; i++) {
    dp[1][1 << i] = 1;
    sums[1][1 << i] = st[len - 1] * i % INF;
  }
  for (long long len1 = 2; len1 <= len; len1++) {
    for (long long mask = 0; mask < M; mask++) {
      for (long long i = 0; i < 10; i++) {
        long long mask1 = mask | (1 << i);
        add(dp[len1][mask1], dp[len1 - 1][mask]);
        add(sums[len1][mask1],
            dp[len1 - 1][mask] * i % INF * st[len - len1] % INF);
        add(sums[len1][mask1], sums[len1 - 1][mask]);
      }
    }
  }
  long long res = 0;
  for (long long i = 0; i < M; i++) {
    long long d = __builtin_popcount(i);
    if (d <= k) {
      add(res, sums[len][i]);
    }
  }
  return res;
}
long long calc(long long r, long long k) {
  if (!r) return 0;
  long long res = 0;
  long long M = (1 << 10);
  long long cnt = 0;
  long long rt = r;
  vector<long long> num;
  while (rt) {
    cnt++;
    num.push_back(rt % 10);
    rt /= 10;
  }
  reverse(num.begin(), num.end());
  for (long long i = 1; i < cnt; i++) {
    add(res, calc1(i, k));
  }
  long long dp[cnt + 1][M][2];
  long long sums[cnt + 1][M][2];
  for (long long len = 0; len <= cnt; len++) {
    for (long long j = 0; j < M; j++) {
      for (long long p = 0; p < 2; p++) {
        dp[len][j][p] = 0;
        sums[len][j][p] = 0;
      }
    }
  }
  for (long long i = 1; i < num[0]; i++) {
    dp[1][1 << i][0] = 1;
    sums[1][1 << i][0] = i * st[cnt - 1] % INF;
  }
  dp[1][1 << num[0]][1] = 1;
  sums[1][1 << num[0]][1] = num[0] * st[cnt - 1] % INF;
  for (long long len = 2; len <= cnt; len++) {
    for (long long mask = 0; mask < M; mask++) {
      for (long long i = 0; i < 10; i++) {
        long long mask1 = mask | (1 << i);
        add(dp[len][mask1][0], dp[len - 1][mask][0]);
        add(sums[len][mask1][0], sums[len - 1][mask][0]);
        add(sums[len][mask1][0],
            dp[len - 1][mask][0] * i % INF * st[cnt - len] % INF);
        if (i < num[len - 1]) {
          add(dp[len][mask1][0], dp[len - 1][mask][1]);
          add(sums[len][mask1][0], sums[len - 1][mask][1]);
          add(sums[len][mask1][0],
              dp[len - 1][mask][1] * i % INF * st[cnt - len] % INF);
        } else if (i == num[len - 1]) {
          add(dp[len][mask1][1], dp[len - 1][mask][1]);
          add(sums[len][mask1][1], sums[len - 1][mask][1]);
          add(sums[len][mask1][1],
              dp[len - 1][mask][1] * i % INF * st[cnt - len] % INF);
        }
      }
    }
  }
  for (long long i = 0; i < M; i++) {
    long long d = __builtin_popcount(i);
    if (d <= k) {
      add(res, sums[cnt][i][0]);
      add(res, sums[cnt][i][1]);
    }
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  init();
  long long l, r, k;
  cin >> l >> r >> k;
  cout << (calc(r, k) - calc(l - 1, k) + INF) % INF << "\n";
}

```