#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) { return a % b == 0 ? b : gcd(b, a % b); }
const int MAXN = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const long long INFLL = 0x3f3f3f3f3f3f3f3f;
const long long mod = 998244353;
long long l, r, k;
int str[25];
struct Res {
  long long cnt;
  long long sum;
};
Res temp, dp[25][1025][25];
long long ten[25];
Res DFS(int len, int now, int sum, int flag, int p) {
  long long ans = 0;
  long long cnt = 0;
  if (sum > k) {
    temp.cnt = temp.sum = 0;
    return temp;
  }
  if (len == 0) {
    temp.sum = 0, temp.cnt = 1;
    return temp;
  }
  if (flag == 0 && p == 0 && dp[len][now][sum].cnt != -1)
    return dp[len][now][sum];
  int up = flag ? str[len] : 9;
  for (int i = 0; i <= up; i++) {
    if (now & (1 << i)) {
      temp = DFS(len - 1, now, sum, flag && i == up, 0);
      cnt += temp.cnt;
      cnt %= mod;
      ans =
          (ans + temp.sum + (temp.cnt % mod) * (i % mod) * ten[len - 1] % mod) %
          mod;
    } else {
      if (p == 1 && i == 0) {
        temp = DFS(len - 1, now, sum, flag && i == up, 1);
        cnt += temp.cnt;
        ans = (ans + temp.sum) % mod;
      } else {
        temp = DFS(len - 1, now ^ (1 << i), sum + 1, flag && i == up, 0);
        cnt += temp.cnt;
        cnt %= mod;
        ans =
            (ans + temp.sum + (temp.cnt % mod) * i % mod * ten[len - 1] % mod) %
            mod;
      }
    }
  }
  temp.cnt = cnt;
  temp.sum = ans;
  if (flag == 0 && p == 0) dp[len][now][sum] = temp;
  return temp;
}
Res solve(long long x) {
  int len = 0;
  len = 0;
  while (x) {
    str[++len] = x % 10;
    x /= 10;
  }
  return DFS(len, 0, 0, 1, 1);
}
int main() {
  long long le, ri;
  ten[0] = 1;
  while (~scanf("%lld%lld", &le, &ri)) {
    scanf("%d", &k);
    for (int i = 1; i <= 22; i++) {
      ten[i] = (ten[i - 1] * 10) % mod;
    }
    memset(dp, -1, sizeof(dp));
    printf("%lld\n", (solve(ri).sum - solve(le - 1).sum + mod) % mod);
  }
  return 0;
}

### Prompt

Your task is to create 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;
int gcd(int a, int b) { return a % b == 0 ? b : gcd(b, a % b); }
const int MAXN = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const long long INFLL = 0x3f3f3f3f3f3f3f3f;
const long long mod = 998244353;
long long l, r, k;
int str[25];
struct Res {
  long long cnt;
  long long sum;
};
Res temp, dp[25][1025][25];
long long ten[25];
Res DFS(int len, int now, int sum, int flag, int p) {
  long long ans = 0;
  long long cnt = 0;
  if (sum > k) {
    temp.cnt = temp.sum = 0;
    return temp;
  }
  if (len == 0) {
    temp.sum = 0, temp.cnt = 1;
    return temp;
  }
  if (flag == 0 && p == 0 && dp[len][now][sum].cnt != -1)
    return dp[len][now][sum];
  int up = flag ? str[len] : 9;
  for (int i = 0; i <= up; i++) {
    if (now & (1 << i)) {
      temp = DFS(len - 1, now, sum, flag && i == up, 0);
      cnt += temp.cnt;
      cnt %= mod;
      ans =
          (ans + temp.sum + (temp.cnt % mod) * (i % mod) * ten[len - 1] % mod) %
          mod;
    } else {
      if (p == 1 && i == 0) {
        temp = DFS(len - 1, now, sum, flag && i == up, 1);
        cnt += temp.cnt;
        ans = (ans + temp.sum) % mod;
      } else {
        temp = DFS(len - 1, now ^ (1 << i), sum + 1, flag && i == up, 0);
        cnt += temp.cnt;
        cnt %= mod;
        ans =
            (ans + temp.sum + (temp.cnt % mod) * i % mod * ten[len - 1] % mod) %
            mod;
      }
    }
  }
  temp.cnt = cnt;
  temp.sum = ans;
  if (flag == 0 && p == 0) dp[len][now][sum] = temp;
  return temp;
}
Res solve(long long x) {
  int len = 0;
  len = 0;
  while (x) {
    str[++len] = x % 10;
    x /= 10;
  }
  return DFS(len, 0, 0, 1, 1);
}
int main() {
  long long le, ri;
  ten[0] = 1;
  while (~scanf("%lld%lld", &le, &ri)) {
    scanf("%d", &k);
    for (int i = 1; i <= 22; i++) {
      ten[i] = (ten[i - 1] * 10) % mod;
    }
    memset(dp, -1, sizeof(dp));
    printf("%lld\n", (solve(ri).sum - solve(le - 1).sum + mod) % mod);
  }
  return 0;
}

```