题目背景

终于打过春二心门的 ac 来到了春三，并决定预测一下残暴圣所（Ferocious Sanctuary）的难度。

题目描述

为了通关残暴圣所，ac 需要在接下来的 $2n$ 个时刻进行 $n$ 次操作。第 $i$ 次操作需要在时刻 $l_i$ 按下某个按键，此后一直按住这个按键，直到时刻 $r_i$ 松开它（$l_i<r_i$）。在每个时刻，ac 要么按下一个按键，要么松开一个按键，但是可以同时按住多个按键。

第 $i$ 次操作形成了一个操作区间 $[l_i,r_i]$，满足 $l_i$ 严格递增。并且，由于残暴圣所的关卡设计，任意两个操作形成的操作区间之间，要么不交，要么包含。

ac 设计了 $2n$ 个难度系数 $a_1,a_2,\dots,a_{2n}$。第 $i$ 次操作的难度可以用 $a_{l_i}\times a_{r_i}$ 来评估，而通关残暴圣所的难度即为所有操作的难度之和。

然而，由于 ac 卡在了残暴圣所的第一面，所以他并不知道每个操作的操作区间。在给定 $n$ 和 $\{a\}$ 的前提下，请你计算对于所有可能的情况，通关残暴圣所的难度之和，对 $998244353$ 取模。

形式化题意：

给定一个长为 $2n$ 的数列 $a_1,a_2,\dots,a_{2n}$。

定义“区间组”由 $n$ 个区间组成，第 $i$ 个区间为 $[l_i,r_i]\ (1\le l_i<r_i\le2n)$，求所有满足下列条件的区间组的 $\sum_{i=1}^na_{l_i}\times a_{r_i}$ 之和对 $998244353$ 取模：

1. $l_1,r_1,l_2,r_2,\dots,l_n,r_n$ 是 $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$ 或 $[l_i,r_i]\sube[l_j,r_j]$ 或 $[l_j,r_j]\sube[l_i,r_i]$。

输入格式

第一行一个整数 $n$，表示区间数。

第二行 $2n$ 个整数 $a_i$，含义如上所述。

输出格式

一行一个整数，表示答案对 $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

提示

样例说明

对于样例 1，可能的两个操作区间只有两种情况：

1. $[1,2],[3,4]$，通关难度为 $a_1a_2+a_3a_4=1612986$。
2. $[1,4],[2,3]$，通关难度为 $a_1a_4+a_2a_3=1078706$。

难度之和为 $1612986+1078706=2691692$，对 $998244353$ 取模后仍为 $2691692$。

以下几种情况是不合法的：

1. $[3,4],[1,2]$，因为要求 $l_i$ 严格递增，而 $l_1\ge l_2$。
2. $[1,1],[2,4]$，因为要求 $l_i<r_i$，而 $l_1\ge r_1$。
3. $[1,3],[2,3]$，因为要求在每个时刻，要么按下一个按键，要么松开一个按键，而第三个时刻松开了两个按键，第四个时刻没有按下或松开任何一个按键。
4. $[1,3],[2,4]$，因为要求任意两个操作区间不交或包含，而这两个区间之间有交，并且没有包含关系。

数据范围

对于 $10\%$ 的数据，$n\le15$。

对于 $30\%$ 的数据，$n\le200$。

对于 $50\%$ 的数据，$n\le3000$。

对于另 $5\%$ 的数据，$a_i=1$。

对于 $100\%$ 的数据，$1\le n\le5\times10^5$，$0\le a_i<998244353$。