题目描述

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$ 之间有一条树边。

输出格式

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

样例

输入

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

输出

4
2
12

数据范围与提示

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