G - Prime Circuit Editorial /

Time Limit: 12 sec / Memory Limit: 1024 MiB

配点 : 675 点

問題文

頂点に 1 から N までの番号がついた N 頂点の単純無向連結グラフ G のうち次の条件を満たすものの個数を 998244353 で割った余りを求めてください。

  • G に含まれる任意の回路の辺数が素数である。
    ここで回路とは、同じ頂点を 2 回以上通ってもよい閉路を意味する。(同じ辺を 2 回以上通ってはならない)

制約

  • N は 1 以上 2.5 \times 10^5 以下の整数

入力

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

N

出力

問題文の条件を満たす単純無向連結グラフ G の個数を 998244353 で割った余りを出力せよ。

入力例 1

3

出力例 1

4

条件を満たすグラフ G は以下の 4 個です。

  • (1, 2), (1, 3) を辺集合に持つグラフ
  • (1, 2), (2, 3) を辺集合に持つグラフ
  • (1, 3), (2, 3) を辺集合に持つグラフ
  • (1, 2), (1, 3), (2, 3) を辺集合に持つグラフ

入力例 2

2025

出力例 2

879839321

入力例 3

61261

出力例 3

202537766

Score : 675 points

Problem Statement

Find the number, modulo 998244353, of simple undirected connected graphs G with N vertices labeled from 1 to N that satisfy the following condition:

  • For every circuit in G, the number of edges in that circuit is a prime number.
    Here, a circuit is a closed trail that may pass through the same vertex more than once (but must not use the same edge more than once).

Constraints

  • N is an integer between 1 and 2.5 \times 10^5, inclusive.

Input

The input is given from Standard Input in the following format:

N

Output

Print the number, modulo 998244353, of simple undirected connected graphs G satisfying the condition.

Sample Input 1

3

Sample Output 1

4

There are four such graphs G:

  • The graph with edges (1, 2) and (1, 3)
  • The graph with edges (1, 2) and (2, 3)
  • The graph with edges (1, 3) and (2, 3)
  • The graph with edges (1, 2), (1, 3), and (2, 3)

Sample Input 2

2025

Sample Output 2

879839321

Sample Input 3

61261

Sample Output 3

202537766