Problem Description

Xiaoming is counting stars on a tree. This tree has $n$ nodes $1, 2, \cdots, n$. He defines a subgraph $G$ on the tree to be a star if and only if $G$ satisfies all of the following:

1. $G$ is a tree.
2. There exists a node in $G$ whose degree is $|V_G| - 1$, where $|V_G|$ denotes the number of nodes contained in this subgraph.

Two stars are considered different if and only if their node sets $V_G$ are not exactly the same. Xiaoming wants to know how many different stars in this tree have a number of nodes within the interval $[L, R]$. Output the answer modulo $1000000007$.

Input Format

The input has a total of $n + 1$ lines.

The first line contains a positive integer $n$.

The next $n - 1$ lines each contain two positive integers, representing an edge of the tree.

The $(n + 1)$-th line contains two positive integers $L, R$.

Output Format

Output a total of $1$ line, containing one integer representing the answer.

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

6

Hint

Sample Explanation.

There are $5$ stars containing $3$ nodes, and their node sets are $\{1, 2, 3\}$, $\{1, 2, 4\}$, $\{1, 2, 5\}$, $\{2, 4, 5\}$, $\{1, 3, 6\}$.

There is $1$ star containing $4$ nodes, and its node set is $\{1, 2, 4, 5\}$.

Constraints.

For $20\%$ of the testdata, it is guaranteed that $n \le 20$.
For $100\%$ of the testdata, it is guaranteed that $n \le 10^5$, $1 \le L \le R \le n$.

Translated by ChatGPT 5