ABC357 D

これのD問題です

Nが10の18乗まであるため、2倍ずつ積み重ねることを考える。
2つの配列を作る

$Q[i]=N$を$2^i$個積み重ね
$P[i]=10^{Nの桁数*2^i}$
もちろん mod $998244353$ で計算する。

これを$2^i$が$N$を超えないところまでappend。

そして$N$の2進法表示で$2^i$の位が$1$の時に
$N$の$2^i$個積み重ねたものを連結して mod を取ればそれが答えとなる

#(ヘッダは省略)

MOD = 998244353

N=int(input())
	
def main():
	kt = len(str(N))
	#print(kt)
	Q = []
	P = [1]
	i = 1
	M = N
	while i <= N:
		if i == 1:
			Q.append(N % MOD)
			P.append(10**kt)
		else:	
			Q.append((Q[-1]+P[-1]*Q[-1])%MOD)
			P.append((P[-1]**2)%MOD)
		i *= 2
	#print(Q)
	#print(P)
		
	M = N
	j = 0
	ans = 0
	while M > 0:
		if M % 2 == 1:
			ans = (ans * P[j+1] + Q[j]) % MOD
		M //= 2
		j += 1
	print(ans)
				
			
if __name__ == "__main__":
	main()