P8935 [JRKSJ R7] Stem

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$.

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 one integer, the answer modulo $10^9+7$.

### 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. |$\text{Subtask}$|$n\le$|Special Property|$\text{Score}$| |:-:|:-:|:-:|:-:| |$1$|$7$|None|$5$| |$2$|$17$|None|$10$| |$3$|$50$|$\text A$|$5$| |$4$|$50$|None|$15$| |$5$|$500$|$\text A$|$5$| |$6$|$500$|$\text B$|$5$| |$7$|$500$|$\text C$|$10$| |$8$|$500$|None|$45$| 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