题目描述

给定一个$n$,求出$1$~$n$所有数的数位积的和,结果对 $998244353$取余,就是把$1$~$n$的每一个数字的每一位相乘再求和
换句话说求:

$$\left (\sum_{i=1}^{n}\prod_{k=1}^{cnt_{i}}d_{k} \right )\bmod 998244353 $$

$d_{k}$表示数字$i$的第$k$位,$i$的数位为$dig(i)$,$i$的每一位为$d_{1},d_{2},...,d_{dig(i)}，cnt_{i}$为数字$i$的数位个数
比如求$8734$的数位积就是： $d_{1}=4,d_{2}=3,d_{3}=7,d_{4}=8,cnt_{8734}=4$

$$\prod_{k=1}^{cnt_{8734}}d_{k} =4\times 3\times 7\times 8=672 $$

输入格式

测试用例的第一行也是唯一一行包含一个整数 $n$ ($1 \le n \le 10^{6}$)

输出格式

输出$1$~$n$所有数的数位积的和,结果对$998244353$取余

样例

10

45

$$\left (\sum_{i=1}^{10}\prod_{k=1}^{cnt_{i}}d_{k} \right )\bmod 998244353=(1+2+3+4+5+6+7+8+9+0)\bmod 998244353=45 $$