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