Максим Витальевич захотел отправиться в путешествие. Наверное, ему стало скучно. В любом случае для своего нового путешествия Максим Витальевич решил воспользоваться кораблем для межпространственных путешествий, с помощью которого можно отправиться путешествовать в $$$n$$$-мерном пространстве.
Спустя некоторое время своего путешествия Максим Витальевич попадает в довольно шаткое положение. В прямом смысле его корабль начинает сильно шатать из стороны в сторону. Максим Витальевич сразу понял, что он попал в квантовую турбулентность.
Квантовую турбулентность можно описать следующим образом: турбулентность в измерении $$$i$$$ действует для координат $$$x_i \ge 1$$$. Если корабль находится в квантовой турбулентности для $$$i$$$-го измерения, то он становится неуправляемым в данном измерении. Вместо этого корабль перемещается из координаты $$$x_i$$$ в координату $$$x_i + 1$$$ с вероятностью $$$p$$$ и в координату $$$x_i - 1$$$ с вероятностью $$$q = 1 - p$$$. Если корабль попадает в координату $$$x_i \lt 1$$$, он снова становится управляемым и перестает случайно перемещаться в $$$i$$$-м измерении.
Вам необходимо определить вероятность $$$ans$$$, с которой Максим Витальевич сможет полностью восстановить управление по всем $$$n$$$ измерениям, если изначально он находится в координате $$$(a_1, a_2, ..., a_n)$$$.
В первой строке задано число $$$n$$$ — количество измерений.
Во второй строке задано $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ — начальные координаты корабля Максима Витальевича.
В следующих $$$n$$$ строках задано по два целых числа $$$s_i$$$, $$$t_i$$$ — значение вероятности $$$p_i$$$, представленное в виде дроби $$$\frac{s_i}{t_i}$$$.
$$$$$$ 1 \le n \le 1\,000 $$$$$$ $$$$$$ 1 \le a_i \le 1\,000 $$$$$$ $$$$$$ 0 \le s_i \le 10^9 $$$$$$ $$$$$$ 1 \le t_i \le 10^9 $$$$$$
Гарантируется, что ответ $$$ans$$$ можно представить в виде несократимой дроби $$$\frac{s}{t}$$$.
Выведите в единственной строке вероятность того, что Максим Витальевич сможет восстановить управление, представленное в виде $$$s \cdot t^{-1}\mod 10^9+7$$$.
3 1 2 3 4 6 8 10 5 6
714250005
