题目描述

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

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

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

输入格式

输入共 $n + 1$ 行。

第一行为一个正整数 $n$。

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

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

输出格式

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

样例

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

6

提示

【样例说明】

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

包含 $4$ 个结点的星星有 $1$ 个，它的结点集合为 $\{1, 2, 4, 5\}$。

【评测用例规模与约定】

对于 $20\%$ 的评测用例，保证 $n \le 20$。 对于 $100\%$ 的评测用例，保证 $n \le 10^5$，$1 \le L \le R \le n$。