For a division into \(A\) and \(B\) that maximizes the score, let us say \(A_i\) and \(B_i\) to be paired.

[1] When is the score maximized?

For any positive integers \(A\), \(B\), \(C\), and \(D\) such that \(A<B<C<D\), the following holds:

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

Therefore, in a division that maximizes the score, we have the following pairs: \(2N\) and \(2N-1\), \(2N-2\) and \(2N-3\), \(\ldots\), \(2\) and \(1\). (Otherwise, the score could be increased by rearranging the pairs accordingly.)

[2] Correspondence to parenthesis sequences

For each pair \((a, b)\), let us call \(a\) the left element when \(a\) is to the left of \(b\) in \(P\).

There are \(2^N\) ways to “direct” the pairs in \(P\), that is, to decide which of each pair is the left element. Additionally, there are \(N!\) possible relative orders of the left elements in \(P\).

Here, if the elements in \(P\) are scanned from left to right, there must always be more left elements than right elements. The number of such arrangements corresponds to that of parenthesis sequences.

Eventually, there are \(N!\) ways to order the pairs, \(2^N\) ways to direct them, and \(\frac{1}{N+1}\binom{2N}{ N}\) parenthesis sequences (the Catalan number), for a total of \(2^N \frac{(2N)!}{(N+1)!}\) sequences that can be made.

[3] Sample Implementation

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)