Little S is a girl who loves counting.

One day, while lying in bed counting before sleep, she reached $977431$ and finally felt sleepy, so she decided to go to sleep. However, she suddenly noticed that the digits of this number are monotonically non-increasing! She found this quite interesting, and as a result, she couldn't fall asleep again.

She wondered how many numbers between $L$ and $R$ have digits that are monotonically non-increasing. But this problem was too boring.

She then wondered how many pairs $(a, b)$ between $L$ and $R$ exist such that the digits of $(a + b)$ are monotonically non-increasing. But this problem was also too boring.

Finally, she thought of a more interesting problem: Given integers $L, R, k$, find how many $k$-dimensional vectors $(a_1, a_2, \dots, a_k)$ exist such that the digits of $(a_1 + a_2 + \dots + a_k)$ are monotonically non-increasing, and $\forall i \in [1, k], L \le a_i \le R$.

She could not solve it. Since the answer can be very large, you only need to help her find the answer modulo $998244353$.

Input

The input consists of three lines. The first line contains a positive integer $L$, the second line contains a positive integer $R$, and the third line contains a positive integer $k$. See the description for their specific meanings.

Output

Output a single non-negative integer representing the number of $k$-dimensional vectors $(a_1, a_2, \dots, a_k)$ satisfying the requirements, modulo $998244353$.

Examples

Input 1

1
100
2

Output 1

3728

Input 2

19260817
1000000000
3

Output 2

28745082

Input 3

114514233
1919810233
10

Output 3

135934411

Constraints

For all data, $1 \le L \le R < 10^{1000}$, $1 \le k \le 50$. The specific data constraints are shown in the table below.