配点 : $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$ 頂点の木のみです。

2

6

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

222

987355927

222222

675337738