T467185 树上染色

白云有一棵 $n$ 个点的树。白云想给树的每个结点染一个$[1,m]$ 的颜色。 白兔给了白云一个要求：同色点对距离最小值恰好为 $k$。即$\min\{\operatorname{dis}(x,y)~|~[x \neq y \ and \ col[x]=col[y]]\}=k$。如果不存在同色点对就当做 $0$。 白云想知道有多少种合法的染色方案。

第一行三个整数 $n,m,k$。 接下来 $n-1$ 行，每行两个数描述这棵树。

输出一个整数表示答案。对$10^9+7$取模。

- 对于 $30\%$ 的数据，$n \le 5$。 - 对于 $60\%$ 的数据，$n \le 5000$。 - 对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le m \le 10^9$，$0 \le k < n$。