Background

Little L really likes trees, really likes $\operatorname{LCA}$, and really likes ordered tuples, so this problem was created.

Problem Description

For a rooted tree with $n$ nodes (the root is $1$), define a strictly increasing ordered $p$-tuple $(a_1,a_2,\ldots,a_p)$ to be a level-$k$ $\operatorname{LCA}$ $p$-tuple if and only if:

• $1 \le a_1 < a_2 < \ldots < a_p \le n$.
• There exists a node $x$ such that for any strictly increasing ordered $k$-tuple $b \subseteq a$, we have $\operatorname{LCA}_{i=1}^{k}\{b_i\} = x$.

Note that $\operatorname{LCA}(x,y)$ means the lowest common ancestor of nodes $x$ and $y$ in the tree, and $\operatorname{LCA}_{i=1}^{k}\{b_i\}$ means the $\operatorname{LCA}$ of all $b_i$.

Find the number of level-$k$ $\operatorname{LCA}$ $p$-tuples, modulo $10^9+7$.

Input Format

The first line contains three integers $n,p,k$.

The next $n-1$ lines each contain two integers, representing the endpoints of an edge.

Output Format

Output one integer, the required answer.

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

Hint

Sample 1 Explanation

For sample $1$, we find that the only valid $4$-tuple is $(3,4,5,6)$.

Constraints

For $100\%$ of the testdata, $2 \le n \le 5000$, and $2 \le k \le p \le n$.

Note: This problem uses bundled testcases.

• Subtask 1 (10 pts): $n \le 10$.
• Subtask 2 (20 pts): $n \le 20$.
• Subtask 3 (30 pts): $n \le 500$.
• Subtask 4 (10 pts): Node $1$ has a direct edge to every node.
• Subtask 5 (30 pts): No special restrictions.

Contributors

data&check: EstasTonne. (The problem setter of the next problem number under this problem in the problemset.)

Translated by ChatGPT 5