#6172. Samjia 和大树
题目描述
Peter送给Samjia一颗大小为 nnn 的树， 节点编号从 111 到 nnn 。
Samjia要给树上的每一个节点赋一个 [1,m][1,m][1,m] 之间的权值， 并使得有边直接相连的两个节点的权值之差的绝对值 ≥k\geq k≥k 。
请你告诉Samjia有多少种不同的赋值方案。
只用求出答案对 109+7(1000000007)10^9+7(1000000007)109+7(1000000007) 取模得到的结果。
输入格式
输入数据的第一行包含一个整数 TTT , 代表测试数据组数。
接下来是 TTT 组数据。
每组数据的第一行包含三个整数 nnn , mmm 和 kkk 。
接下来 n−1 行,每行包含两个整数 uuu 和 vvv ，代表节点 uuu 和 vvv 之间有一条树边。
输出格式
对于每组数据， 输出一行， 包含一个整数， 代表所求的答案。
样例
样例输入
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≤109
| 测试点编号 | m≤m \leq m≤ | 特殊约定 |
|---|---|---|
| 1,2 | 100 | 无 |
| 3,4 | 10000 | 无 |
| 5,6 | 10910^9109 | 第 2−n2-n2−n 号节点与 111 号节点直接相连 |
| 7,8 | 10910^9109 | 第 iii 号节点与第 i+1i+1i+1 号节点直接相连 |
| 9,10 | 10910^9109 | 无 |