Problem Description

Xiao S is a girl who loves counting numbers.

One day, while counting numbers in bed before sleep, she reached the number $977431$ and finally felt sleepy, deciding to go to sleep. However, she suddenly noticed that the digits of this number were in non-increasing order! She found this quite interesting and couldn't fall asleep.

She wondered how many numbers between $L$ and $R$ have digits in non-increasing order. But this problem seemed too boring.

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

Finally, she came up with a more interesting problem:

Given integers $L$, $R$, and $k$, find how many $k$-dimensional vectors $(a_1, a_2, ..., a_k)$ satisfy that the digits of $(a_1 + a_2 + ... + a_k)$ are in non-increasing order, and $\forall i \in [1, k], L \leq a_i \leq R$.

Since the answer might be very large, output it modulo $998244353$.

Input Format

The first line of input contains a positive integer $L$, as described in the problem statement.

The second line contains a positive integer $R$, as described in the problem statement.

The third line contains a positive integer $k$, as described in the problem statement.

Output Format

Output a single integer representing the number of valid vectors, modulo $998244353$.

Sample Input and Output

Sample Input #1

1
100
2

Sample Output #1

3728

Sample Input #2

19260817
1000000000
3

Sample Output #2

28745082

Sample Input #3

114514233
1919810233
10

Sample Output #3

135934411

Sample Input #4

See attached file digit4.in

Sample Output #4

See attached file digit4.ans

Sample Input #5

See attached file digit5.in

Sample Output #5

See attached file digit5.ans

Notes/Hints

[Data Range and Constraints]

For all data, $1 \leq L \leq R < 10^{1000}$, $1 \leq k \leq 50$.

The specific data range and constraints are as follows:

见题面 Input 部分

见题面 Output 部分