G. Good Number
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

对于非负整数 $$$x$$$ 和 $$$i$$$($$$0 \leq x$$$,$$$0 \leq i \leq 9$$$),我们定义 $$$F(x, i)$$$ 表示 $$$x$$$ 的十进制表示下数字 $$$i$$$ 的出现次数。

对于非负整数 $$$x$$$($$$0 \leq x$$$),我们定义它的美观程度 $$$G(x)$$$ 为:

$$$$$$ G(x) = \sum_{\substack{0 \leq i \leq 9 \\ F(x, i) \gt 0}} F(x, i)^{F(x, i)} $$$$$$

例如,$$$x = 1145$$$ 时,由于 $$$F(x, 1)=2$$$,$$$F(x, 4)=1$$$,$$$F(x, 5)=1$$$,其余 $$$F(x, i)$$$ 均为 $$$0$$$,因此 $$$G(x) = 2^2 + 1^1 + 1^1 = 6$$$。

给定三个正整数 $$$L$$$、$$$R$$$、$$$K$$$,请你计算一下:

  • 在 $$$[L, R]$$$ 范围内的所有整数中,有多少个数的美观程度 $$$G(x) \geq K$$$?
  • 这些满足条件的数的美观程度的总和是多少?由于结果可能很大,请输出答案对 $$$998 \, 244 \, 353$$$ 取模后的结果。

注意只有第二个问题的答案需要对 $$$998 \, 244 \, 353$$$ 取模。

Input

仅一行,包含三个整数 $$$L, R, K$$$($$$1 \leq L \leq R \leq 10^{15}$$$ 且 $$$1 \leq K \leq 10^{18}$$$)。

Output

输出一行,包含两个整数,分别表示两个问题的答案。

Examples
Input
1 100 1
Output
100 212
Input
1000000000000000 1000000000000000 1
Output
1 567381139
Input
1 1000000000000000 114514
Output
2968291384813 671467889