配点 : $600$ 点

問題文

正整数列のうち、全ての隣接している $2$ 項が異なるものを素晴らしい整数列と定めます。

要素の総和が $N$ の素晴らしい整数列全てに対する長さの総和を $998244353$ で割ったあまりを求めてください。

制約

• $1 \le N \le 2 \times 10^5$
• 入力はすべて整数

入力

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

$N$

出力

答えを出力せよ。

4

8

要素の総和が $4$ の素晴らしい整数列は、$(4),(1,3),(3,1),(1,2,1)$ の $4$ 個です。なので、答えはこれらの長さの総和の $1+2+2+3=8$ です。

$(2,2)$ や $(1,1,2)$ は総和が $4$ ですが、両方 $1$ 項目と $2$ 項目が等しいため条件を満たしません。

297

475867236

123456

771773807