Given two connected graphs . You should count the number of ways to delete edges from such that becomes disconnected, where is the Cartesian product of and (See the next section for formal definitions).

In graph theory, the Cartesian product  of graphs  and  is a graph such that:

• the vertex set of is the Cartesian product ; and
• two vertices and are adjacent in if and only if either
• and is adjacent to in , or
• and is adjacent to in .

Since the answer might be large, you should output the answer modulo .

输入描述:

The input consists of descriptions of the two graphs  and  sequentially. 

For each graph, the first line contains two integers  , denoting the number of vertices and edges in the graph, followed by  lines, with each line containing two integers  , denoting an edge in the graph.

It is guaranteed that both graphs are connected, and have no self-loop or multiple edges.

输出描述:

Output an integer in a line, denoting the number of ways to delete  edges to disconnect the graph , taken modulo .

5 5
1 2
2 3
3 4
4 5
5 1
6 6
1 2
2 3
3 4
4 5
5 6
6 1

30

6 5
1 2
1 3
1 4
2 5
2 6
5 5
1 2
2 3
3 4
4 1
3 5

6154

备注: