「NnOI R1-T3」元组

小 L 很喜欢树，很喜欢 $ \operatorname{LCA} $，很喜欢有序元组，于是有了这样一道题。

对于一棵 $ n $ 点有根树（根为 $ 1 $），定义有序 $ p $ 元组 $ (a_1,a_2,......,a_p) $ 为 $ k $ 级 $ \operatorname{LCA} $ $ p $ 元组当且仅当： * $ 1 \le a_1<a_2<......<a_p \le n $ * 存在 $ x $ 使得对于任意有序严格递增 $ k $ 元组 $ b \subseteq a $ 均满足 $ \operatorname{LCA}_{i=1}^{k}\{b_i\} = x $。 注意，$ \operatorname{LCA}(x,y) $ 指树上 $ x $ 点和 $ y $ 点的最近公共祖先，且 $ \operatorname{LCA}_{i=1}^{k}\{b_i\} $ 指的是所有的 $ b_i $ 的 $ \operatorname{LCA} $。 求出 $ k $ 级 $ \operatorname{LCA} $ $ p $ 元组的个数，对 $ 10^9+7 $ 取模。

第一行一个整数 $ n,p,k $。 接下来 $ n-1 $ 行，每行两个整数代表一条边的两个端点的编号。

输出一个整数代表要求的答案。

6 4 3
1 2
2 3
3 4
3 5
3 6

1

6 3 2
1 2
1 3
1 4
1 5
1 6

20

6 4 2
1 2
1 3
2 4
2 5
3 6

0

### 样例解释 对于样例 $ 1 $，我们发现符合要求的 $ 4 $ 元组只有 $ (3,4,5,6) $。 ### 数据范围 对于 $ 100\% $ 的数据，$ 2 \le n \le 5000 $，$ 2 \le k \le p \le n $。 **提示：本题开启捆绑测试。** 本题共 $ 5 $ 个子任务。 | 子任务编号 | $ n \le $ | 特殊性质 | 分数 | |:-:|:-:|:-:|:-:| | $ 1 $ | $ 10 $ | 无 | 10 | | $ 2 $ | $ 20 $ | 无 | 20 | | $ 3 $ | $ 500 $ | 无 | 30 | | $ 4 $ | $ 5000 $ | $ 1 $ 和所有点存在连边 | 10 | | $ 5 $ | $ 5000 $ | 无 | 30 | ### 题目来源 | 项目 | 人员 | |:-:|:-:| | idea | Kevin0501 | | std | Kevin0501 | | data | EstasTonne | | check | EstasTonne | | solution | Kevin0501 |