定义无根满二叉树上某个点 $u$ 的层级为：$u$ 到 $u$ 子树中距离最远的点的距离。特别地，叶子节点的层级为 $0$，根节点的层级为树高 $H$。

对于每一个节点 $u$，记如下状态：

• $f(u)$ 表示 $u$ 的子树被划分为若干个无根满二叉树的方案数。
• $g_u(+i)$ 表示 $u$ 的层级为 $i$，$u$ 和 $fa_u$ 被划分在同一满二叉树中，且 $fa_u$ 比 $u$ 更靠近他们所在的满二叉树的根时，$u$ 子树内部划分的方案数。
• $g_u(-i)$ 表示 $u$ 的层级为 $i$，$u$ 和 $fa_u$ 被划分在同一满二叉树中，且 $u$ 比 $fa_u$ 更靠近他们所在的满二叉树的根时，$u$ 子树内部划分的方案数。

转移不难。注意到 $i$ 的定义域为 $0\le i\le \lceil\log n\rceil$，状态数为 $\mathcal{O}(n\log n)$ 级别，可以通过。

---

下面给出转移的具体过程。

对于 $g_u(+k)$ 的转移，当 $k=0$ 时显然有

$$g_u(+0)=\prod_{v\in \mathrm{son}_u} f(v)$$

当 $k\neq 0$ 时显然有

$$g_u(+k)=\sum_{x,y\in \mathrm{son_u},x<y}g_x(+(k-1))g_y(+(k-1))\prod_{v\neq x,v\neq y}f_v$$

对于 $g_u(-k)$ 的转移，有 $k\neq 0$。将 $u$ 为中心的方案数与 $u$ 不为中心的方案数相加，可得

$$g_u(-k)=\sum_{x\in \text{son}_u}g_x(+(k-1))\prod_{v\neq x}f_v+\sum_{x,y\in \text{son}_u,x\neq y}g_x(-(k+1))g_y(+(k-1))\prod_{v\neq x,v\neq y}f_v$$

对于 $f(u)$ 的转移，分以下情况讨论：$u$ 是中心；$u$ 是叶子，但不是中心；$u$ 既不是叶子也不是中心。 不难发现，此处 $u$ 是中心的转移和 $g_u(\cdot)$ 形式完全相同，大大简化了转移式。直接将几种情况分别相加，可以得到下面的转移：

$$\begin{aligned}&f(u)=\sum_{k\ge 0} g_u(+k)+\sum_{x\in \mathrm{son}_u}g_x(-1)\prod_{v\neq x}f(v)\\&+\sum_{k\ge 1}\sum_{x,y,z\in \text{son}_u,x\neq y,x\neq z,y<z} g_x(-(k+1))g_y(+(k-1))g_z(+(k-1))\prod_{v\neq x,v\neq y,v\neq z}f(v)\end{aligned}$$

实现细节：上述转移中复杂的求和式不需要直接枚举儿子二元组或三元组，而是可以用一个简单的线性 DP 解决，这里不再赘述。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F(i, a, b) for (int i = (a); i <= (b); i ++ )
#define DF(i, a, b) for (int i = (a); i >= (b); i -- )
inline void chkmin(int& a, int b) { if (a > b) a = b; }
inline void chkmax(int& a, int b) { if (a < b) a = b; }

const int N = 200010, M = 2 * N, mod = 1e9 + 7;

int n, h[N], e[M], ne[M], idx;
int f[N], gplus[N][25], gminus[N][25];
int tmp[N][25][2][3], tmp2[N][2], cnt;

inline void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u, int father)
{
	gplus[u][0] = 1;
	for (int i = h[u]; ~i; i = ne[i])
	{
		int j = e[i];
		if (j == father) continue;
		dfs(j, u);
	}
	F(id, 0, cnt) F(k, 0, 19) F(i, 0, 1) F(j, 0, 2)
		tmp[id][k][i][j] = id == 0 && i == 0 && j == 0;
	F(id, 0, cnt) F(i, 0, 1) tmp2[id][i] = id == 0 && i == 0;
	cnt = 0;
	for (int i = h[u]; ~i; i = ne[i])
	{
		int j = e[i];
		if (j == father) continue;
		gplus[u][0] = gplus[u][0] * f[j] % mod;
		cnt ++ ;
		F(k, 1, 19) F(x, 0, 1) F(y, 0, 2)
		{
			tmp[cnt][k][x][y] = tmp[cnt - 1][k][x][y] * f[j] % mod;
			if (x > 0) (tmp[cnt][k][x][y] += tmp[cnt - 1][k][x - 1][y] * gminus[j][k + 1]) %= mod;
			if (y > 0) (tmp[cnt][k][x][y] += tmp[cnt - 1][k][x][y - 1] * gplus[j][k - 1]) %= mod;
		}
		F(x, 0, 1)
		{
			tmp2[cnt][x] = tmp2[cnt - 1][x] * f[j] % mod;
			if (x > 0) (tmp2[cnt][x] += tmp2[cnt - 1][x - 1] * gminus[j][1]) %= mod;
		}
	}
	F(k, 1, 19) gplus[u][k] = tmp[cnt][k][0][2], gminus[u][k] = (tmp[cnt][k][0][1] + tmp[cnt][k][1][1]) % mod;
	F(k, 0, 19) (f[u] += gplus[u][k]) %= mod;
	(f[u] += tmp2[cnt][1]) %= mod;
	F(k, 1, 19) (f[u] += tmp[cnt][k][1][2]) %= mod;
}

void solve()
{
	cin >> n;
	F(i, 1, n) h[i] = -1, f[i] = 0;
	F(i, 1, n) F(j, 0, 19) gplus[i][j] = gminus[i][j] = 0;
	idx = 0;
	F(i, 2, n)
	{
		int a, b; cin >> a >> b;
		add(a, b), add(b, a);
	}
	dfs(1, -1);
	cout << f[1] << "\n";
}

signed main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T; cin >> T; 
	while (T -- ) solve();
	return 0;
}