seuOJ195 - 引爆炸弹

题目描述

众所周知，《Besiege》是一款中世纪攻城游戏。由于非常的硬核，许多技术不佳又脑洞太大的同学常常被人吐槽，大神玩的是《围攻》，自己玩的是《围观》。

炸弹是《Besiege》中威力最强的武器，但是炸弹的触发却是一个概率事件。小 Q 在《公爵的堡垒》一关中，在 nn 个不同地点各设置了一颗炸弹，其中第 ii 颗炸弹自发爆炸的概率是 PiP_i。

为了提高一部分炸弹爆炸的概率，小 Q 决定给每颗炸弹加上一根导火索，指向第 TOiTO_i 颗炸弹。也就是说当第 ii 颗炸弹爆炸时，会有 QiQ_i 的概率引燃导火索，将第 TOiTO_i 颗炸弹引爆。

分别求最终每一颗炸弹爆炸的概率。

输入格式

第一行一个整数 n(2≤n≤105)n(2 \leq n \leq 10^5) 表示有炸弹数目。

接下来 nn 行，每行两个整数 xi, yi(1≤xi<yi≤108)x_i,\ y_i(1 \leq x_i < y_i \leq 10^8)，表示 Pi=xiyiP_i = \frac{x_i}{y_i}。

接下来一行 nn 个正整数 TOi(1≤TOi≤n，TOi≠i)TO_i(1 \leq TO_i \leq n，TO_i \neq i)，表示第i颗炸弹爆炸时有可能触发第 TOiTO_i 颗炸弹。

接下来 nn 行，每行两个整数 ai, bi(1≤ai<bi≤108)a_i,\ b_i(1 \leq a_i < b_i \leq 10^8)，表示 Qi=xiyiQ_i = \frac{x_i}{y_i}。

输出格式

共一行，包含 nn 个整数。

其中第 ii 个数表示第 ii 颗炸弹最终爆炸的概率。

为防止精度误差，请将答案对 109+710^9+7 取模。也就是说如果答案的最简分数形式为 XY\frac{X}Y，请输出一个整数 pp，要求满足 0≤p<109+70 \leq p < 10^9+7，且 pY≡X(mod 109+7)pY ≡ X (mod\ 10^9+7)。

样例

样例输入1

3
1 2
1 2
1 2
2 3 1
1 2
1 2
1 2

样例输出1

906250007 906250007 906250007

样例输入2

2
1 2
1 2
2 1
1 3
2 3

样例输出2

666666672 583333338

样例解释2

第一颗炸弹自发爆炸的概率是 12\frac12，没爆炸但被第二颗触发的概率是 12×12×23\frac12 \times \frac12 \times \frac23。

所以，第一颗炸弹爆炸的概率是 12+12×12×23=23\frac12 + \frac12 \times \frac12 \times \frac23 = \frac23。

第二颗炸弹爆炸的概率是 12+12×12×13=712\frac12 + \frac12 \times \frac12 \times \frac13 = \frac7{12}。