Simple Tree Decomposition Problem

Interview

Time limit3sMemory limit1024 MB

Summary

Count the edge subsets of a tree whose removal leaves every connected component with exactly A or B vertices, modulo 10^9+7.

Level: Medium6 of 10
Topics: Tree, Dynamic programming
Solved: No attempts yet

Problem

BOOM! Dohoon's head exploded while he was solving the tree decomposition practice problem assigned at the Summer School on Combinatorics and Algorithms at KAIST. His brain could no longer focus on the problem, so it started idling by decomposing a tree instead of doing tree decomposition on general graphs.

Dohoon is given a tree with $N$ vertices. He decomposes the tree into a collection of connected components as follows.

He selects zero or more edges from the tree and removes them. Let $S$ be the set of removed edges.
After the edges in $S$ are removed, each connected component must have either $A$ or $B$ vertices.

Count the number of possible sets of edges $S$ that satisfy these conditions.

Input

The first line contains three integers $N$ , $A$ , $B$ , separated by spaces. Each of the following $N-1$ lines contains two integers $x_i$ and $y_i$ , separated by a space, meaning that the $i$ -th edge connects vertices $x_i$ and $y_i$ .

Output

Print the number of possible sets $S$ modulo $10^9+7$ .

Constraints

$1 \le N \le 100\,000$

$1 \le A < B \le 500$

$1 \le x_i < y_i \le N$ ( $1 \le i \le N-1$ )

The given edges form a tree.

Examples1

Example 1
Input
```
6 1 2
1 2
2 3
2 4
4 5
4 6
```
Expected output
```
10
```