题目描述

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

输入

第一行两个整数分别代表$N$和$Q$。 接下来$N-1$行，每行两个整数$u,v$代表树中的一条边。 接下来$Q$行，每行两个整数代表询问的$u,v$。

输出

一共$Q$行, 每行一个整数代表答案。

输入样例

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

输出样例

9
5

提示

【数据规模】 对于20%的数据，$N≤10$。 对于40%的数据，$N≤1000$。 另有20%的数据，保证给定的树是一条链。 对于100%的数据，$N≤100000, Q≤100000$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。