M - Formula
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
1
, 2
, 3
, 4
, 5
, 6
, 7
, 8
, 9
, +
,*
の 11 種類の文字からなる、長さ N の文字列を考えます。
このような文字列は全部で 11^N 通りありますが、そのうち式として成り立っているものすべての計算結果の和を、998244353 で割ったあまりで求めてください。
ただし、文字列 S が式として成り立っているとは、
- S の先頭と末尾の文字は
+
でも*
でもない - S から連続する 2 文字をとってきたとき、少なくとも一方は
+
でも*
でもない
ことを指します。
また、式に含まれる整数は全て 10 進数表記であるとし、式の計算は普通の四則演算に基づいて行われるものとします。例えば、文字列 22+3*4
の計算結果は 34 にな ります。
制約
- 1 \leq N \leq 10^{18}
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを 1 行に出力せよ。
入力例1
1
出力例1
45
あり得る文字列は 1
, 2
, 3
, 4
, 5
, 6
, 7
, 8
, 9
の 9 通りであり、それぞれの計算結果は 1,2,3,4,5,6,7,8,9 となるので、求めるべき値はこれらの総和である 45 になります。
入力例2
3
出力例2
407430
成り立っている式の例として、239
, 2+5
, 5*8
などがあります。
入力例3
1000000000000000000
出力例3
493565653