P8362 [SNOI2022] Digits

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$.

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

**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. | Test Point | $R