CF1528E.Mashtali and Hagh Trees

Today is Mashtali's birthday! He received a Hagh tree from Haj Davood as his birthday present!

A directed tree is called a Hagh tree iff:

• The length of the longest directed path in it is exactly $n$.
• Every vertex has at most three edges attached to it independent of their orientation.
• Let's call vertices $u$ and $v$ friends if one of them has a directed path to the other. For every pair of vertices $u$ and $v$ that are not friends, there should exist a vertex $w$ that is friends with both $u$ and $v$ (a mutual friend).

After opening his gift, Mashtali found out that the labels on the vertices were gone.

Immediately, he asked himself: how many different unlabeled Hagh trees are there? That is, how many possible trees could he have received as his birthday present?

At the first glance, the number of such trees seemed to be infinite since there was no limit on the number of vertices; but then he solved the problem and proved that there's a finite number of unlabeled Hagh trees!

Amazed by this fact, he shared the task with you so that you could enjoy solving it as well. Since the answer can be rather large he asked you to find the number of different unlabeled Hagh trees modulo $998244353$.

Here two trees are considered different, if they are not isomorphic: if there is no way to map nodes of one tree to the second tree, so that edges are mapped to edges preserving the orientation.

Some examples for $n = 2$:

Directed trees $D$ and $E$ are Hagh. $C$ is not Hagh because it has a vertex with $4$ edges attached to it. $A$ and $B$ are not Hagh because their longest directed paths are not equal to $n$. Also in $B$ the leftmost and rightmost vertices are not friends neither do they have a mutual friend.

今天是马什塔利的生日！他收到了哈吉·达伍德送给他的一棵“哈吉树”作为生日礼物！

一棵有向树被称为哈吉树，当且仅当满足以下条件：

• 其中最长有向路径的长度恰好为 $n$；
• 每个顶点所关联的边数（不考虑方向）至多为三条；
• 若顶点 $u$ 与 $v$ 中存在一条从其中一个指向另一个的有向路径，则称它们为朋友。对任意一对不是朋友的顶点 $u$ 和 $v$，必须存在一个顶点 $w$，使得 $w$ 同时是 $u$ 和 $v$ 的朋友（即 $w$ 是它们的共同朋友）。

打开礼物后，马什塔利发现顶点上的标签全都消失了。

他立刻自问：有多少棵互不同构的无标号哈吉树？也就是说，他可能收到的生日礼物共有多少种不同的树？

乍一看，这样的树的数量似乎是无限的，因为题目并未限制顶点总数；但随后他解出了该问题，并证明了无标号哈吉树的总数是有限的！

他对这一事实感到惊讶，于是将这个问题分享给你，让你也能享受解题的乐趣。由于答案可能非常大，他要求你输出不同无标号哈吉树的数目对 $998244353$ 取模的结果。

此处，若两棵树不同构（即不存在一种将第一棵树的节点一一映射到第二棵树节点的方式，使得所有有向边在映射下保持方向并一一对应），则认为它们是不同的树。

$n = 2$ 时的部分示例：

有向树 $D$ 和 $E$ 是哈吉树；$C$ 不是哈吉树，因为它含有一个关联了 $4$ 条边的顶点；$A$ 和 $B$ 也不是哈吉树，因为它们的最长有向路径长度不等于 $n$。此外，在 $B$ 中，最左侧顶点与最右侧顶点既不是朋友，也没有共同朋友。

The first line of input contains a single integer $n$ $(1 \le n \le 10^6)$.

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

Print a single integer, the answer to Mashtali's task modulo $998244353$.

输出一个整数，即马什塔利任务的答案对 $998244353$ 取模的结果。

All the five Hagh trees for $n = 1$:

当 $n = 1$ 时的全部五棵 Hagh 树：