题目描述

战争胜利了，但敌人的余党依旧在活动。为了防范敌人的入侵，指挥官派你在接下来的 $t$ 天内在边境侦察。

边境可以看作一棵 $n$ 个点的无向树。令 $\mathrm{dist}(x,y)$ 表示 $x,y$ 两点在树上的最短路长度。称树上一条路径是简单的，当且仅当不存在一个点在路径上出现超过一次。

第 1 天开始前，你熟悉了地形，并可以任意选择一个点作为终点停下来休息。而接下来的每一天，你从上一天的终点出发，选择一条最长的简单路径并沿着这条路径侦察，在终点处停下休息。若有多条路径同时满足条件，你可以任意选择其中一条。

现在你需要求出，在这 $t$ 天中，你究竟有多少种侦察方案。

形式化地说，你需要求出有多少长度为 $t+1$ 的顶点序列 $a_0, a_1, \dots, a_t$，满足：

• 对所有 $1 \le i \le t$，不存在任意点 $x$ 使得
  $\mathrm{dist}(a_{i-1}, x) > \mathrm{dist}(a_{i-1}, a_i)$。

答案可能会很大，只需输出对 $10^9 + 7$ 取模后的结果。

输入格式

本题采用多组测试。

第一行两个非负整数 tid, T，分别表示测试点编号和数据组数。特别地，在样例中 tid = 0。

对于每组数据：

• 第一行两个正整数 $n, t$。
• 接下来 $n-1$ 行，每行两个正整数 $u_i, v_i$，表示树的一条无向边。

每组数据间用一个空行隔开。

输出格式

共 $T$ 行，每行一个整数，表示一组数据的答案。

0 4

5 2
1 2
2 5
3 1
3 4

5 5
1 2
1 3
2 4
2 5

6 3
2 1
2 3
3 4
2 5
1 6

8 4
6 8
3 7
4 1
5 7
3 6
1 6
2 7

6
28
8
32

样例解释

样例 1（第一组数据）中，所有可能的序列为：

• $\{1, 4, 5\}$，$\{1, 5, 4\}$，$\{2, 4, 5\}$，$\{3, 5, 4\}$，$\{4, 5, 4\}$，$\{5, 4, 5\}$。

因此答案为 $6$。

数据范围与提示

• 对所有数据：$1 \le T \le 4$，$1 \le n \le 2500$，$1 \le t \le 10^{18}$，$1 \le u_i, v_i \le n$，且 $u_i \ne v_i$。

测试点与特殊性质

• 特殊性质 A：$u_i=i,\ v_i=i+1$。
• 特殊性质 B：$u_i=1,\ v_i=i+1$。