数星星

题目描述

小明正在一棵树上数星星，这棵树有 $n$ 个结点 $1, 2, . . . , n$。他定义树上的一个子图 $G$ 是一颗星星，当且仅当 $G$ 同时满足：

1. $G$ 是一棵树。

2. $G$ 中存在某个结点，其度数为 $|V_G| − 1$。其中 $|V_G|$ 表示这个子图含有的结点数。

两颗星星不相同当且仅当它们包含的结点集合 $V_G$ 不完全相同。小明想知道这棵树上有多少颗不同的星星包含的结点的数量在区间 $[L, R]$ 中，答案对 $1000000007$ 取模。

在无根无向树中，一个节点的度指的是有多少个节点与它直接连接。例如样例(下方有图)中，节点 $2$ 的度为 $3$，因为存在 $\{1, 4, 5\}$ 这三个节点与它直接连接。

输入格式

输入共 $n + 1$ 行。

第一行为一个正整数 $n(1 \le n \le 10^5)$。

后面 $n − 1$ 行，每行两个正整数表示树上的一条边。

第 $n + 1$ 行，两个正整数 $L$, $R(1 \le L \le R \le n)$。

输出格式

输出共 1 行，一个整数表示答案。

样例 #1

样例输入 #1

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

样例输出 #1

6

提示

【样例说明】 包含 $3$ 个结点的星星有 $5$ 个，它们的结点集合分别为 $\{1, 2, 3\}，\{1, 2, 4\}，\{1, 2, 5\}，\{2, 4, 5\}，\{1, 3, 6\}$。包含 $4$ 个结点的星星有 $1$ 个，它的结点集合为 $\{1, 2, 4, 5\}$。