H. Roulette
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Little John loves challenges and decided to test his luck at the Big Tiger roulette. Initially, he plays on a roulette with $$$l[1]$$$ markings, all equally probable, but only one marking results in a win. After every $$$q[i]$$$ consecutive losses, the system reduces the size of the roulette, moving to a new one with $$$l[i+1]$$$ markings, where $$$l[i+1] \lt l[i]$$$. This process continues until reaching the last roulette, which has $$$l[n]$$$ markings.

Little John is very persistent and will keep playing until he gets his first win. After that, he decides to stop and go home.

You, concerned about Little John's obsession, decided to calculate the expected value $$$E$$$ of the number of times the roulette will be spun until the first win.

The result should be represented as an irreducible fraction $$$\frac{p}{q}$$$, where $$$\gcd(p, q) = 1$$$. To avoid issues with floating-point numbers, print the answer as $$$p \cdot q^{-1} \mod (10^9 + 7)$$$, where $$$q^{-1}$$$ is the modular inverse of $$$q$$$ modulo $$$10^9 + 7$$$. It can be shown that $$$q \neq 0 \mod (10^9 + 7)$$$ within the problem's constraints.

Input

The input consists of an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$), representing the number of roulettes, followed by $$$n$$$ pairs $$$l[i] \, q[i]$$$, where $$$l[i]$$$ represents the number of markings on the $$$i$$$-th roulette and $$$q[i]$$$ ($$$1 \leq q[i] \leq 10^9$$$) represents the number of consecutive losses required to switch to the next roulette. For the last roulette, $$$q_n = -1$$$.

It is guaranteed that $$$1 \leq l[n] \lt l[n-1] \lt \dots \lt l[1] \lt 10^9 + 7$$$.

Output

Print a single integer, the expected value $$$E$$$ of the number of spins until the first win, represented as $$$p \cdot q^{-1} \mod (10^9 + 7)$$$.

Examples
Input
1
2 -1
Output
2
Input
2
3 1
2 -1
Output
333333338