题目描述

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$。