1419: #6172. Samjia 和大树

Memory Limit:512 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

输入格式

输入数据的第一行包含一个整数 TTT , 代表测试数据组数。
接下来是 TTT 组数据。
每组数据的第一行包含三个整数 nnn , mmmkkk
接下来 n1 行,每行包含两个整数 uuuvvv ,代表节点 uuuvvv 之间有一条树边。

输出格式

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

样例

样例输入

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^9T10,n100,k100,m109

测试点编号 m≤m \leq m 特殊约定
1,2 100
3,4 10000
5,6 10910^9109 2−n2-n2n 号节点与 111 号节点直接相连
7,8 10910^9109 iii 号节点与第 i+1i+1i+1 号节点直接相连
9,10 10910^9109