Migrated from Lutece 2663 奥日与灵树之末

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

『终局即将来临』

『一切的道路都通向灵树』

……

---

在黑暗的侵蚀下，昔日散发光芒的灵树，如今已经变得千疮百孔

灵树内部的空间被黑暗所扭曲，混沌一片。具体来说，灵树内部被划分为 $n$ 块本质相同的空间。这些空间之间存在着一些连接两个空间的单向传送门。经过观察，奥日发现灵树内部不会有两个传送门起点终点完全相同，也不会有起点和终点落在同一处空间的传送门。

在进入灵树之前，奥日想知道，灵树内部的空间有多少种本质不同的连接情况。

两种连接情况如果本质相同，是指存在一种方案，分别将两种连接情况中的空间用 $1\ldots n$ 进行编号，使得两种连接情况中任意的单向传送门都在另一种连接情况中出现。

你可以帮助奥日解决这个难题吗？

Input

输入一行 $n$ 表示灵树内部的空间数。

Output

输出一行，表示灵树内部总共可能的连接情况种类数。 由于答案很大，你只需要告诉奥日答案对 $998244353$ 取模后的结果。

Samples

2

3

11

578828030

45

212539913

14

352044742

Constraints

$1\le n\le 60$

Note

简要题意：无标号简单有向图计数。

Resources

2021 UESTC ICPC Training for Math and Geometry