H - Beautiful Binary Tree Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

正の整数 N に対して、次の条件を満たす根付き二分木を N 次の美しい二分木 と定めます。

  • 頂点には 0 か 1 が書かれている。
  • 頂点が葉ならば、必ず 1 が書かれている。
  • 次の操作を高々 N-1 回行うことで、根に書かれている数を N に、それ以外の頂点に書かれている数を 0 にすることができる。
    • 頂点 u, v を選ぶ。ここで v は u の子、あるいは u の子の子である必要がある。 u,v に書かれている数を a_u, a_v としたとき、 a_u \gets a_u + a_v, a_v \gets 0 とする。

N が与えられるので、N 次の美しい二分木の個数を 998244353 で割ったあまりを答えてください。

制約

  • 1 \leq N \leq 10^7
  • 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N

出力

答えを出力せよ。

入力例 1

1

出力例 1

1

条件を満たす二分木は、根に 1 が書かれている 1 頂点の木のみです。

入力例 2

2

出力例 2

6

条件を満たす二分木は次の 6 通りです。

image

入力例 3

222

出力例 3

987355927

入力例 4

222222

出力例 4

675337738

Score : 600 points

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.

image

Sample Input 3

222

Sample Output 3

987355927

Sample Input 4

222222

Sample Output 4

675337738