配点 : $300$ 点

問題文

整数 $N$ が与えられるので、以下の問題を解いてください。

$f(x)=$ ( $x$ 以下の正整数で、 $x$ と桁数が同じものの数) とします。 $f(1)+f(2)+\dots+f(N)$ を $998244353$ で割った余りを求めてください。

制約

• $N$ は整数
• $1 \le N < 10^{18}$

入力

入力は以下の形式で標準入力から与えられる。

$N$

出力

答えを整数として出力せよ。

16

73

• $1$ 以上 $9$ 以下の正整数 $x$ について、 $x$ 以下の整数で、 $x$ と桁数が同じものは $1,2,\dots,x$ です。- これより、 $f(1)=1,f(2)=2,...,f(9)=9$ となります。
• $10$ 以上 $16$ 以下の正整数 $x$ について、 $x$ 以下の整数で、 $x$ と桁数が同じものは $10,11,\dots,x$ です。- これより、 $f(10)=1,f(11)=2,...,f(16)=7$ となります。

結局、求める答えは $73$ です。

238

13870

999999999999999999

762062362

$998244353$ で割った余りを求めることに注意してください。