← 返回题目列表

AtCoder · abc387_g

G. Prime 电路

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

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