#P18838. [Croatian CPC2020] Ekstremna Ekspedicija

[Croatian CPC2020] Ekstremna Ekspedicija

[Croatian CPC2020] Ekstremna Ekspedicija

题目描述

有一棵包含 nn 个节点的无向树,节点编号为 11 至 nn,每条边的通行时间均为一分钟。

Kile 计划进行 qq 次旅行。第 ii 次旅行从节点 aia_i 开始,在第一次到达节点 bib_i 时结束。

每当 Kile 位于某个节点时,他都会从与该节点相连的所有边中等概率随机选择一条,沿该边走到相邻节点;允许立即沿刚刚经过的边返回。

对于每次旅行,求它的期望持续时间。

为避免精度问题,将期望写成最简分数 P/RP/R,你需要输出 P⋅R−1 mod (109+7)P\cdot R^{-1}\bmod(10^9+7),其中 R−1R^{-1} 表示 RR 在模 109+710^9+7 意义下的乘法逆元。

输入格式

第一行包含两个整数 n,qn,q(2≤n≤3×1052\le n\le3\times10^5,1≤q≤3×1051\le q\le3\times10^5)。

接下来 n−1n-1 行,每行包含两个整数 ui,viu_i,v_i(1≤ui,vi≤n1\le u_i,v_i\le n),表示一条无向边。保证这些边构成一棵树。

接下来 qq 行,第 ii 行包含两个不同的整数 ai,bia_i,b_i(1≤ai,bi≤n1\le a_i,b_i\le n),表示第 ii 次旅行的起点和终点。

输出格式

输出 qq 行,第 ii 行包含一个整数,表示第 ii 次旅行的期望持续时间按上述方式取模后的结果。

样例 1

输入

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

输出

11
10
7

样例 2

输入

3 1
1 2
2 3
2 3

输出

3

样例 2 说明

从节点 22 出发,有一半概率用一步到达节点 33,另一半概率先到节点 11,再用一步回到节点 22 重新开始。最终期望时间为 33。