Migrated from Lutece 2595 数字求和

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

一个数字的多样程度是把该数字看作一个字符串后，这个字符串所包含的字符种类数。例如，数字 $11223300$ 包含四种字符 $0,1,2,3$，多样程度为 $4$；数字 $666$ 只有一种字符 $6$，多样程度为 $1$。

现在你想把区间 $[L,R]$ 中多样程度不超过 $N$ 的数全部相加，输出和对 $998244353$ 取模后的结果。

Input

输入三个整数 $L,R,N$。

Output

输出一个整数，表示答案对 $998244353$ 取模后的结果。

Samples

1 50 1

155

123 123456789 2

876375760

Constraints

$1\leq L \leq R <10^{18}$ $1\leq N \leq 10$

Note

样例 $1$ 中需要相加的数为 $1,2,3,4,5,6,7,8,9,11,22,33,44$。

Resources

2021 UESTC ICPC Training for Dynamic Programming