問題文

長さ $N$ の整数列 $A=(a_1,a_2,\dots ,a_N)$ が与えられます。

$A$ からいくつかの要素を取り出し、元の順序を保ったまま並べることで数列 $B$ を作ることを考えます。より具体的には、$A$ から $i_1,i_2,\dots ,i_M$ 番目 ($1\le i_1<i_2<\cdots <i_M\le N$) の要素を取り出し、$B=(b_1,b_2,\dots ,b_M)=(a_{i_1},a_{i_2},\dots ,a_{i_M})$ とすることを考えます。

長さ $M$ の数列 $B$ に対する スコア を、$\sum _{i=1}^M(i\times b_i)$ と定義します。$B$ が長さ $0$ の列である場合のスコアは $0$ です。

$B$ としてあり得るすべての数列に対してスコアを計算し、その総和を $998244353$ で割った余りを求めてください。なお、ふたつの数列 $(a_{i_1},a_{i_2},\dots ,a_{i_{M_1}})$, $(a_{j_1},a_{j_2},\dots ,a_{j_{M_2}})$ は、以下の条件のうち少なくとも一方を満たすときに区別されます。

• 長さが異なる。すなわち $M_1\ne M_2$ である。
• 長さが等しく、添字列が異なる。すなわち $i_k\ne j_k$ となるような $k$ ($1\le k\le M_1$) が存在する。

入力

$N$
$a_1$ $a_2$ $\dots$ $a_N$

• $1\le N\le 500,000$
• $1\le a_i\le {10}^9$ ($1\le i\le N$)
• 入力はすべて整数で与えられる

出力

答えを $998244353$ で割った余りを出力してください。最後に改行してください。

サンプル

3
1 2 3

40

10
3 1 4 1 5 9 2 6 5 3

70656

20
107 308 203 269 817 203 123 593 200 252 753 198 200 201 987 222 687 354 901 734

944766948