CF1528E Mashtali and Hagh Trees

今天是 Mashtali 的生日！他收到了 Haj Davood 送给他的一个 Hagh 树作为生日礼物！ 一个有向树被称为 Hagh 树，当且仅当： - 其最长有向路径的长度恰好为 $n$。 - 每个顶点无论边的方向如何，最多只能连接三条边。 - 若顶点 $u$ 和 $v$ 之间存在一条有向路径，则称 $u$ 和 $v$ 是朋友。对于任意一对不是朋友的顶点 $u$ 和 $v$，都存在一个顶点 $w$，使得 $w$ 同时是 $u$ 和 $v$ 的朋友（即 $w$ 与 $u$、$v$ 都有有向路径相连）。 打开礼物后，Mashtali 发现顶点上的标签都消失了。 他立刻思考：有多少种不同的无标号 Hagh 树？也就是说，他可能收到多少种不同的树作为生日礼物？ 乍一看，这样的树似乎有无穷多种，因为顶点数没有限制；但他解决了这个问题，并证明无标号 Hagh 树的数量是有限的！ 他为此感到惊奇，并把这个任务分享给你，希望你也能享受解题的乐趣。由于答案可能非常大，他要求你将不同无标号 Hagh 树的数量对 $998244353$ 取模后输出。 如果两棵树不是同构的（不存在一种方式可以将一棵树的节点映射到另一棵树的节点，使得边的连接关系和方向都被保留），则认为它们是不同的。 对于 $n=2$ 的一些例子：  有向树 $D$ 和 $E$ 是 Hagh 树。$C$ 不是 Hagh 树，因为它有一个顶点连接了 $4$ 条边。$A$ 和 $B$ 不是 Hagh 树，因为它们的最长有向路径长度不等于 $n$。此外，在 $B$ 中，最左和最右的顶点既不是朋友，也没有共同的朋友。

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

输出一个整数，表示 Mashtali 的问题的答案，对 $998244353$ 取模。

对于 $n=1$ 的所有五种 Hagh 树：  由 ChatGPT 4.1 翻译