問題文

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 で求めてください。

制約

• 1 \leq N \leq 2×10^5
• 入力は全て整数

部分点

次の追加制約を満たすテストケースに正解した場合、 300 点が与えられる。

• 1 \leq N \leq 2000

入力例 1

5

出力例 1

444530692

例えば、行列が次のようになっている場合を考えます。

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 を出力してください。

入力例 2

2

出力例 2

1

有向グラフとして考えられるのは 2^1 = 2 通りで、そのどちらの場合も Champion? である頂点の個数は 1 です。

入力例 3

100

出力例 3

550420818

入力例 4

2026

出力例 4

926770690

このケースは N が 2000 よりも大きいため、部分点には影響しません。