[SNOI2022] 数位

小 S 是一个喜欢数数的女孩子。 有一天，她在睡前躺在床上数数，当她数到 $977431$ 的时候，她终于困了，并且决定睡觉。但此时她突然发现这个数字的各位数码是单调不增的！她觉得这相当有趣，于是她又睡不着了。 她想知道有多少个数在 $L, R$ 之间，并且它的各位数码是单调不增的。但这个问题太无聊了。 她又想知道有多少数对 $(a, b)$ 在 $L, R$ 之间，并且 $(a + b)$ 的各位数码是单调不增的。但这个问题也太无聊了。 终于，她想到了一个有趣一些的问题： 给定整数 $L, R, k$，求有多少个 $k$ 维向量 $(a_1, a_2, ..., a_k)$ 满足 $(a_1 + a_2 + ... + a_k)$ 的数码是单调不增的，并且 $\forall i \in [1, k], L \leq a_i \leq R$。 由于答案可能很大，请你输出它对 $998244353$ 取模的结果。 ## Input 输入的第一行是一个正整数 $L$，含义见【题目描述】。 输入的第二行是一个正整数 $R$，含义见【题目描述】。 输入的第三行是一个正整数 $k$，含义见【题目描述】。 ## Output 输出一行一个整数表示合法的向量数，答案 $998244353$ 取模。 [samples] ## Note **【数据规模与约定】** 对于全部数据，$1 \leq L \leq R < 10^{1000}$，$1 \leq k \leq 50$。 具体的数据规模与约定见下表。 | 测试点编号 | $R<$ | $k$ | | :--------: | :---------: | :--: | | $1$ | $10^6$ | $1$ | | $2$ | $10^6$ | $10$ | | $3$ | $10^6$ | $20$ | | $4$ | $10^6$ | $30$ | | $5$ | $10^6$ | $50$ | | $6$ | $10^{17}$ | $10$ | | $7$ | $10^{17}$ | $10$ | | $8$ | $10^{17}$ | $20$ | | $9$ | $10^{17}$ | $30$ | | $10$ | $10^{17}$ | $50$ | | $11$ | $10^{50}$ | $2$ | | $12$ | $10^{50}$ | $10$ | | $13$ | $10^{100}$ | $2$ | | $14$ | $10^{100}$ | $3$ | | $15$ | $10^{100}$ | $10$ | | $16$ | $10^{200}$ | $3$ | | $17$ | $10^{200}$ | $10$ | | $18$ | $10^{300}$ | $10$ | | $19$ | $10^{300}$ | $10$ | | $20$ | $10^{300}$ | $20$ | | $21$ | $10^{500}$ | $10$ | | $22$ | $10^{500}$ | $20$ | | $23$ | $10^{1000}$ | $30$ | | $24$ | $10^{1000}$ | $50$ | | $25$ | $10^{1000}$ | $50$ |