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>
static void print_int(int64_t n) {
  if (n < 0) {
    putchar('-');
    n = -n;
  }
  if (n == 0) {
    putchar('0');
    return;
  }
  int s[20], len = 0;
  while (n > 0) {
    s[len++] = n % 10 + '0';
    n /= 10;
  }
  while (len > 0) {
    putchar(s[--len]);
  }
}
static int64_t read_int(void) {
  int prev = '\0';
  int c = getchar();
  while (!('0' <= c && c <= '9')) {
    prev = c;
    c = getchar();
  }
  int64_t res = 0;
  while ('0' <= c && c <= '9') {
    res = 10 * res + c - '0';
    c = getchar();
  }
  return prev == '-' ? -res : res;
}
const int32_t mod = 998244353;
int32_t popcnt(int32_t n) {
  int32_t k = 0;
  while (n > 0) {
    k += n & 1;
    n >>= 1;
  }
  return k;
}
typedef struct count_val {
  int64_t cnt;
  int64_t sum;
} node;
int64_t calc(int64_t n, int32_t k) {
  if (n == 0) return 0;
  const int32_t p = 10;
  int32_t digit[20];
  int32_t len = 0;
  while (n > 0) {
    digit[len++] = n % p;
    n /= p;
  }
  node *now = ((node *)calloc((1 << p), sizeof(node)));
  node *next = ((node *)calloc((1 << p), sizeof(node)));
  int32_t sup = 0;
  int64_t sup_val = 0;
  for (int32_t i = len - 1; i >= 0; --i) {
    memset(next, 0, sizeof(node) * (1 << p));
    for (int32_t b = 0; b < (1 << p); ++b) {
      for (int32_t d = 0; d < p; ++d) {
        next[b | (1 << d)].sum += p * now[b].sum + d * now[b].cnt;
        next[b | (1 << d)].cnt += now[b].cnt;
      }
    }
    for (int32_t d = (i == len - 1 ? 1 : 0); d < digit[i]; ++d) {
      next[sup | (1 << d)].sum += sup_val * p + d;
      next[sup | (1 << d)].cnt += 1;
    }
    if (i < len - 1) {
      for (int32_t d = 1; d < p; ++d) {
        next[1 << d].sum += d;
        next[1 << d].cnt += 1;
      }
    }
    for (int32_t b = 0; b < (1 << p); ++b) {
      now[b].sum = next[b].sum % mod;
      now[b].cnt = next[b].cnt % mod;
    }
    sup |= 1 << digit[i];
    sup_val = (p * sup_val + digit[i]) % mod;
  }
  int64_t ans = popcnt(sup) <= k ? sup_val % mod : 0;
  for (int32_t i = 0; i < (1 << p); ++i) {
    if (popcnt(i) <= k) {
      ans += now[i].sum;
    }
  }
  free(now);
  free(next);
  return ans % mod;
}
void run(void) {
  int64_t l = read_int();
  int64_t r = read_int();
  int32_t k = read_int();
  int64_t ans = (calc(r, k) - calc(l - 1, k) + mod) % mod;
  print_int(ans);
  puts("");
}
int main(void) {
  run();
  return 0;
}
