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>
#pragma GCC optimize("O3")
using namespace std;
int dp[20][1 << 10][2][2];
long long cnt[20][1 << 10][2][2];
vector<int> l, r;
const int M = 998244353;
void add(int &a, int b) { a = (a + b) % M; }
int pw[20];
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  pw[0] = 1;
  for (int i = 1; i <= 18; i++) {
    pw[i] = pw[i - 1] * 1ll * 10 % M;
  }
  long long L, R;
  int k;
  cin >> L >> R >> k;
  for (int i = 0; i < 20; i++) {
    l.push_back(L % 10);
    r.push_back(R % 10);
    L /= 10;
    R /= 10;
  }
  reverse(l.begin(), l.end());
  reverse(r.begin(), r.end());
  for (int digit = l[1]; digit <= r[1]; digit++) {
    dp[1][digit == 0 ? 0 : (1 << digit)][l[1] < digit][digit < r[1]] += digit;
    cnt[1][digit == 0 ? 0 : (1 << digit)][l[1] < digit][digit < r[1]]++;
  }
  for (int len = 1; len < 19; len++) {
    for (int mask = 0; mask < (1 << 10); mask++) {
      for (int p1 = 0; p1 < 2; p1++) {
        for (int p2 = 0; p2 < 2; p2++) {
          if (cnt[len][mask][p1][p2]) {
            for (int digit = 0; digit < 10; digit++) {
              if ((p1 || l[len + 1] <= digit) && (p2 || digit <= r[len + 1])) {
                int pp1 = p1 || (l[len + 1] < digit),
                    pp2 = p2 || (digit < r[len + 1]);
                int mmask = mask | (digit == 0 && mask == 0 ? 0 : (1 << digit));
                cnt[len + 1][mmask][pp1][pp2] += cnt[len][mask][p1][p2];
                add(dp[len + 1][mmask][pp1][pp2],
                    (dp[len][mask][p1][p2] + (digit * 1ll * pw[18 - len] % M) *
                                                 (cnt[len][mask][p1][p2] % M) %
                                                 M) %
                        M);
              }
            }
          }
        }
      }
    }
  }
  int ans = 0;
  for (int mask = 0; mask < (1 << 10); mask++) {
    if (__builtin_popcount(mask) <= k) {
      for (int p1 = 0; p1 < 2; p1++) {
        for (int p2 = 0; p2 < 2; p2++) {
          add(ans, dp[19][mask][p1][p2]);
        }
      }
    }
  }
  cout << ans;
}
