O - Rooted Tree Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 5 点

問題文

頂点に 1 から N の番号がついていて、頂点 1 を根とする N 頂点の根付き木のうち次の条件を満たすものの個数を 998244353 で割った余りを求めてください。

  • 1 \leq i \leq N を満たす全ての整数 i について、i の子の個数は 0 または素数である。

制約

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

入力

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

N

出力

答えを出力せよ。

入力例 1

3

出力例 1

1

例えば頂点 2 と頂点 3 の親がともに頂点 1 である根付き木は条件を満たします。なぜならば、頂点 1 の子の個数は 2 個(素数) で、頂点 2 と頂点 3 の子の個数は 0 個だからです。
条件を満たす木は上に説明した木の 1 個のみです。

入力例 2

123456

出力例 2

607180670

Score: 5 points

Problem Statement

Consider rooted trees with N vertices, where the vertices are labeled 1 through N, and vertex 1 is the root.
Count how many such rooted trees satisfy the following condition, and output the result modulo 998244353.

  • For every integer i such that 1 \leq i \leq N, the number of children of vertex i is either 0 or a prime number.

Constraints

  • 3 \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

1

For example, consider the rooted tree where both vertex 2 and vertex 3 have parent 1.
This satisfies the condition because vertex 1 has 2 children (a prime number), and vertices 2 and 3 both have 0 children.
This is the only rooted tree that satisfies the condition.

Sample Input 2

123456

Sample Output 2

607180670