题目描述

小 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$，含义见【题目描述】。

输出格式

输出一行一个整数表示合法的向量数，答案 $998244353$ 取模。

样例 #1

样例输入 #1

1
100
2

样例输出 #1

3728

样例 #2

样例输入 #2

19260817
1000000000
3

样例输出 #2

28745082

样例 #3

样例输入 #3

114514233
1919810233
10

样例输出 #3

135934411

样例 #4

样例输入 #4

样例 4 见附件 digit4.in

样例输出 #4

样例 4 见附件 digit4.ans

样例 #5

样例输入 #5

样例 5 见附件 digit5.in

样例输出 #5

样例 5 见附件 digit5.ans

提示

【数据规模与约定】

对于全部数据，$1 \leq L \leq R < 10^{1000}$，$1 \leq k \leq 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$