問題文

正の整数 $n$ が与えられます。
フィボナッチ数列の第 $n$ 項を $998244353$ で割った余りを求めてください。
なお，ここでは，フィボナッチ数列の第 $1$ 項は $1$ ，第 $2$ 項は $1$ であるとします。

制約

• $1≤n≤10^{18}$
• $n$ は整数である。

入力

制約を満たす正の整数 $n$ が一行に与えられます。

出力

フィボナッチ数列の第 $n$ 項を $998244353$ で割った余りを出力してください。

入力例 $1$

1

出力例 $1$

1

フィボナッチ数列の第 $1$ 項は $1$ です。

入力例 $2$

1000000000000000000

出力例 $2$

23849548