AT_pakencamp_2025_day1_p Champion

$ N × N $ の 01行列 $ P $ が次の条件を満たすとき、 $ P $ は **League行列** であるとします。 - $ P_{i,i} = 0 $ ( $ 1 \leq i \leq N $ ) - $ P_{i,j} + P_{j,i} = 1 $ ( $ 1 \leq i < j \leq N $ ) また、ある League 行列 $ P $ から次のように $ N $ 頂点 $ N(N-1)/2 $ 辺の有向グラフ $ G $ を得ます。 - $ P_{i,j} = 1 $ の時、 $ G $ において頂点 $ j $ から頂点 $ i $ に有向辺を引く ここで、 $ G $ において入次数が最も多い頂点（複数あればその全て）を **Champion** とし、次のいずれかの条件を満たす頂点を **Champion?** とします。 - Champion である - ある Champion である頂点から辺をいくつか辿ることで到達できる 有り得る全ての $ N × N $ の League 行列から $ 1 $ つを無作為に選んだ時の、 Champion? である頂点の個数の期待値を $ \mathrm{mod} $ $ 998244353 $ で求めてください。

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

答えを一行に出力せよ。

### 部分点 次の追加制約を満たすテストケースに正解した場合、 $ 300 $ 点が与えられる。 - $ 1 \leq N \leq 2000 $ ### Sample Explanation 1 例えば、行列が次のようになっている場合を考えます。 ``` 0 1 0 1 1 0 0 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 1 0 ``` この時、これに対応する有向グラフ上での Champion 及び Champion? である頂点は次のようになります。 - まず、入次数が最も多い頂点は頂点 $ 1 $ と $ 2 $ の $ 2 $ つであり、この $ 2 $ 頂点は Champion であり、同時に Champion? でもある。 - 頂点 $ 3 $ は、 Champion である頂点 $ 1 $ から $ 1 $ → $ 3 $ と辺を辿って移動できるので、 Champion? である。 - 頂点 $ 5 $ は、 Champion である頂点 $ 1 $ から $ 1 $ → $ 3 $ → $ 5 $ と辺を辿って移動できるので、 Champion? である。 - 頂点 $ 4 $ は、どの Champion である頂点からも辺を辿って移動できないので Champion? ではない。 よって、この場合の Champion? である頂点の個数は $ 4 $ つです。 $ 5 × 5 $ の League 行列は $ 2^{10} = 1024 $ 個存在しますが、それらから無作為に $ 1 $ つ選んだ時の Champion? である頂点の個数の期待値は $ \frac{455}{128} $ なので、 $ \mathrm{mod} $ $ 998244353 $ 上でこれを表す $ 444530692 $ を出力してください。 ### Sample Explanation 2 有向グラフとして考えられるのは $ 2^1 = 2 $ 通りで、そのどちらの場合も Champion? である頂点の個数は $ 1 $ です。 ### Sample Explanation 4 このケースは $ N $ が $ 2000 $ よりも大きいため、部分点には影響しません。 ### Constraints - $ 1 \leq N \leq 2×10^5 $ - 入力は全て整数