We are given a tree with ~N~ nodes denoted with different positive integers from ~1~ to ~N~.

Additionally, you are given ~M~ node pairs from the tree in the form of ~(a_1, b_1), (a_2, b_2), \dots, (a_M, b_M)~.

We need to direct each edge of the tree so that for each given node pair ~(a_i, b_i)~ there is a path from ~a_i~ to ~b_i~ or from ~b_i~ to ~a_i~. How many different ways are there to achieve this? Since the solution can be quite large, determine it modulo ~10^9 + 7~.

Input Specification

The first line of input contains the positive integers ~N~ and ~M~ ~(1 \le N, M \le 3 \cdot 10^5)~, the number of nodes in the tree and the number of given node pairs, respectively.

Each of the following ~N-1~ lines contains two positive integers, the labels of the nodes connected with an edge.

The ~i^{th}~ of the following ~M~ lines contains two different positive integers ~a_i~ and ~b_i~, the labels of the nodes from the ~i^{th}~ node pair. All node pairs will be mutually different.

Output Specification

You must output a single line containing the total number of different ways to direct the edges of the tree that meet the requirement from the task, modulo ~10^9 + 7~.

Scoring

In test cases worth 20% of total points, the given tree will be a chain. In other words, node ~i~ will be connected with an edge to node ~i+1~ for all ~i < N~.

In additional test cases worth 40% of total points, it will hold ~N, M \le 5 \cdot 10^3~.

Sample Input 1

4 1
1 2
2 3
3 4
2 4

Sample Output 1

4

Sample Input 2

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

Sample Output 2

8

Sample Input 3

4 3
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 3

0