AT_fps_24_m 連結グラフ

题目描述

计算有 $N$ 个结点（编号为 $1$ 到 $N$）、无重边无自环、连通的无向图的个数。
输出结果模 $998244353$。

输入格式

从标准输入读取一行：

$N$

输出格式

输出答案。

输入输出样例 #1

输入 #1

3

输出 #1

4

输入输出样例 #2

输入 #2

123456

输出 #2

317059543

说明/提示

样例解释 1

当 $N=3$ 时，所有连通的简单无向图如下：

• $3$ 个有 $2$ 条边的图，
• $1$ 个有 $3$ 条边的图，

总共有 $4$ 个。

数据范围

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

由 ChatGPT 5 翻译