AT_fps_24_o 根付き木

頂点に $ 1 $ から $ N $ の番号がついていて、頂点 $ 1 $ を根とする $ N $ 頂点の根付き木のうち次の条件を満たすものの個数を $ 998244353 $ で割った余りを求めてください。 - $ 1 \leq i \leq N $ を満たす全ての整数 $ i $ について、 $ i $ の子の個数は $ 0 $ または素数である。

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

答えを出力せよ。

### Sample Explanation 1 例えば頂点 $ 2 $ と頂点 $ 3 $ の親がともに頂点 $ 1 $ である根付き木は条件を満たします。なぜならば、頂点 $ 1 $ の子の個数は $ 2 $ 個(素数) で、頂点 $ 2 $ と頂点 $ 3 $ の子の個数は $ 0 $ 個だからです。 条件を満たす木は上に説明した木の $ 1 $ 個のみです。 ### Constraints - $ 3 \leq N \leq 2.5 \times 10^5 $ - $ N $ は整数