問題文

正の整数 $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$ 通りです。

入力例 3

222

出力例 3

987355927

入力例 4

222222

出力例 4

675337738