Tree Path Weight Assignment

We are given an undirected tree with (n) nodes (numbered from 1 to (n)). Initially every node has weight 0. Each node (i) has an allowed range ([l_i, r_i]) of positive integers. KK will perform the following process on the tree:

1. Choose an arbitrary node as the starting (current) node, and set its weight to a positive integer (x) satisfying (l_i \le x \le r_i).
2. Then, repeatedly, either stop the process or move from the current node to an adjacent node that has weight 0 and update its weight similarly (choosing a value in its valid range). If no such adjacent node exists, the process stops.

Effectively, KK selects any simple path in the tree and assigns each node (i) on that path a value (x_i) satisfying (l_i \le x_i \le r_i). However, the assignment is considered valid only if the difference between the maximum and minimum assigned values on that path is at most (K) (i.e. if (\max_i x_i - \min_i x_i \le K)).

Your task is to answer two questions modulo (10^9+7):

1. How many different trees (i.e. assignments) can be obtained? Two trees are considered different if at least one node has a different weight. (Nodes not on the chosen path remain 0, and note that KK will update at least one node.)

2. What is the sum of weights of all nodes over all valid trees?

Input/Output Format:

The input begins with two positive integers (n) and (K). Then (n-1) lines follow, each containing two integers (u) and (v) representing an edge between nodes (u) and (v). Finally, (n) lines follow; the (i)-th of these lines contains two integers (l_i) and (r_i), indicating the allowed range for node (i).

Output two integers: the number of valid trees and the sum of their weights, both taken modulo (10^9+7).

Note:

• KK always modifies at least one node (the starting node).
• In essence, KK is choosing any simple path in the tree and assigning a value to each node on that path.

inputFormat

The first line contains two integers (n) and (K) (the number of nodes and the maximum allowed difference).
Then (n-1) lines follow, each with two integers (u) and (v) denoting an edge of the tree.
Then (n) lines follow; the (i)-th line contains two integers (l_i) and (r_i) (the allowed range for node (i)).

outputFormat

Output two integers separated by a space: the number of different valid trees and the sum of weights of all valid trees, both modulo (10^9+7).

sample

3 2
1 2
2 3
1 3
1 2
2 3

29 123