Tommy’s Tree Infection Orderings

Tommy has a tree with n vertices numbered from 1 to n. Initially, only two vertices, a and b, are colored black, and all other vertices are white.

Tommy performs the following process until all vertices become red:

1. Choose any black vertex p and color it red.
2. Immediately, for every white neighbor of p, color that neighbor black.

As the process continues, each vertex will eventually be colored red. Let t_i be the step at which vertex i is colored red. The sequence t₁, t₂, …, t_n is a permutation of 1,2,…,n.

Your task is to count the number of different red‐ordering permutations that can result from Tommy’s process. If there is a unique simple path between a and b (say it has length d+1, so that d is the distance between them), then the red orders on the vertices along this path can occur in 2^d different ways. In addition, every vertex not on that path becomes infected from the first adjacent red vertex, and the orders in the subtrees attached to the path vertices can be interleaved arbitrarily subject to the constraint that a vertex is red only after the vertex that “infected” it.

This naturally leads to a recursive counting: for a rooted tree the number of valid orders is

$$f(r)=\left(|T_r|!\prod_{v\,\text{is a child of}\,r}\frac{f(v)}{|T_v|!}\right), $$

and for the forest induced by the two initial seeds and the unique simple path connecting them, the final answer is

$$\text{Answer}=2^{d}\prod_{p\,\in\,P} \left( \frac{(\sum_{c\in C(p)} |T_c|)!}{\prod_{c\in C(p)}\,(|T_c|)!} \prod_{c\in C(p)}f(c) \right) \pmod{10^9+7}, $$

where P is the unique path from a to b and for each vertex p on this path, C(p) is the set of subtrees attached to p (i.e. the adjacent vertices that are not on the path). In our input the tree is given and you are to compute the number of valid red‐orderings modulo 10^9+7.

inputFormat

The input begins with an integer n (the number of vertices) on the first line. The second line contains two distinct integers a and b indicating the two initially black vertices. Each of the following n-1 lines contains two integers u and v indicating that there is an edge between vertices u and v (the tree is connected).

Note: The vertices are numbered from 1 to n.

outputFormat

Output a single integer: the number of different red‐ordering permutations modulo 10^9+7.

sample

3
1 2
1 3
2 3

4