시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 1024 MB34262076.923%

문제

$N$개의 정점으로 이루어진 트리 $T_{N}$를 다음과 같은 방법으로 생성한다.

  • $T_{1}$은 1번 정점만으로 이루어진 트리다.
  • 2 이상의 $i$에 대해 $T_{i}$는 $T_{i-1}$에 $i$번 정점을 $T_{i-1}$의 정점 중 하나와 간선으로 이어 추가한 트리다. $i$번 정점과 연결된 정점이 $j$번 정점이 될 확률은 $\frac{a_j}{a_1+ \cdots + a_{i-1}}$이다. $i$번 정점과 연결된 정점이 $j$번 정점이라면 그 간선의 길이는 $c_i + c_j$이다.

$Q$개의 쿼리가 주어진다. 각 쿼리로 $u$와 $v$가 주어질 때마다 $T_{N}$에서 $u$번 정점과 $v$번 정점의 거리의 기댓값을 구하여라.

입력

첫 번째 줄에 $N$과 $Q$가 주어진다. $(2 \leq N,Q \leq 300\,000)$

두 번째 줄에 $N-1$개의 정수 $a_1,a_2, \cdots, a_{N-1}$이 공백으로 구분되어 주어진다. $(1 \leq a_i \leq 2\,000)$

세 번째 줄에 $N$개의 정수 $c_1,c_2, \cdots, c_N$이 공백으로 구분되어 주어진다. $(1 \leq c_i \leq 2\,000)$

이후 $Q$개의 줄에 걸쳐 쿼리들이 주어진다. 각 줄에는 $u$와 $v$가 공백으로 구분되어 주어진다. $(1 \leq u,v \leq N)$

출력

$i$번째 쿼리의 답을 $ans_i=\frac{p_i}{q_i}$라 하자. ($p_i$, $q_i$는 서로소인 음이 아닌 정수) $i$번째 줄에는 $p_i \equiv q_i x_i \pmod{10^9+7}$를 만족하는 $0$ 이상 $10^9+7$ 미만의 정수 $x_i$를 출력한다. 이 수는 유일하게 존재함을 증명할 수 있다.

예제 입력 1

5 7
1 1 1 1
1 2 4 8 16
1 3
2 5
4 3
1 5
3 3
4 5
1 2

예제 출력 1

7
666666697
15
666666697
0
333333366
3

예제 입력 2

5 4
17 19 23 29
2 3 5 7 11
1 2
3 4
5 2
3 5

예제 출력 2

5
927495315
106531441
450222593
W3sicHJvYmxlbV9pZCI6IjIwNTUyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhYzcwXHViOWFjXHVjNzU4IFx1YWUzMFx1YjMxM1x1YWMxMiIsImRlc2NyaXB0aW9uIjoiPHA+JE4kXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzgxMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVkMmI4XHViOWFjICRUX3tOfSRcdWI5N2MgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHVjMGRkXHVjMTMxXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiRUX3sxfSRcdWM3NDAgMVx1YmM4OCBcdWM4MTVcdWM4MTBcdWI5Y2NcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1ZDJiOFx1YjlhY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+MiBcdWM3NzRcdWMwYzFcdWM3NTggJGkkXHVjNWQwIFx1YjMwMFx1ZDU3NCZuYnNwOyRUX3tpfSRcdWIyOTQgJFRfe2ktMX0kXHVjNWQwICRpJFx1YmM4OCBcdWM4MTVcdWM4MTBcdWM3NDQgJFRfe2ktMX0kXHVjNzU4IFx1YzgxNVx1YzgxMCBcdWM5MTEgXHVkNTU4XHViMDk4XHVjNjQwIFx1YWMwNFx1YzEyMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWM1YjQgXHVjZDk0XHVhYzAwXHVkNTVjIFx1ZDJiOFx1YjlhY1x1YjJlNC4gJGkkXHViYzg4IFx1YzgxNVx1YzgxMFx1YWNmYyBcdWM1ZjBcdWFjYjBcdWI0MWMgXHVjODE1XHVjODEwXHVjNzc0ICRqJFx1YmM4OCBcdWM4MTVcdWM4MTBcdWM3NzQgXHViNDIwIFx1ZDY1NVx1Yjk2MFx1Yzc0MCAkXFxmcmFje2Ffan17YV8xKyBcXGNkb3RzICsgYV97aS0xfX0kXHVjNzc0XHViMmU0LiAkaSRcdWJjODggXHVjODE1XHVjODEwXHVhY2ZjIFx1YzVmMFx1YWNiMFx1YjQxYyBcdWM4MTVcdWM4MTBcdWM3NzQgJGokXHViYzg4IFx1YzgxNVx1YzgxMFx1Yzc3NFx1Yjc3Y1x1YmE3NCBcdWFkZjggXHVhYzA0XHVjMTIwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAkY19pICsgY19qJFx1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD4kUSRcdWFjMWNcdWM3NTggXHVjZmZjXHViOWFjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1Y2ZmY1x1YjlhY1x1Yjg1YyAkdSRcdWM2NDAgJHYkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGNcdWI5YzhcdWIyZTQgJFRfe059JFx1YzVkMFx1YzExYyAkdSRcdWJjODggXHVjODE1XHVjODEwXHVhY2ZjICR2JFx1YmM4OCBcdWM4MTVcdWM4MTBcdWM3NTggXHVhYzcwXHViOWFjXHVjNzU4IFx1YWUzMFx1YjMxM1x1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCAkTiRcdWFjZmMgJFEkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgyIFxcbGVxIE4sUSBcXGxlcSAzMDBcXCwwMDApJDxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCAkTi0xJFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggJGFfMSxhXzIsIFxcY2RvdHMsIGFfe04tMX0kXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDEgXFxsZXEgYV9pIFxcbGVxIDJcXCwwMDApJDxcL3A+XHJcblxyXG48cD5cdWMxMzggXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCAkTiRcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4ICRjXzEsY18yLCBcXGNkb3RzLCBjX04kXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDEgXFxsZXEgY19pIFxcbGVxIDJcXCwwMDApJDxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgJFEkXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVjZmZjXHViOWFjXHViNGU0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzkwNFx1YzVkMFx1YjI5NCAkdSRcdWM2NDAgJHYkXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDEgXFxsZXEgdSx2IFxcbGVxIE4pJDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiRpJFx1YmM4OFx1YzlmOCBcdWNmZmNcdWI5YWNcdWM3NTggXHViMmY1XHVjNzQ0ICRhbnNfaT1cXGZyYWN7cF9pfXtxX2l9JFx1Yjc3YyBcdWQ1NThcdWM3OTAuICgkcF9pJCwgJHFfaSRcdWIyOTQgXHVjMTFjXHViODVjXHVjMThjXHVjNzc4IFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4KSAkaSRcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0ICRwX2kgXFxlcXVpdiBxX2kgeF9pIFxccG1vZHsxMF45Kzd9JFx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgJDAkIFx1Yzc3NFx1YzBjMSAkMTBeOSs3JCBcdWJiZjhcdWI5Y2NcdWM3NTggXHVjODE1XHVjMjE4ICR4X2kkXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YzIxOFx1YjI5NCBcdWM3MjBcdWM3N2NcdWQ1NThcdWFjOGMgXHVjODc0XHVjN2FjXHVkNTY4XHVjNzQ0IFx1Yzk5ZFx1YmE4NVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjIwNTUyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRXhwZWN0ZWQgRGlzdGFuY2UiLCJkZXNjcmlwdGlvbiI6IjxwPkdpdmVuIGFyZSB0d28gaW50ZWdlciBzZXF1ZW5jZXM6ICRcXHthX2lcXH0kIG9mIGxlbmd0aCAkTiAtIDEkIGFuZCAkXFx7Y19pXFx9JCBvZiBsZW5ndGggJE4kLiBMZXQgdXMgYnVpbGQgYSB0cmVlICRUX3tOfSQgd2l0aCAkTiQgdmVydGljZXMgaW4gdGhlIGZvbGxvd2luZyB3YXk6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+JFRfezF9JCBpcyBhIHRyZWUgbWFkZSB1cCBvZiBvbmx5IHZlcnRleCAkMSQuPFwvbGk+XHJcblx0PGxpPkZvciAkaSAmZ3Q7IDEkLCAkVF97aX0kIGNvbm5lY3RzIHZlcnRleCAkaSQgdG8gb25lIG9mIHRoZSB2ZXJ0aWNlcyBvZiAkVF97aSAtIDF9JC4gVGhlIHByb2JhYmlsaXR5IHRoYXQgdmVydGV4ICRqJCB3aWxsIGJlIGNob3NlbiBpcyAkXFxkaXNwbGF5c3R5bGUgXFxmcmFje2Ffan17YV8xICsgXFxjZG90cyArIGFfe2kgLSAxfX0kLiBUaGUgbGVuZ3RoIG9mIHRoZSBhZGRlZCBlZGdlIGlzIHRoZW4gY2FsY3VsYXRlZCBhcyAkY19pICsgY19qJC48XC9saT5cclxuXHQ8bGk+V2hlbiAkVF97Tn0kIGlzIGJ1aWx0LCB0aGUgcHJvY2VzcyBzdG9wcy48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Zb3UgYXJlIGdpdmVuICRRJCBxdWVyaWVzLiBFYWNoIHF1ZXJ5IGlzIGEgcGFpciBvZiB2ZXJ0aWNlcy4gRm9yIGVhY2ggcXVlcnkgJCh1LCB2KSQsIGNhbGN1bGF0ZSB0aGUgZXhwZWN0ZWQgZGlzdGFuY2UgYmV0d2VlbiAkdSQgYW5kICR2JCBpbiAkVF97Tn0kLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzICROJCBhbmQgJFEkOiB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIGFuZCB0aGUgbnVtYmVyIG9mIHF1ZXJpZXMsIHJlc3BlY3RpdmVseSAoJDIgXFxsZXEgTiwgUSBcXGxlcSAzIFxcY2RvdCAxMF41JCkuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyAkTiAtIDEkIGludGVnZXJzICRhXzEkLCAkYV8yJCwgJFxcbGRvdHMkLCAkYV97TiAtIDF9JCAoJDEgXFxsZXEgYV9pIFxcbGVxIDIwMDAkKS48XC9wPlxyXG5cclxuPHA+VGhlIHRoaXJkIGxpbmUgY29udGFpbnMgJE4kIGludGVnZXJzICRjXzEkLCAkY18yJCwgJFxcbGRvdHMkLCAkY19OJCAoJDEgXFxsZXEgY19pIFxcbGVxIDIwMDAkKS48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nICRRJCBsaW5lcyBkZXNjcmliZXMgb25lIHF1ZXJ5IGFuZCBjb250YWlucyB0d28gaW50ZWdlcnMgJHUkIGFuZCAkdiQgc2VwYXJhdGVkIGJ5IGEgc3BhY2U6IG51bWJlcnMgb2YgdmVydGljZXMgdG8gZmluZCB0aGUgZXhwZWN0ZWQgZGlzdGFuY2UgKCQxIFxcbGVxIHUsIHYgXFxsZXEgTiQpLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkl0IGNhbiBiZSBwcm92ZW4gdGhhdCBlYWNoIGFuc3dlciBpcyBhIHJhdGlvbmFsIG51bWJlciBhbmQgY2FuIGJlIHdyaXR0ZW4gaW4gdGhlIGZvcm0gJFxcbWF0aGl0e2Fuc31faSA9IFxcZnJhY3twX2l9e3FfaX0kLCB3aGVyZSAkcF9pJCBhbmQgJHFfaSQgYXJlIGNvcHJpbWUgbm9uLW5lZ2F0aXZlIGludGVnZXJzIGFuZCAkMCAmbHQ7IHFfaSAmbHQ7IDEwXjkgKyA3JC4gRm9yIGVhY2ggcXVlcnksIHByaW50IHRoZSBpbnRlZ2VyICQocF9pIFxcY2RvdCBxX2leey0xfSkgXFxibW9kICgxMF45ICsgNykkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=