AT_pakencamp_2025_day3_i Penguin Flicker

横に長いスケートリンクがあります。スケートリンクは $ L+2 $ 個の区画に分かれていて、左から区画 $ 0,1,2,\dots,L,L+1 $ と番号が付けられています。区画 $ 0 $ と区画 $ L+1 $ には海に落ちる穴が空いていて、それ以外の区画には穴はありません。 スケートリンクの穴のない区画のうち、 $ N $ 個の区画にはペンギンがいます。 $ i $ 番目のペンギンは区画 $ P_i $ にいて、ペンギンのいる区画はすべて相異なります。 パフィンのパ太郎は、これから、全てのペンギンが海に落ちるまでペンギンを動かします。具体的には、以下の操作をすべてのペンギンが海に落ちるまで行います。 - 海に落ちていないペンギンを一様ランダムに $ 1 $ 匹選ぶ。 - 左か右のどちらかを一様ランダムに選び、その選んだ方向に動かす。ペンギンは、以下の条件のどちらかを満たすまで、指定された方に動き続ける。 - 別のペンギンがいる区画の直前の区画に到達する。 - 穴のある区画に到達し、海に落ちる。 ただし、海に落ちたペンギンはどの区画にもいないとみなします。また、すべての選択は独立に行われます。 ペンギンが $ 1 $ 回の操作で区画 $ i $ から区画 $ j $ まで移動したとき、その操作でのペンギンの移動距離を $ |i-j| $ とします。すべてのペンギンが海に落ちるまでの、ペンギンの移動距離の総和の期待値を $ \bmod 998244353 $ で求めてください。 以上の問題を $ T $ 個のテストケースについて解いてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ L $ $ P_1 $ $ P_2 $ $ \dots $ $ P_N $

$ T $ 行出力せよ。 $ i $ 行目には、 $ i $ 番目のテストケースに対する答えを出力せよ。具体的には、求める期待値は必ず有理数となることが証明でき、またこの問題の制約下では、その値を互いに素な正整数 $ p,q $ を用いて $ \frac{p}{q} $ と表したとき、 $ r\times q\equiv p \pmod{998244353} $ かつ $ 0\leq r\lt 998244353 $ なる整数 $ r $ がただ $ 1 $ つ存在することが示せるから、この $ r $ を出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースでは、パ太郎が $ 1 $ 番目のペンギンを左に動かすと移動距離は $ 2 $ 、右に動かすと移動距離は $ 7 $ で、どちらにせよペンギンは海に落ちます。よって、移動距離の期待値は $ \frac{9}{2} $ です。 $ 499122181 \times 2\equiv9\pmod{998244353} $ ですから、答えは $ 499122181 $ です。 $ 2 $ 番目のテストケースでは、例えばパ太郎がはじめに $ 4 $ 番目のペンギンを左に動かすと、 $ 4 $ 番目のペンギンは区画 $ 334 $ に移動し、このときの移動距離は $ 554 $ です。もちろん、それ以外にもペンギンを動かす方法は複数存在し、パ太郎はそのうち一様ランダムに $ 1 $ つ選びます。 ### Constraints - $ 1\leq T\leq 100 $ - $ 1\leq N\leq 5000 $ - $ N\leq L\leq 10^9 $ - $ 1\leq P_1\lt P_2\lt \dots \lt P_N\leq L $ - 入力はすべて整数