Counting Star Subtrees

Xiao Ming is counting stars on a tree with \(n\) nodes labeled \(1, 2, \ldots, n\). A subgraph \(G\) of the tree is called a star if and only if:

1. \(G\) is a tree.
2. There exists a node \(v\) in \(G\) whose degree equals \(|V_G| - 1\), where \(|V_G|\) denotes the number of vertices in \(G\). In other words, one node is adjacent to every other node in \(G\).

Two stars are considered different if and only if their vertex sets \(V_G\) are different.

Given a tree and two integers \(L\) and \(R\), count the number of different stars whose number of vertices is between \(L\) and \(R\) (inclusive). Output the answer modulo \(10^9+7\).

Observation: In any tree, a star is completely determined by choosing a center vertex \(v\) and selecting some of its adjacent neighbors in the original tree. If \(v\) has degree \(d_v\) in the given tree, then for any integer \(k\) such that \(k+1\) (the number of vertices in the star, including the center) lies in \([L, R]\) and \(0 \le k \le d_v\), there are \(\binom{d_v}{k}\) possible stars with \(v\) as center. The final answer is the sum over all vertices \(v\) of the valid choices.

inputFormat

The first line contains three integers \(n\), \(L\), and \(R\) (\(1 \leq n \leq 10^5\), \(1 \leq L \leq R \leq n\)).

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) (\(1 \leq u, v \leq n\)), representing an edge in the tree.

outputFormat

Output a single integer, the number of star subtrees whose vertex count is between \(L\) and \(R\), modulo \(10^9+7\).

sample

3 1 2
1 2
2 3

7