← 返回题目列表

AtCoder · fps_24_o

O. 有根树

中文机器翻译题面 查看原题

分数: 5 点

问题陈述

考虑有根树 N 顶点,其中顶点被标记 1 通过 N和顶点 1 是根。
计算有多少个这样的有根树满足以下条件,并输出结果模 998244353.

  • 对于每个整数 i 这样 1 \leq i \leq N,顶点的子节点数 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 孩子们。
这是唯一满足条件的有根树。


示例输入 2

123456

示例输出 2

607180670