003 - プロ技-再帰

時間制限 1 秒 / メモリ制限 64 MB / 得点 10 / x 6 /


TLE
1sec
MLE
64MB
得点
10

問題


$N$段の階段があります。
この階段を次の3通りの上り方を組み合わせて上るとき、全部で何通りの上り方がありますか?
(上り方)
・1段上に上る
・2段上に上る
・3段上に上る
ただし、答えを998244353で割った余りを求め、出力してください。

入力

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

$N$

1行目に整数$N$が与えられる。

出力

出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

  • $1 \leq N \leq 2×10^{5}$

入出力例

入力例1

3

出力例1

4

入力例2

5

出力例2

13

入力例3

10

出力例3

274

入力例4

200000

出力例4

176305517