Background

Little L loves trees, the lowest common ancestor (LCA), and ordered tuples, which inspired this problem.

Problem Description

For a rooted tree with \( n \) nodes (rooted at 1), an ordered \( p \)-tuple \((a_1, a_2, \ldots, a_p)\) is defined as a \( k \)-level LCA \( p \)-tuple if and only if:

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

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

Calculate the number of \( k \)-level 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 a single integer representing the answer.

Sample Input and Output

Sample Input #1

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

Sample Output #1

1

Sample Input #2

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

Sample Output #2

20

Sample Input #3

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

Sample Output #3

0

Notes

Sample Explanation

For Sample 1, the only valid 4-tuple is \( (3, 4, 5, 6) \).

Data Range

For \( 100\% \) of the data, \( 2 \le n \le 5000 \), \( 2 \le k \le p \le n \).

Hint: This problem has subtasks.

There are 5 subtasks in total.

Problem Source

见题面 Input 部分

见题面 Output 部分