Problem Description

You are given a rooted tree with $n$ nodes, where the root is node $1$. Now you want to prune this tree. Each time, you may choose a node $u$ that has not been pruned yet, and then prune all nodes in the subtree of $u$ (including $u$ itself). The process stops if and only if you prune node $1$.

You know that the path from $1$ to $x$ is the “stem” of this tree and needs special handling. Therefore, at the $k$-th pruning, you must perform the operation on $x$ (rather than just pruning it indirectly). In other words, you are not allowed, at the $k$-th pruning or any earlier pruning, to perform the operation on any ancestor of $x$ so that $x$ gets pruned together.

Compute how many different operation sequences there are. Two operation sequences are different if and only if their lengths are different, or there exists an operation $i$ such that the chosen $u$ at the $i$-th step is different. Output the answer modulo $10^9+7$.

Input Format

The first line contains three integers $n,k,x$. The next $n-1$ lines each contain two integers $u,v$, representing an edge $(u,v)$ in the tree.

Output Format

Output one integer, the answer modulo $10^9+7$.

3 2 2
1 2
1 3

1

5 2 4
1 2
1 3
2 4
2 5

9

5 1 4
1 2
1 3
2 4
2 5

12

Hint

Sample Explanation

For sample $1$, there is only one valid sequence of operations: the first operation chooses $3$, the second chooses $2$, and the third chooses $1$.

For sample $2$, the valid operation sequences are: $\{3,4,1\},\{3,4,2,1\},\{3,4,5,1\},\{3,4,5,2,1\},\\ \{5,4,1\},\{5,4,2,1\},\{5,4,2,3,1\},\{5,4,3,1\},\{5,4,3,2,1\}$.

Constraints

This problem uses bundled testdata.

Special property $\text A$: guaranteed that $k=1$.
Special property $\text B$: guaranteed that $x=1$.
Special property $\text C$: guaranteed that $\forall i\in[1,n-1],i$ has an edge with $i+1$.

For $100\%$ of the testdata, $1\le k,x\le n\le 500$.

Translated by ChatGPT 5