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$ .
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 3Output
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$ .