#3730. 「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$ 取模的结果。

输入格式

输入包含三行，第一行包含一个正整数 $L$，第二行包含一个正整数 $R$，第三行包含一个正整数 $k$，具体意义见「题目描述」。

输出格式

输出一行一个非负整数，表示满足上述要求的 $k$ 维向量 $(a_1, a_2, \ldots , a_k)$ 的个数对 $998244353$ 取模的值。

---

样例 1

输入

1
100
2

输出

3728

---

样例 2

输入

19260817
1000000000
3

输出

28745082

---

样例 3

输入

114514233
1919810233
10

输出

135934411

---

样例 4

见附加文件中 digit4.in 和 digit4.ans。

---

样例 5

见附加文件中 digit5.in 和 digit5.ans。

---

数据范围与提示

对于全部数据，$1\le L\le R< 10^{1000}$，$1\le k\le 50$。

具体的数据规模与约定见下表。

测试点编号	$R$	$k$
1	$< 10^6$	1
2		10
3		20
4		30
5		50
6	$< 10^{17}$	10
7
8		20
9		30
10		50
11	$< 10^{50}$	2
12		10
13	$< 10^{100}$	2
14		3
15		10
16	$< 10^{200}$	3
17		10
18	$< 10^{300}$
19
20		20
21	$< 10^{500}$	10
22		20
23	$< 10^{1000}$	30
24		50
25

---