AT_abc387_g.[ABC387G] Prime Circuit

给定编号为 $1$ 到 $N$ 的 $N$ 个顶点的简单无向连通图 $G$，求满足以下条件的图的数量对 $998244353$ 取模的结果：

• $G$ 中任意回路的边数均为素数。
  此处回路定义为允许重复经过顶点但不允许重复经过边的闭路径。

输入通过标准输入给出，格式如下：

$N$

输出满足条件的简单无向连通图 $G$ 的数量对 $998244353$ 取模后的结果。

约束条件

• $N$ 是满足 $1 \leq N \leq 2.5 \times 10^5$ 的整数

样例解释 1

满足条件的图 $G$ 有以下 4 种：

• 边集为 $(1, 2), (1, 3)$ 的图
• 边集为 $(1, 2), (2, 3)$ 的图
• 边集为 $(1, 3), (2, 3)$ 的图
• 边集为 $(1, 2), (1, 3), (2, 3)$ 的图

翻译由 DeepSeek R1 完成