枚举三角形（Enumerate Triangles）

问题描述

给定一个简单无向图，含 $N$ 个顶点和 $M$ 条边。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。
每个顶点 $i$ 有一个整数值 $x_i$。

若三个顶点 $a, b, c$ 满足 $a < b < c$，且三者两两之间均有边（即 $\{a,b\}, \{a,c\}, \{b,c\}$ 均为图中的边），则称 $(a,b,c)$ 为一个三角形。

求所有三角形 $(a,b,c)$ 对应的乘积 $x_a x_b x_c$ 之和，并输出该和模 $998244353$。

约束条件

• $1 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $0 \leq x_i < 998244353$
• $0 \leq u_i, v_i < N$
• $u_i \ne v_i$
• $\{u_i, v_i\} \ne \{u_j, v_j\}$（$i \ne j$，无重边）

输入

$N\ M$
$x_0\ x_1\ \cdots\ x_{N-1}$
$u_0\ v_0$
$u_1\ v_1$
:
$u_{M-1}\ v_{M-1}$

输出

$A$

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

36

样例解释

三角形是 $\{0,2,3\}$ 和 $\{1,2,3\}$。

具体计算:

• 对于三角形 $\{0,2,3\}$: $x_0 \times x_2 \times x_3 = 1 \times 3 \times 4 = 12$。

• 对于三角形 $\{1,2,3\}$: $x_1 \times x_2 \times x_3 = 2 \times 3 \times 4 = 24$。

• 总和等于 $12 + 24 = 36$, 输出 $36$。