Problem Description

Little S is a girl who likes counting.

One day, she was lying in bed counting before sleep. When she counted to $977431$, she finally felt sleepy and decided to go to sleep. But then she suddenly noticed that the digits of this number are monotonically non-increasing. She found it quite interesting, and then she could not fall asleep again.

She wants to know how many numbers are between $L$ and $R$ whose digits are monotonically non-increasing. But this problem is too boring.

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

Finally, she came up with a more interesting problem:

Given integers $L, R, 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 monotonically non-increasing, and $\forall i \in [1, k], L \leq a_i \leq R$.

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

Input Format

The first line 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 one line with one integer, the number of valid vectors modulo $998244353$.

1
100
2

3728

19260817
1000000000
3

28745082

114514233
1919810233
10

135934411

样例 4 见附件 digit4.in

样例 4 见附件 digit4.ans

样例 5 见附件 digit5.in

样例 5 见附件 digit5.ans

Hint

Constraints

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

The detailed constraints are given in the table below.

Translated by ChatGPT 5