大样例下载

题目描述

某国有 $N$ 个城市，编号为 $1$ ~ $N$。这些城市通过 $N - 1$ 条道路连通起来，构成一棵树的结构。

现在要向每个城市派驻一定数量的士兵，要求：

• 每个城市至少派驻一名士兵，至多派驻 $M$ 名士兵；
• 任意两个相邻城市派驻的士兵数量之差不小于 $K$。（所谓相邻，是指两个城市之间有一条直接道路相连）

问：有多少种不同的派驻方案？输出答案 mod $(10^9+7)$。

两种派驻方案不同，当且仅当存在一个城市，在两种方案中派驻的士兵数量不同。

多组数据。

输入格式

第一行：一个整数 $T$, 表示数据组数。

对于每组数据：

• 第一行：三个整数 $N, M, K$ 。
• 接下来 $N-1$ 行：每行两个整数 $x$ 和 $y$ ，表示城市 $x$ 与 $y$ 是相邻的，即两个城市之间有一条道路。（$1 ≤ x, y ≤ N$）

输出格式

共 $T$ 行，每组数据的答案占一行。

样例输入

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

输出

4
2
12

数据范围与提示

100% 的数据：$T ≤ 10, N ≤ 100, M ≤ 10^9, K ≤ 100$。

其中：

• 有 20% 的数据：$M ≤ 100$;
• 另有 20% 的数据：$M ≤ 10^5$;
• 另有 20% 的数据：城市 $1$ 与其他所有城市相邻;
• 另有 20% 的数据：城市 $i$ 与城市 $i+1$ 相邻（$1 ≤ i < N$）。