Maxim Vitalievich wanted to go on a trip. He must have gotten bored. In any case, for his new journey, Maxim Vitalyevich decided to use a ship for interdimensional travel, with which you can travel to $$$n$$$-dimensional space.
After some time of his journey, Maxim Vitalievich finds himself in a rather precarious position. In the literal sense, his ship begins to wobble violently from side to side. Maxim Vitalievich immediately realized that he had fallen into quantum turbulence.
Quantum turbulence can be described as follows: turbulence in the $$$i$$$-th dimension acts for the coordinates $$$x_i \ge 1$$$. If the ship is in quantum turbulence for the $$$i$$$-th dimension, then it becomes uncontrollable in this dimension. Instead, the ship moves from coordinate $$$x_i$$$ to coordinate $$$x_i + 1$$$ with probability $$$p$$$ and to coordinate $$$x_i - 1$$$ with probability $$$q = 1 - p$$$. If the ship enters the coordinate $$$x_i \lt 1$$$, it becomes controllable again and stops randomly moving in the $$$i$$$-th dimension.
You need to determine the probability $$$ans$$$ with which Maxim Vitalievich will be able to completely restore control over all $$$n$$$ dimensions, if initially he is in the coordinate $$$(a_1, a_2, ..., a_n)$$$.
The first line contains the number $$$n$$$ — the number of measurements.
The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ — the initial coordinates of Maxim Vitalyevich's ship.
The next $$$n$$$ lines contain two integers $$$s_i$$$, $$$t_i$$$ — the value of the probability $$$p_i$$$, represented as a fraction $$$\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 $$$$$$
It is guaranteed that the answer $$$ans$$$ can be represented as an irreducible fraction $$$\frac{s}{t}$$$.
In a single line print the probability that Maxim Vitalievich will be able to restore the control represented as $$$s \cdot t^{-1}\mod 10^9+7$$$.
3 1 2 3 4 6 8 10 5 6
714250005
