1073_E. Segment Sum
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.
```python
import sys
from array import array  # noqa: F401
import typing as Tp  # noqa: F401


def input():
    return sys.stdin.buffer.readline().decode('utf-8')


def main():
    l, r, k = map(int, input().split())

    valid_bits, is_valid_bits = [], [0] * 1024

    for bit in range(1024):
        if bin(bit).count('1') <= k:
            valid_bits.append(bit)
            is_valid_bits[bit] = 1

    mod = 998244353

    def solve(ub):
        dp = array('i', [0]) * 1024
        dp_cnt = array('i', [0]) * 1024
        next_dp = array('i', [0]) * 1024
        next_dp_cnt = array('i', [0]) * 1024
        boundary_dp, b_bit = 0, 0

        for e, digit in zip(range(len(str(ub)) - 1, -1, -1), map(int, str(ub))):
            base = pow(10, e, mod)

            for bit in valid_bits:
                for d in range(10):
                    nextbit = bit | (1 << d)
                    if is_valid_bits[nextbit]:
                        next_dp[nextbit] = (
                            next_dp[nextbit] + dp[bit]
                            + base * d * dp_cnt[bit]
                        ) % mod

                        next_dp_cnt[nextbit] += dp_cnt[bit]
                        if next_dp_cnt[nextbit] >= mod:
                            next_dp_cnt[nextbit] -= mod

            for d in range(digit):
                nextbit = b_bit | (1 << d)
                if is_valid_bits[nextbit]:
                    next_dp[nextbit] = (
                        next_dp[nextbit] + boundary_dp + base * d
                    ) % mod
                    next_dp_cnt[nextbit] += 1

            b_bit |= (1 << digit)
            boundary_dp = (boundary_dp + base * digit) % mod

            for i in valid_bits:
                dp[i] = next_dp[i]
                dp_cnt[i] = next_dp_cnt[i]
                next_dp[i] = next_dp_cnt[i] = 0

            dp[0], dp_cnt[0] = 0, 1
            dp[1] = dp_cnt[1] = 0

        return (sum(dp) + (boundary_dp if is_valid_bits[b_bit] else 0)) % mod

    # print(solve(r), solve(l - 1))
    print((solve(r) - solve(l - 1)) % mod)


if __name__ == '__main__':
    main()

```