题目描述

梦游中的你来到了一棵 $\red{N }$个节点的树上. 你一共做了 $\red{Q }$个梦, 每个梦需要你从点 $\red{u }$走到 点 $\red{v }$之后才能苏醒, 由于你正在梦游, 所以每到一个节点后,你会在它连出去的边中等 概率地 选择一条走过去, 为了确保第二天能够准时到校, 你要求出每个梦期望经过多少条边才能苏醒。为了避免精度误差, 你要输出答案模$\red{10^9 + 7}$的结果。

输入格式

第一行两个整数分别代表 $\red{N }$和 $\red{Q}$。

接下来 $\red{N-1 }$行, 每行两个整数 $\red{u, v }$代表树中的一条边。

接下来 $\red{Q }$行, 每行两个整数代表询问的 $\red{u,v}$。

输出格式

一共 $\red{Q }$行, 每行一个整数代表答案

样例

输入样例

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

输出样例

9
5

提示

数据范围

对于 $\red{20\%}$的数据, $\red{N <= 10.}$

对于 $\red{40\%}$的数据, $\red{N <= 1000.}$

另有 $\red{20\%}$的数据, 保证给定的树是一条链.

对于 $\red{100\%}$的数据, $\red{N <= 100000, Q <= 100000. }$

如果你求出的答案为$\red{\frac{P}{Q}(P,Q}$互质$\red{}$)，那么你需要输出$\red{P\times Q^{10^9+5}}$