Description

给定三个正整数 $l, r, k$，求 $[l, r]$ 之间的各数位上包含的不同数字不超过 $k$ 个的所有数的和，答案对 $998244353$ 取模

例：$1212$ 包含的不同数字数量为 $2$，$1234$ 包含的不同数字数量为 $4$

Format

Input

输入三个正整数 $l, r, k(1 \leq l \leq r \leq 10^{18}, 1 \leq k \leq 10)$

Output

输出一个正整数，表示符合要求的所有数的和

Samples

10 20 1

11

1 2345 10

2750685

Hint