スコアが最大になるような \(A,B\) の分割に対し、\(A_i\) と \(B_i\) はペアになっていると呼びます。

[1] スコアが最大となる構造の分析

\(A<B<C<D\) を満たす任意の正整数 \(A,B,C,D\) について、以下が成立します。

• \(AD+BC < AC+BD < AB+CD\)

よってスコアが最大になる構造では、 \(2N\) と \(2N-1\) ,\(2N-2\)と \(2N-3\),\(\ldots\),\(2\) と \(1\) がペアになってることがわかります。（そうでない場合、適切に入れ替えることでスコアを大きくできます）

[2] 括弧列との対応付け

各ペアについて、\(P\) の中で左に存在する要素を単に左の要素と呼びます。

各ペアについてどちらを左の要素にするか（向き）で、\(2^N\) 通りの場合があります。さらに、左の要素の \(P\) での順番は \(N!\) 通り考えられます。

このとき、左から \(P\) を見ていくときに常に左の要素は右の要素の個数以上でないといけません。この個数は括弧列の個数と対応しています。

結局、順番の割り当てが \(N!\) 、向きが \(2^N\) 、括弧列の個数はカタラン数で \(\frac{1}{N+1}\binom{2N}{ N}\) なので、答えは \(2^N \frac{(2N)!}{(N+1)!}\) となります。

[3] 実装例

Python:

mod = 998244353
n = int(input())
res = pow(2, n, mod)
for i in range(n + 2, 2 * n + 1):
    res *= i
    res %= mod
print(res)