Source: Library Checker
Statement
You are given a simple undirected graph, consisting of N vertices and M edges. The i-th edge is {ui,vi}. Each vertex has an integer value, and the value of i th vertex is xi.
Three vertices a,b,c(a<b<c) connected by three edges {a,b},{a,c},{b,c} are called triangle. Find the sum of xaxbxc over all triangles, and print the sum modulo 998244353 .
N 頂点 M 辺の単純無向グラフが与えられます。 i 番目の辺は {ui,vi} です。 各頂点 i には整数 xi が割り当てられています。
3 頂点 a,b,c(a<b<c) であって辺 {a,b},{a,c},{b,c} が全て存在するものを triangle と呼びます。 全ての triangle についての xaxbxc の和を 998244353 で割った余りを求めてください。
Constraints
- 1≤N≤105
- 1≤M≤105
- 0≤xi<998244353
- 0≤ui<N
- 0≤vi<N
- ui≠vi
- {ui,vi}≠{uj,vj} (i≠j)
Input
- N M
- x0 x1 … xN−1
- u0 v0
- u1 v1
- ⋮
- uM−1 vM−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⋅3⋅4+2⋅3⋅4mod .
0, 2, 3 及び 1, 2, 3 が triangle です。 1 \cdot 3 \cdot 4 + 2 \cdot 3 \cdot 4 を 998\,244\,353 で割った余りである 36 を出力します。