In graph theory, a vertex cover of a graph $G$ is a set of vertices $S$ such that each edge of the graph is incident to at least one vertex of the set. That is to say, for every edge $(u, v)$ of the graph, either $u$ or $v$ is in the vertex cover $S$.
Now, Kamilah shows you an undirected graph $G$ without loops or multiple edges, each vertex of which has a weight. She can evaluate a vertex cover $S$ of $G$ by the product of weights of all vertices belonging to $S$. Here, the product of an empty set (of numbers) is defined as $1$.
You are asked to calculate the sum of the evaluations described above for all vertex covers of $G$.
The input contains several test cases, and the first line is an integer $T$ indicating the number of test cases which is up to $3600$.
For each test case, the first line contains three integers $n med (1 <= n <= 36)$ and $m med (0 <= m <= frac(n (n -1), 2))$ which are the number of vertices and the number of edges in the graph $G$, and $q med (10^8 <= q <= 10^9)$ which is a prime number for the output.
The second line contains $n$ integers, the $i$-th of which is the weight of the $i$-th vertices in $G$. All weights are in the range of $1$ to $10^9$.
Each of the following $m$ lines contains two integers $u$ and $v med (1 <= u, v <= n)$ describing an edge between the $u$-th vertex and the $v$-th one.
We guarantee that no more than $36$ test cases satisfy $n > 18$.
For each test case, output a line containing _Case #x: y_, where _x_ is the test case number starting from $1$, and _y_ is the remainder of the answer dividing by $q$.
## Input
The input contains several test cases, and the first line is an integer $T$ indicating the number of test cases which is up to $3600$.For each test case, the first line contains three integers $n med (1 <= n <= 36)$ and $m med (0 <= m <= frac(n (n -1), 2))$ which are the number of vertices and the number of edges in the graph $G$, and $q med (10^8 <= q <= 10^9)$ which is a prime number for the output.The second line contains $n$ integers, the $i$-th of which is the weight of the $i$-th vertices in $G$. All weights are in the range of $1$ to $10^9$.Each of the following $m$ lines contains two integers $u$ and $v med (1 <= u, v <= n)$ describing an edge between the $u$-th vertex and the $v$-th one.We guarantee that no more than $36$ test cases satisfy $n > 18$.
## Output
For each test case, output a line containing _Case #x: y_, where _x_ is the test case number starting from $1$, and _y_ is the remainder of the answer dividing by $q$.
[samples]
**Definitions**
Let $ G = (V, E) $ be an undirected graph with $ |V| = n $, $ |E| = m $, and no loops or multiple edges.
Let $ w: V \to \mathbb{Z}^+ $ be a weight function on vertices, with $ w_i $ denoting the weight of vertex $ i $.
Let $ \mathcal{S} $ be the set of all vertex covers of $ G $.
**Constraints**
1. $ 1 \le n \le 36 $, $ 0 \le m \le \frac{n(n-1)}{2} $
2. $ 10^8 \le q \le 10^9 $, $ q $ prime
3. $ 1 \le w_i \le 10^9 $ for all $ i \in V $
4. At most 36 test cases have $ n > 18 $
**Objective**
Compute:
$$
\sum_{S \in \mathcal{S}} \prod_{v \in S} w_v \mod q
$$
where the product over the empty set is defined as 1.