問題設定に重大な誤りがありました。条件を追加することにより対応しました。

問題文

$1,2, \dots ,N$ と番号付けられた $N$ 人の人がいます。最初，$N$ 人のうちどの二人組も直接友人ではありません。

あなたは今から，以下の操作をちょうど $N-1$ 回行います。

• $N$ 人のうちから二人選んで，その二人を直接友人にさせる。

また，$N-1$ 回の操作終了後，以下の条件を満たす必要があります。

条件：$N-1$ 回の操作が終了した後，全ての $i$ $(1 \leq i \leq N)$ で，人 $i$ について，人 $i$ の直接の友人，またその友人の直接の友人… というように，直接の友人を辿っていくことで，人 $i$ 以外の全ての人に行きつく。

ありえる $N$ 人の友人関係は何通りあるでしょう？

$N-1$ 回の操作を終えた後の $N$ 人の友人関係 $X$ と，$N$ 人の友人関係 $Y$ について，ある二人組 $p, q \: (1 \leq p,q \leq N)$ で、「$X$ では直接の友人であるが、$Y$ では直接の友人ではないような組」または 「$X$ では直接の友人ではないが、$Y$ では直接の友人であるような組」 である場合，友人関係 $X$ と $Y$ は区別することにします。

ありえる $N$ 人の友人関係の場合の数を $998244353$ （この値は素数です。）で割った余りで出力してください。

制約

$2 \leq N \leq 10^{9}$

入力

出力

ありえる $N$ 人の友人関係の場合の数を $998244353$ で割った余りで一行に出力してください。改行を忘れないこと。

入力例 $1$

2

出力例 $1$

1

$2$ 人を人 $1$ と 人 $2$ と書くことにし，人 $a,b$ 間の友人関係を $\{a,b\}$ で表すことにします。
最終的な友人関係は $\{ 1,2 \}$ の $1$ 通りのみです。$\{ 2,1 \}$ は $\{ 1,2 \}$ と同一視されることに注意してください。
よって，$1$ を $998244353$ で割った余りである $1$ を出力すればよいです。

入力例 $2$

3

出力例 $2$

3

最終的な友人関係は $\{ \{ 1,2 \} , \{ 1,3 \} \}$ , $\{ \{ 1,2 \} , \{ 2,3 \} \}$ , $\{ \{ 1,3 \} , \{ 2,3 \} \}$ の $3$ 通りです。
よって，$3$ を $998244353$ で割った余りである $3$ を出力すればよいです。