M - Connected Graph Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 4 点

問題文

頂点に 1 から N の番号がついた N 頂点の単純連結無向グラフの個数を 998244353 で割った余りを求めてください。

制約

  • 1 \leq N \leq 2.5 \times 10^5
  • N は整数

入力

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

N

出力

答えを出力せよ。

入力例 1

3

出力例 1

4

3 頂点の単純連結無向グラフは、 2 辺のグラフが 3 個、3 辺のグラフが 1 個で合計 4 個あります。

入力例 2

123456

出力例 2

317059543

Score: 4 points

Problem Statement

Count the number of simple connected undirected graphs with N vertices labeled 1 through N.
Output the result modulo 998244353.

Constraints

  • 1 \leq N \leq 2.5 \times 10^5
  • N is an integer

Input

The input is given from standard input in the following format:

N

Output

Print the answer.

Sample Input 1

3

Sample Output 1

4

For N=3, the simple connected undirected graphs are:

  • 3 graphs with 2 edges,
  • 1 graph with 3 edges,

for a total of 4.

Sample Input 2

123456

Sample Output 2

317059543