問題文

正整数 N が与えられます。

総和が N であるような正整数列 s について、スコア を s の総積と定義します。

スコアのとりうる最大値を m とします。スコアが m になるような s の個数を 998244353 で割ったあまりを求めてください。

制約

• 1 \leq N\leq 10^9
• N は整数

部分点

• N \leq 30 を満たすデータセットに正解した場合は、10 点与えられる。
• 追加制約のないデータセットに正解した場合は、上記とは別に 90 点与えられる。

入力例 1

4

出力例 1

2

s としてありうるものは 8 個存在し、それぞれスコアは以下のようになります。

• s=(1,1,1,1)：スコアは 1
• s=(1,1,2)：スコアは 2
• s=(1,2,1)：スコアは 2
• s=(2,1,1)：スコアは 2
• s=(1,3)：スコアは 3
• s=(2,2)：スコアは 4
• s=(3,1)：スコアは 3
• s=(4)：スコアは 4

スコアのとりうる最大値は 4 で、スコアが 4 となる s は 2 個存在します。よって、答えは 2 です。

入力例 2

2

出力例 2

1

入力例 3

1000000000

出力例 3

428670605

s の個数を 998244353 で割ったあまりを求めることを忘れないでください。