問題文

以下の手続きで作られた無向グラフを、腕の本数 $X$ 、腕の長さ $(Y_1, Y_2, \cdots, Y_X)$ の岩井ツリーグラフと定義します。 また、$\mathrm{sum}~Y$ を $\displaystyle \sum_{i = 1}^X Y_i$ と定義します。

• $0$ から $\mathrm{sum} ~Y$ までの番号がそれぞれ割り当てられた $\mathrm{sum} ~ Y + 1$ 個の頂点を用意する。
• 変数 $s$ を $0$ で初期化する。
• $i = 1, 2, \cdots, X$ の順に以下の操作を繰り返す。
• 頂点 $s + 1$ と頂点 $s + 2$ 、頂点 $s + 2$ と頂点 $s + 3$ 、 $\cdots$ 、頂点 $s + Y_i - 1$ と頂点 $s + Y_i$ をそれぞれ辺で結ぶ。
• 頂点 $0$ と頂点 $s + 1$ を辺で結ぶ。
• $s$ に $Y_i$ を加算する。

この岩井ツリーグラフの頂点 $i$ と頂点 $j$ の距離を $f(i, j)$ と定義します。

$\displaystyle \sum_{i = 0}^{\mathrm{sum} ~ Y} \sum_{j = i + 1}^{\mathrm{sum} ~ Y} f(i, j)$ を $998244353$ で割った余りを求めてください。

入力

• $1 \leq X \leq 2 \times 10^5$
• $1 \leq Y_i \leq 10^9$
• 入力で与えられる値はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

$X$
$Y_1$ $Y_2$ $\cdots$ $Y_X$

出力

$\displaystyle \sum_{i = 0}^{\mathrm{sum} ~ Y} \sum_{j = i + 1}^{\mathrm{sum} ~ Y} f(i, j)$ を $998244353$ で割った余りを出力してください。

サンプル

4
3 1 4 1

134

9
9 9 8 2 4 4 3 5 3

7526

5
1000000000 1000000000 1000000000 1000000000 1000000000

742397401