按顺序连成树¶
预估时间限制：0.5 秒。内存限制：128 MB。
实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。
背景故事¶
一座展馆有若干个带编号的展区。施工队逐条铺设双向通道，希望最后任意两个展区之间恰好存在一条简单路线。请统计不同的施工顺序。
(本故事由GPT-6重写)
形式化问题描述¶
有 \(n\) 个互不相同的顶点，初始没有边。每一步在两个不同顶点之间加入一条无向边，同一对顶点至多加入一条边。最终任意两个不同顶点之间必须恰好有一条简单路径。
统计满足条件的加边序列数，答案对 \(998244353\) 取模。最终边集不同，或边的添加顺序不同，均视为不同方案。\(n=0\) 或 \(n=1\) 时，唯一的空操作序列满足条件。
输入格式¶
一行一个非负整数 \(n\) .
输出格式¶
输出一行一个整数，表示答案的非负最小剩余。
样例¶
样例 1¶
输入¶
0
输出¶
1
样例 2¶
输入¶
3
输出¶
6
样例 3¶
输入¶
104
输出¶
68933342
样例解释¶
空图只有空操作序列。三个顶点有三种树，每棵树的两条边可以按两种顺序加入，所以有六种方案。图中展示其中一棵树的两种顺序。
数据范围与保证¶
\(0\le n\le10^6\) .下表中的 \(100/3\%\) 表示总分的精确三分之一；前两组合计三分之二的数据满足 \(n\le3000\) .
| 分值比例 | 额外条件 |
|---|---|
| 100/3% | \(n\le104\) |
| 100/3% | \(n\le3000\) |
| 100/3% | 无额外条件 |