题目描述

zzyuanlai 要开始画画了！

地上有一张纸，纸上有 $n$ 个点。

zzyuanlai 要在结点之间连边。zzyuanlai 的连边是非常有规律的。每次他会拿好笔，选定一个点，从这个点 $x$ 向其他点 $y$ 连边，再从 $y$ 向其他点 $z$ 连边，依次类推，直到连回点 $x$ 。zzyuanlai 会进行若干次这样的连边。并且，自始至终，zzyuanlai 都不会在两个结点之间连超过一条边。

zzyuanlai 想知道，他一共能画出多少种本质不同的图。两个图本质相同，当且仅当存在一个点到点的置换，使得对于原图和在置换作用下的新图，任意两点之间要么都没有连边，要么都有连边。你只需要将答案对 $998244353$ 取模。

一句话题意，$n$ 个点的无标号的每个连通块有欧拉回路的图的个数。

输入格式

第一行一个数 $n$ 。

输出格式

输出一个数。

输入输出样例 #1

输入 #1

4

输出 #1

3

输入输出样例 #2

输入 #2

5

输出 #2

7

说明/提示

对于 $10 \%$ 的数据，$n \le 5$ 。

对于 $40 \%$ 的数据，$n \le 10$ 。

对于 $100 \%$ 的数据，$1 \le n \le 50$ 。