Problem Description

There is an undirected tree with $n$ nodes, initially each node has a weight of $0$. KK wants to modify this tree by performing the following actions, starting from any chosen node:

1. Change the weight of the current node $i$ to a positive integer $x$, where $l_i \leq x \leq r_i$. Here, $l_i$ and $r_i$ are positive integers provided in the input.
2. Either end the modification process or move to an adjacent node with a weight of $0$ (if no such node exists, the modification process must end).

KK has two questions:

1. How many distinct trees can be formed at the end of the modification such that the difference between the maximum and minimum non-zero weights is less than or equal to $K$? $K$ is a positive integer given in the input.
2. What is the sum of the weights of all trees that meet the condition? (The weight of a tree is defined as the sum of the weights of all its nodes.)

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

Notes:

1. KK will modify at least one node (the initial node).
2. Essentially, KK modifies any path on the tree, and the final condition requires the difference between the maximum and minimum weights on this path to be less than or equal to $K$.

Input Format

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$, indicating the minimum and maximum possible weights for the $i$-th node after modification.

The following $n - 1$ lines each contain two positive integers $u_i$ and $v_i$, indicating an edge between node $u_i$ and node $v_i$. The data guarantees that these edges form a tree.

Output Format

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, output any integer on the second line. If only one line is output, it may be judged as $0$ due to format requirements.

Sample Input and Output

Sample Input #1

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

Sample Output #1

14
78

Sample Input #2

See the attached file tree/tree2.in

Sample Output #2

See the attached file tree/tree2.ans

Sample Input #3

See the attached file tree/tree3.in

Sample Output #3

See the attached file tree/tree3.ans

Notes

[Sample Explanation #1]

The table below lists all 14 trees that meet the conditions, with their weights summing up to 78.

[Data Range]

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

Special Constraint A: All nodes form a chain, with an edge between node $i$ and node $i + 1$.

[Scoring Method]

There are 10 test points, each worth 10 points. Correctly answering the first question earns 7 points, and correctly answering the second question earns 3 points.

见题面 Input 部分

见题面 Output 部分