Description

如果一个竞赛图含有哈密顿回路，则称这张竞赛图为值得记录的。

从所有含有 $n$ 个顶点（顶点互不相同）的，值得记录的竞赛图中等概率随机选取一个。

求选取的竞赛图中哈密顿回路数量的期望值。

由于答案可能过大/丢失精度，只需要输出答案除以 $998244353$ 的余数。

即：设答案为 $\frac{q}{p}$，则你需要输出一个整数 $x$，满足 $px\equiv q \mod 998244353$ 且 $0\leqslant x<998244353$，可以证明恰好存在一个这样的 $x$。

若不存在这样的竞赛图，输出 -1。

Input Format

一行一个正整数 $n$。

Output Format

$n$ 行，第 $i$ 行一个数字，代表输入为 $i$ 时的答案

4

1
-1
1
1

Hint

样例解释：

$n=1$ 时只有一种满足条件的竞赛图，就是一个点。

$n=2$ 时竞赛图中只有一条边，不能形成哈密顿回路。

$n=3$ 时有两种满足条件的竞赛图，分别为 $1\to2\to3\to1$ 和 $1\to3\to2\to1$，都只有 $1$ 条哈密顿回路，随机取出后期望值为 $1$。

$n=4$ 时有很多种满足条件的的竞赛图，这里写不下了，但是所有满足条件的竞赛图都是同构的，所以随机取出后期望值为 $1$。

数据范围：

测试点 1~3 中 $n\leqslant7$。

测试点 4~6 中 $n\leqslant10$。

测试点 7~10 中 $n\leqslant1000$。

测试点 11~16 中 $n\leqslant10000$。

测试点 17~25 中 $n\leqslant100000$。

数据有梯度，每个测试点 $4$ 分。

为防止卡常，最后两个点开 2s 时限。

名词解释：

竞赛图：指任意两个顶点间恰有一条有向边的有向图。

哈密顿回路：指除起点和终点外经过所有顶点恰好一次且起点和终点相同的路径。

by oscar