20029 - 数星星

小明正在一棵树上数星星，这棵树有 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 行，一个整数表示答案。

包含 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。

蓝桥杯