問題文

整数 N が与えられます． 1 から N までの番号のついた N 頂点からなる無向グラフ G を考えます． 以下の条件をすべて満たすグラフ G の個数を 998244353 で割った余りを求めてください．

• G は多重辺や自己ループを含まない．
• G は連結である．
• G の頂点集合の分割 \{S_1,S_2,\cdots\} であって，以下の条件をみたすものが存在する．
  • 各 S_i について，|S_i| \geq 2 である．
  • 各 S_i について，S_i による誘導部分グラフは，連結な二部グラフである．

制約

• 2 \leq N \leq 2 \times 10^5
• 入力される値はすべて整数である

入力例 1

2

出力例 1

1

入力例 2

3

出力例 2

3

入力例 3

4

出力例 3

38

入力例 4

5

出力例 4

712

入力例 5

12345

出力例 5

503682022