AT_tupc2024_k Shuffle and Max Bracket Score

あおばさんは次の問題を思いつきました。 > **Max Bracket Score** > 長さ $ 2N $ の整数列 $ A=(A_1,A_2,\ldots,A_{2N}) $ が与えられます。長さ $ 2N $ の正しい括弧列 $ s $ に対して、 $ s $ のスコアを次のように定めます。 > > - $ s_i $ が `(` であるようなすべての $ i $ に対する $ A_i $ の総和 > > 長さ $ 2N $ の正しい括弧列のスコアとしてあり得る最大の値を求めてください。 この問題はひろせさんにとって簡単だったので、以下のように改題しました。 > **Shuffle and Max Bracket Score** > 長さ $ 2N $ の整数列 $ A=(A_1,A_2,\ldots,A_{2N}) $ が与えられます。 $ A $ を一様ランダムにシャッフルした後の Max Bracket Score の答えの期待値を $ \mathrm{mod}\ 998244353 $ で求めてください。 Shuffle and Max Bracket Score を解いてください。 正しい括弧列とは 以下のいずれかの条件を満たす文字列を正しい括弧列と定義します。 - 空文字列 - ある正しい括弧列 $ S $ が存在して、`(`, $ S $ , `)` をこの順に連結した文字列 - ある空でない正しい括弧列 $ S, T $ が存在して、 $ S,T $ をこの順に連結した文字列 期待値 $ \text{mod} \ 998244353 $ とは 求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 $ \frac{P}{Q} $ で表したとき、 $ Q \not \equiv 0 \pmod{998244353} $ となることも証明できます。 よって、 $ R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 $ を満たす整数 $ R $ が一意に定まります。 この $ R $ を答えてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_{2N} $

求める期待値を $ \mathrm{mod}\ 998244353 $ で出力せよ。

### 部分点 - 追加の制約 $ N\leq 100 $ を満たすデータセットに正解した場合は $ 10 $ 点が与えられる。 ### Sample Explanation 1 $ A=(1,2) $ のとき Max Bracket Score の答えは $ 1 $ です。 - $ s $ が `()` のときのスコアは $ 1 $ です。 $ A=(2,1) $ のとき Max Bracket Score の答えは $ 2 $ です。 - $ s $ が `()` のときのスコアは $ 2 $ です。 求める期待値は $ \dfrac{1}{2}(1+2)=\dfrac{3}{2} $ です。 ### Sample Explanation 2 例えば $ A=(1,2,3,4) $ のとき Max Bracket Score の答えは $ 4 $ です。 - $ s $ が `()()` のときのスコアは $ 1+3=4 $ です。 - $ s $ が `(())` のときのスコアは $ 1+2=3 $ です。 また、 $ A=(4,3,2,1) $ のとき Max Bracket Score の答えは $ 7 $ です。 - $ s $ が `()()` のときのスコアは $ 4+2=6 $ です。 - $ s $ が `(())` のときのスコアは $ 4+3=7 $ です。 求める期待値は $ \dfrac{35}{6} $ です。 ### Constraints - $ 1\leq N \leq 10^5 $ - $ 1\leq A_i\leq 10^9 $ - 入力は全て整数