J9 实践-7 彩色圣诞树

题目描述

圣诞节快到了！埃迪收到了一棵圣诞树作为礼物。毫不奇怪，树由 $N$ 个顶点和 $N-1$ 条边组成，并神奇地保持连接。目前，树的所有顶点都是未着色的。$\text{Eddy}$ 想将每个顶点着色为 $K$ 色之一。然而，有太多的方法来给树着色（即 $K^N$ 方法）。埃迪不希望着色的结果太无聊。因此，他将树的颜色定义如下：树的颜色是同一颜色的两个顶点之间的最小距离。现在，埃迪想知道有多少种方法可以给树着色，使树的颜色为 $D$。

输入格式

第一行输入包含三个空格分隔的整数 $N$、$K$、$D$，表示顶点数、颜色数和所需的颜色。

对于后面的 $N-1$ 行，每行包含两个空格分隔的正整数 $u_i,v_i$ 表示 $u_i$ 和 $v_i$ 之间有一条边。

可以保证给定的输入是一棵树。

输出格式

输出一行包含一个整数，表示给树着色的方案数 $\bmod 1000000007$（ $10^9+7$），导致颜色为 $D$。

样例输入1

2 1 1
1 2

样例输出1

1

样例输入2

4 3 2
1 2
2 3
3 4

样例输出2

18

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$1 \le K < N \le 5000$，$1 \le D \le N$，$1 \le u_i < v_i \le N$。