Tommy has an unrooted tree of $n$ nodes numbered $1,2,\dots ,n$. He wishes to assign weights to all nodes on some nonempty path on this tree such that the weight $w_i$ of a node $i$ on this path satisfies $l_i\le w_i\le r_i$ for given $[l_1,r_1],[l_2,r_2],\dots ,[l_n,r_n]$. Tommy has a positive integer $K$ and further requests that the maximum absolute difference of the weight of any two nodes on this path is less than or equal to $K$.

1. How many such assignments satisfy these constraints?
2. What is the sum of the sum of the weights over all such assignments?

Output the answer modulo ${10}^9+7$.

Constraints

$1\le n\le 200$

$1\le l_i\le r_i\le {10}^9$

$1\le K\le {10}^9$

$70\mathrm{\%}$ of points are awarded for the first question and $30\mathrm{\%}$ of points are awarded for the second question.

Test	$n\le$	$r_i,K\le$	Properties
1	$5$	$10$	None
2-3	$30$	${10}^9$	None
4	$30$	$500$	None
5-6	$200$	$2\times {10}^5$	None
7-8	$200$	${10}^9$	For $1\le i<n$, there is an edge between $i$ and $i+1$.
9-10	$200$	${10}^9$	None

Input Specification

The first line contains two integers $n,K$.

The $i$-th of the following $n$ lines contains two integers $l_i,r_i$.

The following $n-1$ lines describe the edges of the tree.

Output Specification

On the first line, output the answer for the first question.

On the second line, output the answer for the second question.

Please output exactly two integers, as otherwise your submission could be graded as Presentation Error.

Sample Input

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

Sample Output

14
78

Attachments