题目背景

（七）再见，地底世界的朋友们

在地灵殿住了许多天了呢。

这些日子里，觉分享了很多旧地狱的故事。

此次地底旅行，可以说是非常充实了。

虽然仍旧有些不舍，不过人类总是要见太阳的，再说这样麻烦觉姐姐招待我们也有些过意不去呢。

那么，和觉，恋，阿燐，阿空，以及其他宠物们说再见吧。

......

旧地狱的街市，依旧飘着雪。

已经能看到溶洞了。

环境又变得幽闭起来。

诶，前面不是山女吗？

“啊，你们要回地面了吗，玩的怎样？”

“很开心呢，对了，剩下的问题已经解决了”

我们向山女解释了从荷取那里听到的方法。

“谢谢!”

“不客气，那么再见了~”

世界一片白茫茫的...

阳光是那么的刺眼，以至于几分钟后我们才能睁开眼睛看清楚地面的景色。

沿着魔法森林中的小路向神社走去，这次的旅行也在我们的脚步声中走向了尾声。

前方的地面上忽然出现了一页破损的笔记。

捡起来一看，发现是从文文的笔记本上脱落下来的。

射命丸文，作为（不靠谱的）新闻记者，观察到最近地灵殿里的宠物们偶尔会互相打架，于是将每场决斗的胜负关系写在了她的笔记本上。刚刚捡起来的这页笔记，上面就记录着几场“单循环赛”。

每场循环赛被抽象成一张竞赛图，其中顶点代表参加循环赛的宠物，从顶点 $u$ 指向顶点 $v$ 的边代表在一场比赛中宠物 $u$ 战胜了宠物 $v$。

观察到这页笔记上所有的竞赛图中都至少存在一条经过所有顶点的回路，我们猜想文文只会记录这样的循环赛。

可能是因为文文不清楚宠物们谁能打过谁，于是在那页笔记的最下面留下了一个这样的问题...

(见题目描述)

这最后一个问题，就留给你来解决啦。

博丽大结界，已经在我们身后了。

希望这次地底旅行，能给你留下美好的记忆~

(全文完)

题目描述

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

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

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

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

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

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

输入格式

一行一个正整数 $n$。

输出格式

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

4

1
-1
1
1

提示

样例解释：

$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