問題文

11 以上 NN 以下の正整数全体の集合 A={1,2,...,N}A = \{1, 2, ..., N\} があります.AA の部分集合 XX であって,以下の条件を満たすものが何通りあるか求めてください.

  • 任意の正整数 kXk \in X について k+1Xk+1 \notin X

ただし答えは非常に大きくなる可能性があるので,998244353998244353 で割った余りを出力してください.

制約

  • 1N2×1051 \leq N \leq 2\times10^5
  • NN は整数である

入力

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

NN

出力

答えを出力せよ.

サンプル

入力例1
2
出力例1
3

{},{1},{2}\{\}, \{1\}, \{2\} が条件を満たします.

入力例2
3
出力例2
5

{},{1},{2},{3},{1,3}\{\}, \{1\}, \{2\}, \{3\}, \{1,3\} が条件を満たします.

入力例3
2022
出力例3
124881012

提出


Go (1.21)