# 按顺序连成树

预估时间限制：0.5 秒。内存限制：128 MB。

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

一座展馆有若干个带编号的展区。施工队逐条铺设双向通道，希望最后任意两个展区之间恰好存在一条简单路线。请统计不同的施工顺序。

(本故事由GPT-6重写)

## 形式化问题描述

有 $n$ 个互不相同的顶点，初始没有边。每一步在两个不同顶点之间加入一条无向边，同一对顶点至多加入一条边。最终任意两个不同顶点之间必须恰好有一条简单路径。

统计满足条件的加边序列数，答案对 $998244353$ 取模。最终边集不同，或边的添加顺序不同，均视为不同方案。$n=0$ 或 $n=1$ 时，唯一的空操作序列满足条件。

## 输入格式

一行一个非负整数 $n$ .

## 输出格式

输出一行一个整数，表示答案的非负最小剩余。

## 样例

### 样例 1

### 输入

```text
0
```

### 输出

```text
1
```

### 样例 2

### 输入

```text
3
```

### 输出

```text
6
```

### 样例 3

### 输入

```text
104
```

### 输出

```text
68933342
```

## 样例解释

空图只有空操作序列。三个顶点有三种树，每棵树的两条边可以按两种顺序加入，所以有六种方案。图中展示其中一棵树的两种顺序。

![Two edge orders for the same labelled tree](assets/orders.svg)

## 数据范围与保证

$0\le n\le10^6$ .下表中的 $100/3\%$ 表示总分的精确三分之一；前两组合计三分之二的数据满足 $n\le3000$ .

| 分值比例 | 额外条件 |
| --- | --- |
| 100/3% | $n\le104$ |
| 100/3% | $n\le3000$ |
| 100/3% | 无额外条件 |