给你一棵有 $$$n$$$ 个顶点的树。第 $$$i$$$ 个顶点的颜色为 $$$h_{i}$$$。
树的值定义为 $$$\sum\limits_{h_{i} = h_{j}, 1 \le i < j \le n}{dis(i,j)}$$$,其中 $$$dis(i,j)$$$ 是 $$$i$$$ 和 $$$j$$$ 之间最短路径上的边数。
每个顶点的颜色都丢失了,你只记得$$$h_{i}$$$可以是$$$[l_{i}, r_{i}]$$$(包含)中的任何整数。您想要计算满足这些条件的所有树的值的总和 $$$10^9 + 7$$$ 模(边集是固定的,但每种颜色是未知的,因此有 $$$\prod\limits_{i = 1}^{n} (r_{i} - l_{i} + 1)$$$ 不同的树)。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 顶点数。
接下来是 $$$n$$$ 行,每行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^5$$$) 表示顶点 $$$i$$$ 可能颜色的范围。
接下来是 $$$n - 1$$$ 行,每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) 表示树的一条边。保证这些边形成一棵树。
输出
打印一个整数 — 所有可能树的值之和,以 $$$10^9 + 7$$$ 为模。
示例
输入 #1
4 1 1 1 2 1 1 1 2 1 2 1 3 3 4
输出 #1
22
注意
在第一个示例中,有四种不同的方法为树着色(因此,有四种不同的树):
- 顶点颜色如下的树:$$$\lbrace 1,1,1,1 \rbrace$$$。这棵树的值为$$$dis(1,2)+dis(1,3)+dis(1,4)+dis(2,3)+dis(2,4)+dis(3,4) = 10$$$;
- 顶点颜色如下的树:$$$\lbrace 1,2,1,1 \rbrace$$$。这棵树的值为$$$dis(1,3)+dis(1,4)+dis(3,4)=4$$$;
- 顶点颜色如下的树:$$$\lbrace 1,1,1,2 \rbrace$$$。这棵树的值为$$$dis(1,2)+dis(1,3)+dis(2,3)=4$$$;
- 顶点颜色如下的树:$$$\lbrace 1,2,1,2 \rbrace$$$。这棵树的值是$$$dis(1,3)+dis(2,4)=4$$$。
总体而言,所有值的总和为 $$$10+4+4+4=22$$$。