Let's Go Cycling

問題文

$N$ 頂点 $0$ 辺のグラフがあります。このグラフの各頂点 $i$ について

• 一様ランダムに頂点 $j\ (j \neq i)$ を一つ選び、有向辺 $i \rarr j$ を張る

という操作を行います。このとき、操作によってできる閉路の個数の期待値を $\mathrm{mod}\ 998244353$ で求めてください。

制約

• $N$ は $2$ 以上 $10^6$ 以下の整数

入力

出力

答えを出力し、最後に改行してください。

入力例1

2

出力例1

1

必ず $1 \rarr 2$ と $2 \rarr 1$ を張ることになるので閉路の個数の期待値は $1$ です。

入力例2

3

出力例2

1

入力例3

1000000

出力例3

671367562