F. Colored Treetime limit per test2.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou're given a tree with n vertices. The color of the i-th vertex is h_{i}.The value of the tree is defined as \sum\limits_{h_{i} = h_{j}, 1 \le i < j \le n}{dis(i,j)}, where dis(i,j) is the number of edges on the shortest path between i and j. The color of each vertex is lost, you only remember that h_{i} can be any integer from [l_{i}, r_{i}](inclusive). You want to calculate the sum of values of all trees meeting these conditions modulo 10^9 + 7 (the set of edges is fixed, but each color is unknown, so there are \prod\limits_{i = 1}^{n} (r_{i} - l_{i} + 1) different trees).InputThe first line contains one integer n (2 \le n \le 10^5) — the number of vertices.Then n lines follow, each line contains two integers l_i and r_i (1 \le l_i \le r_i \le 10^5) denoting the range of possible colors of vertex i.Then n - 1 lines follow, each containing two integers u and v (1 \le u, v \le n, u \ne v) denoting an edge of the tree. It is guaranteed that these edges form a tree.OutputPrint one integer — the sum of values of all possible trees, taken modulo 10^9 + 7.ExampleInput
4
1 1
1 2
1 1
1 2
1 2
1 3
3 4
Output
22
NoteIn the first example there are four different ways to color the tree (so, there are four different trees):  a tree with vertices colored as follows: \lbrace 1,1,1,1 \rbrace. The value of this tree is dis(1,2)+dis(1,3)+dis(1,4)+dis(2,3)+dis(2,4)+dis(3,4) = 10;  a tree with vertices colored as follows: \lbrace 1,2,1,1 \rbrace. The value of this tree is dis(1,3)+dis(1,4)+dis(3,4)=4;  a tree with vertices colored as follows: \lbrace 1,1,1,2 \rbrace. The value of this tree is dis(1,2)+dis(1,3)+dis(2,3)=4;  a tree with vertices colored as follows: \lbrace 1,2,1,2 \rbrace. The value of this tree is dis(1,3)+dis(2,4)=4. Overall the sum of all values is 10+4+4+4=22.
4
1 1
1 2
1 1
1 2
1 2
1 3
3 4

22 
['data structures', 'trees', '*2700']