题目描述

记 $S(n)$ 为满足以下条件的有向图集合：有 $n$ 个带编号顶点 $0,1,\ldots,n-1$，并且每个顶点恰好有一条出边。允许自环，因此 $|S(n)|=n^n$。

一次三旋操作选择三个互不相同的顶点，其当前编号依次为 $A,B,C$，然后同时把它们的编号改为 $B,C,A$。也就是说，三旋操作对顶点编号施加一个 $3$-循环。

如果一个图可以通过若干次（允许零次）三旋操作变成另一个图，则称这两个图三旋同构。

请从 $S(n)$ 中选出尽可能多的图，使任意两个被选中的图都不三旋同构。输出这个最大数量对 $998244353$ 取模后的结果。

输入格式

输入一个整数 $n$。

输出格式

输出一个整数，表示答案对 $998244353$ 取模后的值。

数据范围

$1\le n\le50$。

样例

输入

3

输出

11

输入

5

输出

67