背景

この問題は kroton さんによって原案が提案され、noshi91 が解いたものです。

問題文

正整数列 $R _ n$ を以下のように定めます。

• $R _ 1 = 1$
• $R _ n = \operatorname{cat}(R _ {n - 1}, n, R _ {n - 1}) \quad (n \geq 2)$

入力

$n$

• $1 \leq n \lt 10^{18}$
• $n$ は整数

出力

$R _ n$

$998244353$ で割った余りを出力してください。

サンプル

3

1213121

10

269257815