题目描述

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

输入格式

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

输出格式

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

样例

input

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

output

4
2
12

数据范围与提示

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