Given a tree ( is the set of vertices and is the set of edges) and a set of pairs of vertices satisfying for all , and is an ancestor of on tree , you are supposed to compute how many functions (i.e. for each edge , the value of would be either or ) satisfies the condition for any there exists an edge on the path from to such that . Output the answer modulo .

#### Input Specification

The first line contains an input denoting the number of vertices in tree . The nodes are numbered from 1 to and the root node is node 1. In the following lines, each line contains two integers separated by a space such that denoting there exists an edge on the tree between node and . There are no guarantees for the direction of the edge. The following line contains an integer denoting the size of . In the following lines, each line contains two integers separated by a space denoting . There may be duplication, or in other words, there might exist some such that and .

#### Output Specification

The output contains only an integer denoting the number of functions satisfying the condition above.

#### Sample Input 1

```
5
1 2
2 3
3 4
3 5
2
1 3
2 5
```

#### Sample Output 1

`10`

#### Sample Input 2

```
15
2 1
3 1
4 3
5 2
6 3
7 6
8 4
9 5
10 7
11 5
12 10
13 3
14 9
15 8
6
3 12
5 11
2 5
3 13
8 15
1 13
```

#### Sample Output 2

`960`

#### Constraints

For all test cases, , .

The input forms a tree, where for all , is the ancestor of .

Test Case | Additional Constraints | ||
---|---|---|---|

1 | None. | ||

2 | |||

3 | |||

4 | |||

5 | |||

6 | |||

7 | |||

8 | |||

9 | |||

10 | |||

11 | |||

12 | |||

13 | |||

14 | |||

15 | |||

16 | |||

17 | See below. | ||

18 | |||

19 | None. | ||

20 | |||

21 | |||

22 | |||

23 | |||

24 | |||

25 |

In this problem, a perfect binary tree is a binary tree such that each non-leaf node has two children and the depths of all leaf nodes are the same; if we number the nodes in a perfect binary tree from up to down, from left to right, the tree formed by the nodes with smallest numbers form a complete binary tree. Test cases 17 and 18 are complete binary trees.

## Comments