102227: [AtCoder]ABC222 H - Beautiful Binary Tree

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

问题描述

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

• 每个顶点上都写有$0$或$1$。
• 每个叶顶点上都写有$1$。
• 通过以下操作最多进行$N-1$次，使得根顶点上写有$N$，其他顶点上写有$0$。
• 选择顶点$u$和$v$，其中$v$必须是$u$的子顶点或“$u$的子顶点的子顶点”。将$u$和$v$上的数字分别更新为$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

1

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

样例输入2

2

样例输出2

6

满足条件的二叉树是下图所示的六棵树。

样例输入3

222

样例输出3

987355927

样例输入4

222222

样例输出4

675337738