今天是 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 树: