Problem Description

noya 有一棵 $n$ 个点的以 $1$ 为根的树，由于一些原因，这棵树开始凋零。

具体来说，这棵树每天会等概率随机一个点，然后这个点的子树会全部脱落（即从树中将这棵子树删除）。

由于日久生情，noya 想知道这棵树期望多少天会完全凋零，也就是期望多少天这棵树会失去所有点。

由于 noya 是神，他心算得到了这棵树的期望凋零的天数，觉得小的可怕。于是他打算发动一次魔法，这次魔法会使得树上的每条边都独立的有 $0.5$ 的概率消失或保留。而对于一条消失的边，其连接的两个端点的子树关系就不存在了，这样树完全凋零所需的期望天数也会相应增加。

具体来说，魔法发动后的树变成了一个森林，森林中每棵树的根是在原树中深度最小的点。每天的凋谢仍然是在整个森林中等概率随机一个点，然后这个点在其所在的树中的子树会全部脱落。

现在，noya 还没有发动魔法，而他想知道如果发动魔法后整个森林凋零的期望天数，对 $10^9+7$ 取模后的结果。

Input

本题单个测试点内包含多组测试数据。

第一行一个正整数 $T\,\,(1\leq T\leq 10^5)$，表示数据组数。

对于每组数据，第一行两个正整数 $n\,\,(1\leq n\leq 10^5)$，分别表示 noya 的树的点数。

第 $2\sim n$ 行，每行两个正整数 $x,y\,\,(1\leq x,y\leq n,x\neq y)$，表示 noya 的树上存在一条连接点 $x,y$ 的边。

数据保证单个测试点内所有数据中 $n$ 的和不超过 $10^6$。

Output

对于每组数据输出一行一个正整数表示答案。

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

750000007
458333339
114583338