반전수

$a\_1$개의 $1$, $a\_2$개의 2, $\dots$, $a\_n$개의 $n$으로 이루어진 수열들을 생각하자. 해당 수들로 이루어진 수열 중에 한 개를 균일한 확률로 무작위로 고를 때 반전수의 제곱의 기댓값을 $998\\, 244\\, 353$으로 나눈 나머지를 구하여라.

수열 $p\_1$, $p\_2$, $\dots$, $p\_n$의 반전수는 $i\<j$, $p\_i>p\_j$를 만족하는 순서쌍 $(i,j)$의 개수로 정의한다.

첫 번째 줄에 수열에 있는 수의 최댓값 $n$이 주어진다. ($2\leq n\leq 200\\, 000$)

두 번째 줄에 각 수의 개수 $a\_i$가 공백을 사이에 두고 주어진다. ($1\leq a\_i$; $n\leq\sum\_{i=1}^{n}a\_i\leq 998\\, 244\\, 352$).

문제에서 요구하는 정답을 $998\\, 244\\, 353$으로 나눈 나머지를 출력하여라.

반전수의 제곱의 기댓값이 유리수임을 증명할 수 있다. 이 수를 $\frac{p}{q}$ ($p$, $q$는 서로소)로 표시했을 때, $q$는 $998\\, 244\\, 353$의 배수가 될 수 없음을 증명할 수 있다. $aq\equiv p\ (\mathrm{mod}\ 998\\, 244\\, 353)$을 만족하는 음이 아닌 정수 $a$ 중 가장 작은 수를 $\frac{p}{q}$를 $998\\, 244\\, 353$으로 나눈 나머지로 정의한다.

$1$이 $1$개, $2$가 $1$개로 이루어진 수열은 $12$, $21$ 두 가지가 있고 각 수열의 반전수는 $0$, $1$이다. 즉, 반전수의 제곱의 기댓값은 $\frac{1}{2}$가 되고 $499\\, 122\\, 177\times 2\equiv 1\ (\mathrm{mod}\ 998\\, 244\\, 353)$이기 때문에 $499\\, 122\\, 177$이 정답이 된다.