问题描述

给定整数$N$，解决以下问题。

令$f(x)=$ (最大为$x$的与$x$有相同位数的正整数的个数)。
找出$f(1)+f(2)+\\dots+f(N)$在模$998244353$下的值。

约束条件

• $N$是一个整数。
• $1 \\le N < 10^{18}$

输入

输入以以下格式从标准输入给出：

$N$

输出

以整数形式输出答案。

示例输入1

16

示例输出1

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$。

示例输入2

238

示例输出2

13870

示例输入3

999999999999999999

示例输出3

762062362

一定要在模$998244353$下计算总和。