406049: GYM102222 K Vertex Covers

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~(1\le n\le 36)$$$ and $$$m~(0\le m\le \frac{n(n-1)}{2})$$$ which are the number of vertices and the number of edges in the graph $$$G$$$, and $$$q~(10^8 \leq q \leq 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~(1\le u,v\le 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$$$.

2
4 3 998244353
1 1 1 1
1 2
2 3
3 4
4 6 998244353
1 1 1 1
1 2
1 3
1 4
2 3
2 4
3 4

Case #1: 8
Case #2: 5