AT_abc222_h [ABC222H] Beautiful Binary Tree

[problemUrl]: https://atcoder.jp/contests/abc222/tasks/abc222_h 正の整数 $ 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 $ で割ったあまりを答えてください。

N/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 10^7 $ - 入力はすべて整数である。 ### Sample Explanation 1 条件を満たす二分木は、根に $ 1 $ が書かれている $ 1 $ 頂点の木のみです。 ### Sample Explanation 2 条件を満たす二分木は次の $ 6 $ 通りです。 !\[image\](https://img.atcoder.jp/ghi/37c6125e227d459cd725b6ccec96e2c8.png)