Jumping

Jumping

From a location i, you can jump forward $a_i$ or $b_i$ steps forward. Once you get beyond location $n$, stop making any jumps. Beginning at location 1, how many ways are there get past location $n$.

Input

The first line contains the integer $n$. The following $n$ lines contain integers $a_i$ and $b_i$ indicating the size of jumps made. In order of location $1,2,3 \dots$.

Output

The number of ways of getting from location $1$ to beyond $n$, modulo $10^9 + 7$

Constraints

• $1 \le n \le 10^5$
• $1 \le a,b \le 10^5$

Example 1

In

5
1 2
1 2
1 2
1 2
1 2

Out

13

Example 2

In

10
1 3
1 3
2 2
2 3
2 5
2 5
1 4
1 5
1 4
2 2

Out

31