「PMOI-2」城市

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$ | $0$ | $0$ | $0$ | | -----------: | -----------: | -----------: | -----------: | $4$ | $0$ | $0$ | $0$ | | $2$ | $1$ | $0$ | $0$ | | $1$ | $0$ | $0$ | $0$ | 所以吸引力为 $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$。 **温馨提示**：输入量较大，请使用较快的读入方式。