题目描述

P 国有 $N$ 座城市和 $M$ 条无向道路，其中 $1$ 号城市是首都，且任意两座城市都能通过道路互相到达。

现在 P 国要在首都召开 ION。为了建设比赛场地，每个城市都要向首都提供原材料，其中第 $i$ 座城市可以提供类型为 $c_i$ 的原材料。每座城市都会有货车从该城市出发，沿简单路径前往首都。如果从城市 $A$ 出发的货车必须经过城市 $B$ ，那么我们称城市 $B$ 在城市 $A$ 到首都的必经之路上。如果对于城市 $A,B,C$，从 $B$ 到 $A$ 的任意简单路径与 $C$ 到 $A$ 的任意简单路径没有公共边，那么我们称城市 $B$ 和城市 $C$ 关于城市 $A$ 互不影响。

记 $f(A,k)$ 为满足下列所有条件的 $k$ 元集合 $\{B_1,B_2,\cdots B_k\}$ 的个数：

1. 对于任意 $1\leq i \leq k$ 满足 $A\neq B_i$，城市 $A$ 在城市 $B_i$ 到首都的必经之路上且城市 $B_i$ 供应的材料与城市 $A$ 不同。

2. 对于任意 $1\leq i < j \leq k$ 满足 $B_i$ 与 $B_j$ 关于 $A$ 互不影响，且 $B_i$ 和 $B_j$ 供应的原材料相同。

定义举办 ION 的吸引力为$\sum_{i=1}^N\sum_{k=1}^Kf(i,k)$，其中 $K$ 是给定的常数。

现在，你作为 P 国的首脑，你想要知道这次 ION 的吸引力。

由于答案可能很大，所以请将答案对 $998244353$ 取模。

输入格式

第一行三个整数 $N,M,K$。

第二行 $N$ 个整数，第 $i$ 个数第 $i$ 座城市供应的原材料类型 $c_i$。

接下来 $M$ 行，每行两个整数 $u,v$ ，表示 $P$ 国的一条道路。保证没有重边，没有自环。（$1\leq u, v \leq N, u\neq v$）

输出格式

一行一个整数表示答案。

7 7 2
1 2 3 3 1 1 2
1 2
2 3
2 4
3 4
3 5
3 6
4 7

12

提示

【样例解释】

样例中 P 国的地图如下：

下表中，第 $i$ 行第 $j$ 列表示 $f(i,j)$。

所以吸引力为 $4+4+2+1+1=12$。

【数据范围】

本题采用捆绑测试。

• Subtask1（10pts）：$N,K \le 8$；
• Subtask2（10pts）：$K=1$；
• Subtask3（15pts）：$K=2$；
• Subtask4（15pts）：保证图的形态为一棵树；
• Subtask5（15pts）：$N \le 2000$；
• Subtask6（15pts）：$N \le 4\times 10^4$；
• Subtask7（20pts）：无特殊限制。

对于 $100\%$ 的数据满足，$1\leq N\leq 5\times 10^5$， $1\leq M \leq \min(10^6,\frac{N\times(N-1)}{2})$，$1 \le K \le 20$，$1 \le c_i \le 10^9$。

温馨提示：输入量较大，请使用较快的读入方式。