AT_abc222_h [ABC222H] Beautiful Binary Tree

题目描述

对于正整数 $N$，满足以下条件的有根二叉树被定义为 $N$ 次美丽二叉树。

• 每个顶点上写有 $0$ 或 $1$。
• 如果顶点是叶子节点，则该节点上一定写有 $1$。
• 通过至多 $N-1$ 次如下操作，可以使根节点上的数变为 $N$，其余所有顶点上的数变为 $0$。
  • 选择顶点 $u, v$，其中 $v$ 必须是 $u$ 的子节点或 $u$ 的孙节点。设 $a_u, a_v$ 分别为 $u, v$ 上的数，执行 $a_u \gets a_u + a_v, a_v \gets 0$。

给定 $N$，请输出 $N$ 次美丽二叉树的个数，答案对 $998244353$ 取模。

输入格式

输入为一行，包含一个整数 $N$。

输出格式

输出一个整数，表示答案。

输入输出样例 #1

输入 #1

1

输出 #1

1

输入输出样例 #2

输入 #2

2

输出 #2

6

输入输出样例 #3

输入 #3

222

输出 #3

987355927

输入输出样例 #4

输入 #4

222222

输出 #4

675337738

说明/提示

限制

• $1 \leq N \leq 10^7$
• 输入均为整数。

样例解释 1

满足条件的二叉树只有一种，即根节点上写有 $1$ 的单节点树。

样例解释 2

满足条件的二叉树共有 $6$ 种。

由 ChatGPT 4.1 翻译