ION Attraction

Country P has \(N\) cities and \(M\) undirected roads. City 1 is the capital. It is guaranteed that any two cities are connected by some road. For the upcoming ION event at the capital, every city must supply raw materials to the capital. In particular, city \(i\) supplies material of type \(c_i\). From every city a truck departs and travels along a simple path (i.e. no repeated vertices) to the capital.

For any two distinct cities \(A\) and \(B\), if every simple path from \(B\) to the capital passes through \(A\), then we say that city \(A\) is on the mandatory path from \(B\) to the capital.

For three cities \(A, B, C\), if for every simple path from \(B\) to \(A\) and every simple path from \(C\) to \(A\) there is no common edge, then we say that \(B\) and \(C\) are non interfering with respect to \(A\>.

For every city \(A\) and every integer \(k\ge 1\), define \(f(A,k)\) as the number of \(k\)-element sets \(\{B_1, B_2, \dots, B_k\}\) satisfying the following conditions:

1. For each \(1\le i\le k\) we have \(B_i\neq A\), city \(A\) is on the mandatory path from \(B_i\) to the capital, and \(c_{B_i}\neq c_A\).
2. For any two distinct indices \(i<j\), if \(B_i\) and \(B_j\) are non interfering with respect to \(A\), then they must supply different types of raw materials, i.e. \(c_{B_i}\neq c_{B_j}\).

The attraction of hosting ION is defined as \(\sum_{A=1}^{N} \sum_{k=1}^{K} f(A,k)\), where \(K\) is a given constant. Since the answer might be huge, output it modulo \(998244353\).

Note: A simple path is a path that does not visit any vertex more than once.

inputFormat

The input starts with a line containing three integers \(N\), \(M\) and \(K\) \( (2 \le N,\ M;\ K \ge 1)\). The next line contains \(N\) integers \(c_1, c_2, \dots, c_N\), where \(c_i\) represents the type of material that city \(i\) supplies. Each of the following \(M\) lines contains two integers \(u\) and \(v\) denoting an undirected road between cities \(u\) and \(v\>.

It is guaranteed that any two cities are connected by roads.

outputFormat

Output a single integer denoting the ION attraction modulo \(998244353\).

sample

2 1 1
1 2
1 2

1