Problem Description

Country $P$ has $N$ cities and $M$ undirected roads. City $1$ is the capital, and any two cities can reach each other through roads.

Now Country $P$ is going to hold ION in the capital. To build the contest venue, each city needs to provide raw materials to the capital. City $i$ can provide raw material of type $c_i$. Each city will have a truck departing from that city and going to the capital along a simple path. If the truck starting from city $A$ must pass through city $B$, then we say that city $B$ lies on the unavoidable path from city $A$ to the capital. If for cities $A, B, C$, any simple path from $B$ to $A$ and any simple path from $C$ to $A$ have no common edges, then we say that cities $B$ and $C$ are independent of each other with respect to city $A$.

Let $f(A,k)$ be the number of $k$-element sets $\{B_1,B_2,\cdots B_k\}$ that satisfy all of the following conditions:

1. For any $1 \le i \le k$ with $A \neq B_i$, city $A$ lies on the unavoidable path from city $B_i$ to the capital, and the material supplied by city $B_i$ is different from that of city $A$.

2. For any $1 \le i < j \le k$, $B_i$ and $B_j$ are independent with respect to $A$, and the raw materials supplied by $B_i$ and $B_j$ are the same.

Define the attractiveness of holding ION as $\sum_{i=1}^N \sum_{k=1}^K f(i,k)$, where $K$ is a given constant.

Now, as the leader of Country $P$, you want to know the attractiveness of this ION.

Since the answer may be very large, please output the answer modulo $998244353$.

Input Format

The first line contains three integers $N, M, K$.

The second line contains $N$ integers. The $i$-th number is the type of raw material $c_i$ supplied by city $i$.

The next $M$ lines each contain two integers $u, v$, indicating a road in Country $P$. It is guaranteed that there are no multiple edges and no self-loops. ($1 \le u, v \le N, u \neq v$)

Output Format

Output one integer, the answer.

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

Hint

[Sample Explanation]

In the sample, the map of Country $P$ is as follows:

In the table below, the entry in row $i$ and column $j$ represents $f(i,j)$.

So the attractiveness is $4 + 4 + 2 + 1 + 1 = 12$.

[Constraints]

This problem uses bundled testdata.

• Subtask 1 (10 pts): $N, K \le 8$.
• Subtask 2 (10 pts): $K = 1$.
• Subtask 3 (15 pts): $K = 2$.
• Subtask 4 (15 pts): the graph is guaranteed to be a tree.
• Subtask 5 (15 pts): $N \le 2000$.
• Subtask 6 (15 pts): $N \le 4 \times 10^4$.
• Subtask 7 (20 pts): no special constraints.

For $100\%$ of the data: $1 \le N \le 5 \times 10^5$, $1 \le M \le \min\left(10^6, \frac{N \times (N - 1)}{2}\right)$, $1 \le K \le 20$, $1 \le c_i \le 10^9$.

Warm reminder: The input is large, so please use a fast input method.

Translated by ChatGPT 5