Problem Description

You have a rooted tree with $n$ nodes where the root node is $1$. You need to prune this tree. Each time, you can choose an unpruned node $u$ and remove all nodes in the subtree of $u$ (including $u$). The operation stops if and only if node $1$ is pruned.

You know that the path from $1$ to $x$ is the stem of the tree and requires special handling. Therefore, you need to operate on node $x$ at the $k$-th pruning, rather than just pruning it. This means you cannot prune any ancestor of $x$ before the $k$-th pruning to avoid it being pruned indirectly.

Determine the number of different operation sequences. Two sequences are considered different if they have different lengths or if there exists an operation $i$ where the chosen node $u$ at the $i$-th operation is different. Output the answer modulo $10^9+7$.

Input Format

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

Output Format

Output a single number representing the answer modulo $10^9+7$.

Sample Input and Output

Sample Input #1

3 2 2
1 2
1 3

Sample Output #1

1

Sample Input #2

5 2 4
1 2
1 3
2 4
2 5

Sample Output #2

9

Sample Input #3

5 1 4
1 2
1 3
2 4
2 5

Sample Output #3

12

Notes/Hints

Sample Explanation

For Sample $1$, there is only one way to satisfy the condition: first prune node $3$, then node $2$, and finally node $1$.

For Sample $2$, the sequences that satisfy the condition 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\}$.

Data Constraints

This problem uses batched testing.

Special Condition $\text A$: Guarantees $k=1$.\
Special Condition $\text B$: Guarantees $x=1$.\
Special Condition $\text C$: Guarantees $\forall i\in[1,n-1], i$ and $i+1$ are connected by an edge.

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

见题面 Input 部分

见题面 Output 部分