题目描述

你有一棵 $n$ 个点的根节点为 $1$ 的有根树，现在你要对这棵树进行剪枝，每次你可以选择一个还未被剪掉的节点 $u$ 进行操作，然后剪掉 $u$ 的子树所有点（包括 $u$）。当且仅当你剪掉 $1$ 时，操作停止。

你知道 $1$ 到 $x$ 这条路径是这棵树的茎，需要特殊处理。所以你需要在第 $k$ 次剪枝时对 $x$ 进行操作，而非仅仅将其剪掉，即你不能在第 $k$ 次及以前对其祖先进行操作使其被连带剪掉。

求有多少种不同的操作序列，两个操作序列不同当且仅当长度不同或存在一次操作 $i$ 使得两操作序列在第 $i$ 次时选择的 $u$ 不同。输出答案模 $10^9+7$。

输入格式

第一行三个数 $n,k,x$。
接下来 $n-1$ 行每行两个数 $u,v$，代表树上的一条边 $(u,v)$。

输出格式

一个数表示答案对 $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

提示

样例解释

对于样例 $1$，只有一种操作方法满足条件，第一次操作 $3$，第二次操作 $2$，第三次操作 $1$。

对于样例 $2$，满足条件的操作序列：$\{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\}$。

数据规模

本题采用捆绑测试。

特殊性质 $\text A$：保证 $k=1$。
特殊性质 $\text B$：保证 $x=1$。
特殊性质 $\text C$：保证 $\forall i\in[1,n-1],i$ 与 $i+1$ 有边。

对于 $100\%$ 的数据，$1\le k,x\le n\le 500$。