争分夺秒
题号:NC208695
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

七夕节到了,牛牛要去找牛妹约会了。

牛牛知道自己如果空手去约会,绝对会遭到牛妹的无情殴打。所以他决定打电话找跑腿,让跑腿去买花送到牛妹家楼下,牛牛要在牛妹下楼前到牛妹家楼下并且拿到花才不会遭到牛妹的无情殴打。

现在把整个城市看作一棵n个结点的树,牛妹在点1,牛牛家在点a,花店在点b,跑腿的起始点在c,牛牛在出发前会给牛妹打电话,问牛妹还有多久下楼。

为了让自己能够安然的度过今天,牛牛模拟了q个场景,想要计算一下自己能够不遭牛妹殴打的概率。

如果牛牛刚到牛妹家楼下,或者刚拿到花,这个时候牛妹刚好下楼,牛妹仍然会殴打牛牛。

输入描述:

第一行有两个正整数n(n<=200000),表示有n个结点

接下来n-1行每行有两个正整数u,v(u,v<=n)表示u,v两个结点有一条边

第n+1行有一个q(q<=200000),表示牛牛会给牛妹打q次电话

接下来q行,每行有四个正整数a,b,c,t(a,b,c<=n,t<=200000)a,b,c如题意描述,t为牛妹下楼的时间

输出描述:

输出p/q mod 1e9+7,表示牛牛不会被牛妹殴打的概率。

示例1

输入

复制
4
1 2
1 3
3 4
2
2 3 4 1
2 4 3 4

输出

复制
500000004