問題文

正整数 N が与えられます。以下の条件を満たす長さ N の正整数列 A=(A_1,A_2,\dots,A_N) の個数を 998244353 で割った余りを求めてください。

• 頂点に 1,2,\dots,N と番号が振られた N 頂点単純無向連結グラフ G であって、以下を満たすものが存在する。
  • 任意の整数 i (1 \leq i \leq N) について、G における頂点 i に隣接する頂点の頂点番号の最大値は A_i である。

制約

• 2 \leq N \leq 200000
• 入力は全て整数

部分点

• N \leq 200 を満たすデータセットに正解した場合は、30 点与えられる。
• 追加制約のないデータセットに正解した場合は、上記とは別に 70 点与えられる。

入力例 1

3

出力例 1

3

A としてありうる整数列は、(2,3,2),(3,1,1),(3,3,2) の 3 つです。

入力例 2

5

出力例 2

99

入力例 3

10

出力例 3

14352615