分数: 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