There is a rootless tree with $n$ nodes, and initially, the weight of each node is 0. KK wants to perform some modifications on this tree. He will choose an arbitrary node as the initial current node and then repeat the following actions:

1. Modify the weight of the current node $i$ to a positive integer $x$, satisfying $l_i \le x \le r_i$, where $l_i$ and $r_i$ are two positive integers given in the input.
2. Either end the modification process or move to an adjacent node whose current weight is 0 (if no such node exists, the modification process must end).

Now KK has two questions:

1. After the modification process ends, how many different trees can be obtained such that the difference between the maximum and minimum non-zero weights in the tree is less than or equal to $K$? Here, $K$ is a positive integer given in the input.
2. What is the sum of the weights of these valid trees? (The weight of a tree is defined as the sum of the weights of all nodes in the tree.)

You need to output the answers to these two questions modulo $10^9 + 7$. We consider two trees to be different if and only if there is at least one node with a different weight.

Tips: 1. KK will modify at least one node (the initial node). 2. In essence, KK will modify an arbitrary path on the tree, and finally, the difference between the maximum and minimum weights of the nodes on this path must be less than or equal to $K$.

Input

The first line contains two positive integers $n$ and $K$, representing the number of nodes and the maximum allowed difference in weights.

The next $n$ lines each contain two positive integers $l_i$ and $r_i$, representing the minimum and maximum values for the weight of node $i$ after modification.

The next $n - 1$ lines each contain two positive integers $u_i$ and $v_i$, representing an edge between nodes $u_i$ and $v_i$. The data is guaranteed to form a tree.

Output

Output two lines, each containing an integer, representing the answers to the first and second questions modulo $10^9 + 7$, respectively. Note that if you do not intend to answer the second question, please output any integer on the second line. If the output file contains only one line, it will be scored 0 points for failing to meet the format requirements.

Examples

Input 1

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

Output 1

14
78

Note 1

The table below lists all 14 valid trees, and the sum of the weights of these trees is 78.

Example 2

See tree/tree2.in and tree/tree2.ans in the contestant directory.

Example 3

See tree/tree3.in and tree/tree3.ans in the contestant directory.

Constraints

For 100% of the data, $1 \le n \le 200$, $1 \le l_i \le r_i \le 10^9$, $1 \le K \le 10^9$.

Scoring

This problem has 10 test cases, each worth 10 points. Answering the first question correctly earns 7 points, and answering the second question correctly earns 3 points.