分数: 675 点
问题陈述
求模数 998244353,简单的无向连通图 G 与 N 顶点标记自 1 to N 满足以下条件:
- 对于每个电路 G,该电路中的边数是素数。
这里,环路是一条闭合路径,可以多次通过同一顶点(但不得多次使用同一边)。
约束
- N 是 1 到 1 之间的整数 2.5 \times 10^5,包括在内。
输入
输入由标准输入按以下格式给出:
N
输出
打印数字,模数 998244353,简单的无向连通图 G 满足条件。
示例输入 1
3
示例输出 1
4
有四个这样的图 G:
- 有边的图 (1, 2) 和 (1, 3)
- 有边的图 (1, 2) 和 (2, 3)
- 有边的图 (1, 3) 和 (2, 3)
- 有边的图 (1, 2), (1, 3),和 (2, 3)
示例输入 2
2025
示例输出 2
879839321
示例输入 3
61261
示例输出 3
202537766