流星雨
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

现在一共有n天，第i天如果有流星雨的话，会有w_i颗流星雨。
第i天有流星雨的概率是p_i。
如果第一天有流星雨了，那么第二天有流星雨的可能性是，否则是p_2。相应的，如果第天有流星雨，第i天有流星雨的可能性是，否则是p_i。
求n天后，流星雨颗数的期望。

输入描述:

第一行三个整数，n,a,b，其中n为天数，
第二行n个整数w_i。
接下来n行，每行两个整数，x,y，第i+2行表示第i天有流星雨的概率。

输出描述:

一行一个整数，为答案对 取模的结果。
即设答案化为最简分式后的形式为，其中a和b互质。输出整数 x 使得且。可以证明这样的整数x是唯一的。

示例1

输入

复制 
2 1 3
1 1 
1 2
1 2

输出

复制 
166666669

说明

第一天有流星雨第二天也有流星雨的概率是\frac{1}{2} \times (\frac{1}{2} + \frac{1}{3})，然后乘以流星雨的颗数2
第一天有流星雨第二天没有流星雨的概率是\frac{1}{2} \times \frac{1}{6}，乘以颗数1
第一天没有，第二天有的概率\frac{1}{2} \times \frac{1}{2}，乘以颗数1
第一天没有，第二天也没有的概率\frac{1}{2} \times \frac{1}{2}，乘以颗数0。
所以流星雨颗数的期望是\frac{7}{6}
示例2

输入

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

输出

复制 
763333341