Migrated from Lutece 3171 要乐奈树

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag: 指数生成函数、符号化体系、牛顿迭代/半在线卷积

要乐奈和她的猫猫朋友们找了一棵 $n$ 个结点的、带标号的、有根的树睡觉。

什么？你问要乐奈怎么睡在上面的？拜托，猫猫是自由的。

如果一个顶点上有猫猫睡觉，我们称这个点为“猫点”。

为了防止这个树倒塌，对于任何一个结点，在它和它的子结点中，猫点的数量必须要小于一半。这样的树我们称之为猫树。

两颗猫树被认为是不同的，当且仅当下面的三个条件存在一个条件被满足：

• 存在一个顶点，在一棵树中是猫点，另一棵树中不是。
• 存在一个顶点，在两颗树中，它的子结点集合不同。
• 存在一个顶点，在两棵树中，它的子结点集合中的猫点的相对顺序不同。

当猫树有 $n$ 个结点时，你能算出来有多少个不同的猫树吗？（答案对 $998244353$ 取模）

Input

一行输入一个整数 $n$，表示猫树的结点数量。

Output

一行输出一个整数，表示 $n$ 个结点时不同猫树的数量。（对 $998244353$ 取模）

Samples

1

1

3

24

100

413875584

Constraints

$1\leq n \leq 10^5$

Note

考虑白色的顶点为猫点，则下面两颗猫树是相同的：

而下面四颗猫树两两不同：

Resources

2024 UESTC ICPC Training for Math