2564: #6172. Samjia 和大树

Peter送给Samjia一颗大小为 $n$ 的树， 节点编号从 $1$ 到 $n$ 。
Samjia要给树上的每一个节点赋一个 $[1,m]$ 之间的权值， 并使得有边直接相连的两个节点的权值之差的绝对值 $\ge k$ 。
请你告诉Samjia有多少种不同的赋值方案。
只用求出答案对 109+7(1000000007)10^9+7(1000000007)10​9​​+7(1000000007) 取模得到的结果。

输入格式

输入数据的第一行包含一个整数 $T$ , 代表测试数据组数。
接下来是 $T$ 组数据。
每组数据的第一行包含三个整数 $n$ , $m$ 和 $k$ 。
接下来 $n-1$ 行,每行包含两个整数 $u$ 和 $v$ ，代表节点 $u$ 和 $v$ 之间有一条树边。

输出格式

对于每组数据， 输出一行， 包含一个整数， 代表所求的答案。

样例

样例输入

3
2 2 0
1 2
3 3 2
1 3
1 2
3 3 1
1 2
2 3

样例输出

4
2
12

数据范围与提示

对于所有数据，T≤10,n≤100,k≤100,m≤109 T \leq 10, n \leq 100, k \leq 100, m\leq 10^9T≤10,n≤100,k≤100,m≤10​9​​

测试点编号	$m\le$	特殊约定
1,2	100	无
3,4	10000	无
5,6	10910^910​9​​	第 $2-n$ 号节点与 $1$ 号节点直接相连
7,8	10910^910​9​​	第 $i$ 号节点与第 $i+1$ 号节点直接相连
9,10	10910^910​9​​	无