美丽二叉树

题目描述

对于正整数 $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$ 取模。

输入格式

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

$N$

输出格式

输出答案。

样例

1

1

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

2

6

满足条件的二叉树为以下六棵。

222

987355927

222222

675337738

数据范围

• $1 \le N \le 10^7$
• 输入中的所有值均为整数。