AT_abc387_g [ABC387G] Prime Circuit

頂点に $ 1 $ から $ N $ までの番号がついた $ N $ 頂点の単純無向連結グラフ $ G $ のうち次の条件を満たすものの個数を $ 998244353 $ で割った余りを求めてください。 - $ G $ に含まれる任意の回路の辺数が素数である。 ここで回路とは、同じ頂点を $ 2 $ 回以上通ってもよい閉路を意味する。(同じ辺を $ 2 $ 回以上通ってはならない)

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

問題文の条件を満たす単純無向連結グラフ $ G $ の個数を $ 998244353 $ で割った余りを出力せよ。

### Sample Explanation 1 条件を満たすグラフ $ G $ は以下の $ 4 $ 個です。 - $ (1, 2), (1, 3) $ を辺集合に持つグラフ - $ (1, 2), (2, 3) $ を辺集合に持つグラフ - $ (1, 3), (2, 3) $ を辺集合に持つグラフ - $ (1, 2), (1, 3), (2, 3) $ を辺集合に持つグラフ ### Constraints - $ N $ は $ 1 $ 以上 $ 2.5 \times 10^5 $ 以下の整数