← 返回题目列表

Codeforces · 1528/E

E. Mashtali 和 Hagh 树

中文机器翻译题面 查看原题

今天是 Mashtali 的生日!他收到了 Haj Davood 送给他的一棵哈格树作为他的生日礼物!

有向树称为 Hagh 树,当且仅当:

- 其中最长有向路径的长度恰好是$$$n$$$。
- 每个顶点最多有三个附加到其上的边,无论其方向如何。
- 如果顶点 $$$u$$$ 和 $$$v$$$ 中的一个有到另一个的有向路径,我们将它们称为好友。对于每对不是好友的顶点 $$$u$$$ 和 $$$v$$$,应该存在一个与 $$$u$$$ 和 $$$v$$$ 都是好友(共同好友)的顶点 $$$w$$$。

打开礼物后,Mashtali 发现顶点上的标签不见了。

他立即问自己:有多少种不同的未标记哈格树?也就是说,他可能会收到多少棵树作为他的生日礼物?

乍一看,这种树的数量似乎是无限的,因为顶点的数量没有限制;但后来他解决了这个问题并证明了未标记哈格树的数量是有限的!

对此事实感到惊讶,他与您分享了该任务,以便您也可以享受解决它的乐趣。由于答案可能相当大,他要求你找到不同的未标记哈格树模 $$$998244353$$$ 的数量。

这里,如果两棵树不是同构的,则认为它们是不同的:如果无法将一棵树的节点映射到第二棵树,以便将边映射到保持方向的边。

$$$n = 2$$$ 的一些示例:

有向树 $$$D$$$ 和 $$$E$$$ 是 Hagh。 $$$C$$$ 不是 Hagh,因为它有一个顶点,并附有 $$$4$$$ 边。 $$$A$$$ 和 $$$B$$$ 不是 Hagh,因为它们的最长有向路径不等于 $$$n$$$。同样在 $$$B$$$ 中,最左边和最右边的顶点不是朋友,也没有共同的朋友。

输入

输入的第一行包含一个整数 $$$n$$$ $$$(1 \le n \le 10^6)$$$。

输出

打印一个整数,即 Mashtali 任务模 $$$998244353$$$ 的答案。

示例

输入 #1

1

输出 #1

5

输入 #2

2

输出 #2

31

输入 #3

344031

输出 #3

272040628

注意

$$$n = 1$$$ 的所有五棵 Hagh 树: