Source: Library Checker

Statement

You are given a simple undirected graph, consisting of $N$ vertices and $M$ edges. The $i$-th edge is $\lbrace u_i, v_i \rbrace$. Each vertex has an integer value, and the value of $i$ th vertex is $x_i$.

Three vertices $a, b, c (a \lt b \lt c)$ connected by three edges $\lbrace a, b \rbrace, \lbrace a, c \rbrace, \lbrace b, c \rbrace$ are called triangle. Find the sum of $x_a x_b x_c$ over all triangles, and print the sum modulo $998\,244\,353$ .

$N$ 頂点 $M$ 辺の単純無向グラフが与えられます。 $i$ 番目の辺は $\lbrace u_i, v_i \rbrace$ です。 各頂点 $i$ には整数 $x_i$ が割り当てられています。

3 頂点 $a, b, c (a \lt b \lt c)$ であって辺 $\lbrace a, b \rbrace, \lbrace a, c \rbrace, \lbrace b, c \rbrace$ が全て存在するものを triangle と呼びます。 全ての triangle についての $x_a x_b x_c$ の和を $998\,244\,353$ で割った余りを求めてください。

Constraints

• $1 \le N \le 10^5$
• $1 \le M \le 10^5$
• $0 \le x_i \lt 998\,244\,353$
• $0 \le u_i \lt N$
• $0 \le v_i \lt N$
• $u_i \neq v_i$
• $\lbrace u_i, v_i \rbrace \neq \lbrace u_j, v_j \rbrace \ (i \neq j)$

Input

• $N$ $M$
• $x_0$ $x_1$ $\ldots$ $x_{N-1}$
• $u_0$ $v_0$
• $u_1$ $v_1$
• $\vdots$
• $u_{M-1}$ $v_{M-1}$

Ouput

• $A$

Example

Input

4 5
1 2 3 4
0 3
2 0
2 1
2 3
1 3

Output

36

$0, 2, 3$ and $1, 2, 3$ are triangles. Print $36$, which is the result of $1 \cdot 3 \cdot 4 + 2 \cdot 3 \cdot 4 \bmod 998\,244\,353$ .

$0, 2, 3$ 及び $1, 2, 3$ が triangle です。 $1 \cdot 3 \cdot 4 + 2 \cdot 3 \cdot 4$ を $998\,244\,353$ で割った余りである $36$ を出力します。