L. Simple Tree Decomposition Problem
time limit per test
3 seconds
memory limit per test
1024 mebibytes
input
standard input
output
standard output

BOOM! Dohoon's head has exploded while solving the tree decomposition practice problem given as an assignment while attending the Summer School on Combinatorics and Algorithms at KAIST. Dohoon's brain, now unable to focus on the problem, is idling away time performing 'decomposition' on a 'tree' instead of doing tree decomposition on general graphs.

Specifically, Dohoon is given a tree with $$$N$$$ vertices. He plans to decompose the tree into a collection of connected components as follows:

  1. Dohoon will select zero or more edges from the tree and remove them from the tree. Let $$$S$$$ be the set of removed edges in this procedure.
  2. After the edges in $$$S$$$ are removed, each connected component in the resulting graph must have either $$$A$$$ or $$$B$$$ vertices.

Help Dohoon find the number of different ways to decompose the tree as given above. To be specific, determine the number of possible sets of edges $$$S$$$ that satisfy the given conditions.

Note that a tree is a connected, acyclic, undirected graph, where each undirected edge is an unordered pair of vertices.

Input

The first line contains three space-separated integers, $$$N$$$, $$$A$$$, $$$B$$$.

The $$$i$$$-th of the following $$$N-1$$$ lines contains two space-separated integers $$$x_i$$$ and $$$y_i$$$, denoting that the $$$i$$$-th edge connects vertices $$$x_i$$$ and $$$y_i$$$ in the tree.

Output

Print the number of possible sets $$$S$$$ that satisfy the conditions given in the problem, modulo $$$10^9+7$$$.

Scoring
  • $$$1 \le N \le 100\,000$$$
  • $$$1 \le A \lt B \le 500$$$
  • $$$1 \le x_i \lt y_i \le N$$$ ($$$1 \le i \le N-1$$$)
  • It is guaranteed that the given edges form a tree.
Example
Input
6 1 2
1 2
2 3
2 4
4 5
4 6
Output
10