問題文

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}
• 入力は全て整数である。

入力例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