画画
题目描述
yww 要开始画画了!
地上有一张纸,纸上有 $n$ 个点。
yww 要在结点之间连边。yww 的连边是非常有规律的。每次他会拿好笔,选定一个点,从这个点 $x$ 向其他点 $y$ 连边,再从 $y$ 向其他点 $z$ 连边,依次类推,直到连回点 $x$ 。yww 会进行若干次这样的连边。并且,自始至终,yww 都不会在两个结点之间连超过一条边。
yww 想知道,他一共能画出多少种本质不同的图。两个图本质相同,当且仅当存在一个点到点的置换,使得对于原图和在置换作用下的新图,任意两点之间要么都没有连边,要么都有连边。你只需要将答案对 $998244353$ 取模。
一句话题意,n 个点的无标号的每个连通块有欧拉回路的图的个数。
输入输出格式
输入格式
第一行一个数 $n$ 。
输出格式
输出一个数。
输入输出样例
输入样例 #1
4
输出样例 #1
3
输入样例 #2
5
输出样例 #2
7
说明
对于 $10 \%$ 的数据,$n \le 5$ 。
对于 $40 \%$ 的数据,$n \le 10$ 。
对于 $100 \%$ 的数据,$1 \le n \le 50$ 。