P9414 "NnOI R1-T3" Tuples

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

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

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 one integer, the required answer.

**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