AT_fps_24_o 根付き木

题目描述

考虑有 $N$ 个顶点的有根树，顶点编号为 $1$ 到 $N$，顶点 $1$ 为根。 请计算有多少种满足以下条件的有根树，并输出答案对 $998244353$ 取模后的结果。

• 对于每个 $1 \leq i \leq N$，顶点 $i$ 的儿子数要么为 $0$，要么为质数。

输入格式

输入从标准输入获取，格式如下：

$N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3

输出 #1

1

输入输出样例 #2

输入 #2

123456

输出 #2

607180670

说明/提示

样例解释 1

例如，考虑这样的有根树：顶点 $2$ 和顶点 $3$ 的父节点均为 $1$。 这个有根树满足条件，因为顶点 $1$ 有 $2$ 个儿子（$2$ 是质数），顶点 $2$ 和顶点 $3$ 都没有儿子（儿子数为 $0$）。 这是唯一一种满足条件的有根树。

数据范围

• $3 \leq N \leq 2.5 \times 10^5$
• $N$ 是整数。

由 ChatGPT 5 翻译