City Partitioning and State Satisfaction

We are given n cities numbered from 1 to n. The i-th city has a population w_i. Some pairs of cities are connected by bidirectional roads. It is possible that some pairs of cities are not directly connected by a road.

You are to partition these n cities into one or more states. In a partition, each state is a nonempty set of cities and every city belongs to exactly one state. The states are given in a fixed order: if the partition consists of k states, we denote them by V₁, V₂, …, V_k in order. Two partitions are considered different if the number of states k is different or for some index i we have V_i different.

Define an internal road of a state as a road whose both endpoints lie in that state. A state is defined as illegal if there exists a path (which may be of length 0) that:

• starts and ends at the same city;
• never visits a city outside the state;
• traverses every internal road of the state exactly once (i.e. forms an Eulerian circuit for the state), and
• visits every city in the state at least once.

Note that a path of length 0 is allowed. In particular, if a state consists of a single city (with no road) then the trivial 0-length path qualifies, and the state is illegal.

For a legal partition (i.e. one in which no state is illegal), define the satisfaction of state i (for i = 1,2,…,k) as

$$\left(\frac{\sum_{x\in V_i} w_x}{\sum_{j=1}^{i}\sum_{x\in V_j} w_x}\right)^p, $$

and the satisfaction of the partition is the product of the satisfactions of its states. Here, p is an integer exponent given in the input.

Your task is to compute the sum of the satisfaction values over all legal partitions, taken modulo 998244353.

Input

The input consists of the following:

• The first line contains three integers n, m and p – the number of cities, the number of roads and the exponent (1 ≤ n ≤ small since the intended solution is by complete search, m ≥ 0, and p ≥ 0).
• The second line contains n integers w₁, w₂, ..., w_n, where w_i is the population of city i.
• Each of the next m lines contains two integers u and v indicating that there is a bidirectional road between cities u and v (1-indexed).

Output

Output a single integer – the sum of the satisfaction values of all legal partitions modulo 998244353.

---

Explanation of the legality condition: For a state, consider the subgraph induced by the cities in that state and the roads whose both endpoints belong to the state. If this induced graph is connected and every vertex in it has even degree, then an Eulerian circuit exists (note that in a single-vertex state with no edges, the trivial 0-length path qualifies). Such a state is illegal. Otherwise, the state is legal. A partition is legal if and only if every state in it is legal.

Note: Since the number of partitions can be huge, it is guaranteed that n is small (for example, n ≤ 8), so that an exhaustive search is possible.

inputFormat

The first line contains three integers n, m and p.

The second line contains n integers: w₁ w₂ ... w_n.

Then m lines follow, each containing two integers u v indicating a road between cities u and v.

You can assume that 1 ≤ n ≤ 8, m ≥ 0, and p ≥ 0.

outputFormat

Output a single integer – the sum of satisfaction values over all legal partitions modulo 998244353.

sample

2 0 1
3 5

1