H - 美丽的二叉树

分数：$600$ 分

问题描述

对于一个正整数 $N$，如果满足以下条件的根二叉树被称为“度数为 $N$ 的美丽二叉树”。

• 每个顶点上写有 $0$ 或 $1$。
• 每个叶子结点上写有 $1$。
• 可以进行以下操作最多 $N-1$ 次，使得根结点上写有 $N$，其他结点上写有 $0$：
  • 选择结点 $u$ 和结点 $v$，其中 $v$ 必须是 $u$ 的孩子结点或 $u$ 的孩子结点的孩子结点。设 $a_u \gets a_u + a_v, a_v \gets 0$，其中 $a_u$ 和 $a_v$ 分别是结点 $u$ 和 $v$ 的值。

给定 $N$，求满足度数为 $N$ 的美丽二叉树的数量（对 $998244353$ 取模）。

约束条件

• $1 \leq N \leq 10^7$
• 输入中的所有值都是整数。

输入

从标准输入中以以下格式给出：

$N$

输出

输出答案。

1

1

满足条件的二叉树只有一个顶点，根结点上写有 $1$。

2

6

满足条件的二叉树示例如下所示。

222

987355927

222222

675337738