Score : $600$ points

问题描述

对于一个正整数 $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$，求出模 $998244353$ 后，度为 $N$ 的美丽二叉树的数量。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

For a positive integer $N$, a rooted binary tree that satisfies the following conditions is said to be a beautiful binary tree of degree $N$.

• Each vertex has $0$ or $1$ written on it.
• Each vertex that is a leaf has $1$ written on it.
• It is possible to do the following operation at most $N-1$ times so that the root has $N$ written on it and the other vertices have $0$ written on them.
  • Choose vertices $u$ and $v$, where $v$ must be a child of $u$ or a child of "a child of $u$." Let $a_u \gets a_u + a_v, a_v \gets 0$, where $a_u$ and $a_v$ are the numbers written on $u$ and $v$, respectively.

Given $N$, find the number, modulo $998244353$, of beautiful binary trees of degree $N$.

Constraints

• $1 \leq N \leq 10^7$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$

Output

Print the answer.

Sample Input 1

1

Sample Output 1

1

The only binary tree that satisfies the condition is a tree with one vertex whose root has $1$ written on it.

Sample Input 2

2

Sample Output 2

6

The binary trees that satisfy the condition are the six trees shown below.

Sample Input 3

222

Sample Output 3

987355927

Sample Input 4

222222

Sample Output 4

675337738

update @ 2024/3/10 09:48:30