Ant

有一棵 $n$ 个节点的石榴树，点的下标为 $1 \ldots n$，下标为 $m$ 的节点上有一颗石榴。石榴树有 $2n-2$ 条有向边，每条有向边都连接两个不同的节点，不存在完全相同的两条有向边，且如果从节点 $a$ 到节点 $b$ 的有向边存在，反过来从节点 $b$ 到节点 $a$ 的有向边也必定存在。从任意一个节点都能（经过这些有向边中的若干条）到达任意一个其它节点。

现在有两只小蚂蚁去找石榴。

两只小蚂蚁都从 $1$ 号点出发，第一只蚂蚁先走。它每次会从它当前所在的节点出发的没有走过的有向边中等概率地选择一条走（注意从 $a$ 到 $b$ 和从 $b$ 到 $a$ 是两条不同的有向边），并且在这条有向边上留下信息素。如果蚂蚁找到了石榴，或者无路可走了，它就会停下来。

第一只蚂蚁停下来以后第二只蚂蚁走，它每次从它当前所在的节点出发的有第一只蚂蚁留下的信息素且自己没走过的有向边中等概率地选择一条走。如果第二只蚂蚁找到了石榴，或者它无路可走了，它就会停下来。

如果第二只蚂蚁沿着从 $1$ 到 $m$ 的最短路找到了石榴，就说它成功了。请问对于第一只蚂蚁，使得第二只蚂蚁成功率大于等于 $1/2$ 的概率是多少？

第一行一个正整数 $test~(1 \leq test \leq 100)$ 表示数据组数。

对于每组数据，第一行两个正整数 $n，m~(1 \leq n \leq 100000, 1 \leq m \leq n)$ 分别表示点数和石榴在哪里。

接下来 $n-1$ 行描述 $2n-2$ 条有向边，每行两个整数 $x，y$ 代表从 $x$ 到 $y$ 和从 $y$ 到 $x$ 各有一条有向边。

数据保证读入是一棵合法的石榴树，数据保证树是这样随机生成的：

```
for (int i = 1; i <= n; i++)
a[i] = i;
random_shuffle(a + 1, a + n + 1);
for (int i = 2; i <= n; i++)
连接编号为 a[i] 和 a[j] 的点，其中 j 为 {1, ..., i-1} 中一个随机的整数。每次随机相互独立。
```
（实际上每次随机使用了C++自带的随机函数。）

对于每组数据，一行一个数表示答案。由于答案 $A/B$ 中的 $AB$ 可能很大，请输出 $A/B\bmod{(10^9+7)}$。假设 $A/B$ 为最简分数，$A/B\bmod{(10^9+7)} = A \times B^{-1}\bmod{(10^9+7)}$，$B^{-1}$ 为满足 $B^{-1}\times B\bmod{(10^9+7)}=1$ 的整数。

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

1
666666672
416666670

2020 年百度之星·程序设计大赛 - 初赛三