题目思路

本题难度较大，需要一定的图论基础。没有了解过LCA和逆元的可以先去学习一下。

树上任意两个点的路径其实是唯一的，所以到达的概率需要通过数个可供选择的邻居数量的倒数相乘，设$cnt_i$是节点$i$的邻居数量，由于概率需要取模，所以我们应用快速幂求乘法逆元得到概率取模后的值。

这里简单介绍一下逆元的知识，假设x * y % mod == 1，那么我们就称y是x的逆元，所以我们其实就是求类似于$cnt_i$的逆元。

首先考虑简单的情况，对于两个点$u,v$，如果它们在树上是祖先-子孙关系，那么通过dfs枚举到子孙v时，我们可以统计从根结点（这个可以自己定，这里我们定为0）到v这条路径上所有节点的$1/(cnt_i-1)$的累乘值： 比如对于1-2-3来说，这在树上是一条链，那么1记录的就是$1/(cnt_1-1)$，2记录的就是$1/(cnt_1-1) * 1/(cnt_2-1)$，我们将这个值保存在path中。

题目描述

小美在树上迷路了，位于$s$节点，但他想去$t$节点。小美很精明，他每次都会选一条之前没有走过的路走，他想知道，他走到$t$的概率是多少？

包含多次询问，每次输出概率对$10^9+7$取余后的结果。可以证明$x$是唯一的。

如果最后答案为分数，则最简分式后的形式为$\frac{a}{b}$，其中$a,b$互质。那么输出整数$x$使$b*x\equiv a(mod10^9+7)$且$0\le x\lt 10^9+7$。

输入描述

第一行输入一个整数$n(\le 2*10^5)$表示树节点个数。

接下来$n-1$行，每行为$u,v$ ,表示树上的边。

接下来一行，输入一个整数$q(\le 2*10^5)$，代表询问次数。

接下来$q$行，每行为$s,t$表示询问。

输出描述

输出$q$行，每行输出一个整数表示概率

样例

输入

3
1 2
1 3
2 
2 3
1 3

输出

1
500000004

说明

第一个询问，有1的概率从节点2走到节点1，然后有1的概率从节点1走到节点3。因此答案为$1mod10^9+7=1$

第二个询问，有1/2的概率从节点1走到节点2，有1/2的概率从节点1走到节点3。答案为1/2，按公式取余后结果为500000004