Background

After finally clearing the Spring 2 Heart Gate, ac arrived at Spring 3 and decided to predict the difficulty of Ferocious Sanctuary.

Problem Description

To clear Ferocious Sanctuary, ac needs to perform $n$ operations during the next $2n$ moments. The $i$-th operation requires pressing a key at time $l_i$, then holding this key until releasing it at time $r_i$ ($l_i<r_i$). At each moment, ac either presses a key or releases a key, but can hold multiple keys at the same time.

The $i$-th operation forms an operation interval $[l_i,r_i]$, and $l_i$ is strictly increasing. Also, due to the level design of Ferocious Sanctuary, for any two operations, their operation intervals either do not intersect, or one contains the other.

ac designed $2n$ difficulty coefficients $a_1,a_2,\dots,a_{2n}$. The difficulty of the $i$-th operation can be evaluated as $a_{l_i}\times a_{r_i}$, and the difficulty of clearing Ferocious Sanctuary is the sum of the difficulties of all operations.

However, since ac is stuck on the first screen of Ferocious Sanctuary, he does not know the operation intervals of each operation. Given $n$ and $\{a\}$, please compute, over all possible cases, the sum of the clearing difficulty, modulo $998244353$.

Formal statement:

Given a sequence $a_1,a_2,\dots,a_{2n}$ of length $2n$.

Define an "interval group" as a set of $n$ intervals, where the $i$-th interval is $[l_i,r_i]\ (1\le l_i<r_i\le2n)$. For all interval groups satisfying the conditions below, compute the sum of $\sum_{i=1}^na_{l_i}\times a_{r_i}$, modulo $998244353$:

1. $l_1,r_1,l_2,r_2,\dots,l_n,r_n$ is a permutation of $1,2,\dots,2n$.
2. $\forall 1\le i<n$，$l_i<l_{i+1}$。
3. $\forall i,j$，$[l_i,r_i]\cap[l_j,r_j]=\varnothing$ or $[l_i,r_i]\sube[l_j,r_j]$ or $[l_j,r_j]\sube[l_i,r_i]$。

Input Format

The first line contains an integer $n$, representing the number of intervals.

The second line contains $2n$ integers $a_i$, with the meaning described above.

Output Format

Output one integer in one line, representing the answer modulo $998244353$.

2
114 514 1919 810

2691692

3
1 1 4 5 1 4

98

8
275272885 418731188 289662326 114331587 192436268 885936831 877490593 508774565 633402863 149033362 995239139 494498006 168828873 138947653 983144753 844326228

349824160

Hint

Sample Explanation

For sample 1, there are only two possible interval groups:

1. $[1,2],[3,4]$, the clearing difficulty is $a_1a_2+a_3a_4=1612986$。
2. $[1,4],[2,3]$, the clearing difficulty is $a_1a_4+a_2a_3=1078706$。

The sum of difficulties is $1612986+1078706=2691692$, and modulo $998244353$ it is still $2691692$.

The following cases are invalid:

1. $[3,4],[1,2]$, because $l_i$ is required to be strictly increasing, but $l_1\ge l_2$。
2. $[1,1],[2,4]$, because $l_i<r_i$ is required, but $l_1\ge r_1$。
3. $[1,3],[2,3]$, because at each moment, one must either press a key or release a key, but at the third moment two keys are released, and at the fourth moment no key is pressed or released.
4. $[1,3],[2,4]$, because any two operation intervals must be disjoint or one contains the other, but these two intervals intersect and neither contains the other.

Constraints

For $10\%$ of the testdata, $n\le15$。

For $30\%$ of the testdata, $n\le200$。

For $50\%$ of the testdata, $n\le3000$。

For another $5\%$ of the testdata, $a_i=1$。

For $100\%$ of the testdata, $1\le n\le5\times10^5$，$0\le a_i<998244353$。

Translated by ChatGPT 5