問題文

非負整数 $x$ について、関数 $f(x)$ を次のように定めます。

• $f(0) = 8$
• $f(1) = 88$
• $f(x) = f(x - 1) + f(x - 2) \: (2 \leq x)$

$f(N)$ の値を $998244353$ で割った余りを求めてください。

制約

• $0 \leq N \leq 10^{18}$
• 入力はすべて整数である。

入力

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

N

出力

問題の答えを一行に出力せよ。

入出力例

3

184

$f(2) = f(0) + f(1) = 8 + 88 = 96$
$f(3) = f(1) + f(2) = 88 + 96 = 184$
であるので、$184$ を出力します。

100

642685655

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