背景

曾经这道题目的名字叫逆归。但是一位马姓男子不同意，于是本题改名为城市规划。

提示

该题目为文本读写模式，文件名为city.in/out

题面

小 Y 是一位市长。他所下辖的区域可以分为 $n$ 块片区。

为了能够让城市之间可以互相通行，小 Y 决定建造一些双向路径。

考虑到每块片区的重要程度不同，小 Y 要求各块片区到片区 $1$ 的距离应当按照片区编号排序后成单调不下降序列。

并且，为尽量增加居民在单一路径上的活跃度，小 Y 要求各块片区到片区 $1$ 的最短路径只能有一条。

为了省钱，小 Y 要求方案中不能出现自环与重边。

请给出满足小 Y 要求的方案数，对 $998244353$ 取模。

形式化题面

一个图中有 $n$ 个点。起初它们之间没有连边。

你需要在这 $n$ 个点之间连接若干条双向边，求满足以下条件的方案数，其中定义 $d(i,j)$ 为点 $i$ 到点 $j$ 之间的最短距离。 1.$n$ 个点联通。 2.对于所有 $2\le i\le n$ ， $d(1,i-1)\le d(1,i)$ 。 3.长度为 $d(1,j)$ 的从点 $1$ 到点 $j$ 的路径恰好只有一条。

请输出方案数对 $998244353$ 取模的余数。

输入

一个整数 $n$ 。

输出

对应的方案数。

样例

2

1

3

3

4

15

42

905088720

数据范围

对于所有数据， $2\le n\le 100$ 。