This problem is a programming version of Problem 194 from projecteuler.net
Consider graphs built with two graph units and , where the graph units are glued along their leftmost and rightmost vertical edges. For example, if graph units and are 
and 
then the graph 
is built by gluing the units in the order .
A configuration of type is a graph thus built of units and units , where the graph's vertices are coloured using up to colours, so that no two adjacent vertices have the same colour.
The compound graph above is an example of a configuration of type , in fact of type for all .
Let be the number of configurations of type , where two configurations of type are considered the same if the corresponding coloured compound graphs are identical under translation transformation.
For example, with the graph units and as given above, , and .
Find the number modulo for a given pair of graph units and and the numbers , , and .
Input Format
The first line contains three space-separated integers: , , and , where and are number of graph units of type and respectively, and is the number of colours.
The subsequent lines define the graph units and . Each graph is defined as follows:
The first line contains two space-separated integers: which is the number of vertices and which is the number of edges in the graph being defined.
Each line of the subsequent lines (where ) contains two space-separated integers and describing the position of the -th vertex in the graph being defined, with as horizontal and as vertical dimension.
Each line of the subsequent lines (where ) contains two space-separated integers and describing the -th edge as connecting vertices and .
The first two edges in the given lists for each graph are vertical edges of the same length for both graph units, the first edge being the leftmost edge, and the second one being the rightmost edge. These edges are used for the graph units binding.
Constraints
- as number of units and ;
- as number of colours;
- for all as coordinates of the -th vertex, with no two vertices having the same coordinates;
- for all as vertex indices of the -th edge;
- , where and are number of vertices in the graph units and respectively.
Both graph units and are simple connected planar graphs.
The time restriction is a double of the usual time restriction.
Output Format
On a single line print one integer denoting the required number of graph configurations modulo .
Sample Input 0
1 2 3
4 6
0 4
0 0
4 4
4 0
1 2
3 4
1 3
1 4
2 3
2 4
4 3
6 0
6 4
10 2
10 6
1 2
3 4
2 3
Sample Output 0
0
Explanation 0
The given graph units and are as follows:
There are only three ways to glue the graph units and for a configuration of type : , , and .
However the graph unit cannot be coloured with just colours. Since the unit should be included in any configuration of the type then the total number of possible coloured configurations is zero.
Sample Input 1
1 1 2
4 3
0 0
0 4
4 0
4 4
1 2
3 4
2 3
6 6
6 0
6 4
10 4
10 8
6 8
7 4
1 2
3 4
2 6
3 6
4 5
5 6
Sample Output 1
4
Explanation 1
The given graph units and are as follows:
There are two ways to glue the units and together: and ; and there are two possible ways to colour each combined graph with colours:
Therefore the number of configurations of type is .
Sample Input 2
1 1 2
4 3
0 0
0 4
4 0
4 4
1 2
3 4
2 4
4 3
10 4
6 4
6 0
10 0
2 3
1 4
1 2
Sample Output 2
2
Explanation 2
The given graph units and are as follows:
The two possible bindings and generate the same compound graph that can be coloured in two ways:
Therefore the answer is .
Sample Input 3
1 0 3
7 10
0 0
0 4
2 4
2 0
1 1
1 2
1 3
1 2
3 4
1 4
1 5
2 3
2 7
3 7
4 5
5 6
6 7
7 9
4 0
4 4
6 4
6 0
5 1
5 2
5 3
1 2
3 4
1 5
2 3
2 7
3 7
4 5
5 6
6 7
Sample Output 3
24
Explanation 3
The given graph units and are as follows:
Since is zero, only the single unit of graph is used for colouring. There are ways to colour unit with colours:
