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