Trains

Time limit2sMemory limit1024 MB

Summary

Count the journeys from city 1 where a train from city i stops every d_i cities, at most x_i times, without passing city N. Print the count modulo 10^9+7.

Level: Medium7 of 10
Topics: Dynamic programming, Prefix sum
Solved: No attempts yet

Problem

You have arrived in Vilnius and want to visit various cities in Lithuania.

Cities in Lithuania are located on a straight line and numbered from $1$ to $N$ in order. Vilnius is city number $1$ .

Each city has a train station with one train route that departs from it. You can only board a train at the start of its route, but you can get off at any of its stops. Trains starting at the $i$ -th city stop every $d_i$ cities, and their route has $x_i$ stops (not counting the starting city). If $d_i = 0$ , the trains departing from the $i$ -th city are out of service, so you cannot board them.

More precisely, if you board a train in city $i$ , you can get off in any city numbered $i + t \cdot d_i$ where $1 \le t \le x_i$ . Since you only want to visit cities in Lithuania, you will not ride past city $N$ , even if the train has more stops on its route.

You are going to visit some cities by taking trains between them. While planning the trip, you wonder how many different options you have for a journey that starts in Vilnius. Two journeys are different if they stop at different sequences of cities.

Calculate this number and print it modulo $10^9 + 7$ .

Input

The first line contains one integer $N$ , the number of cities. Then $N$ lines follow. The $i$ -th of them contains two integers $d_i$ and $x_i$ , describing the route that starts in the $i$ -th city.

Output

Print a single integer, the number of ways to visit some of the $N$ cities, modulo $10^9 + 7$ .

Constraints

$1 \le N \le 10^5$
$0 \le d_i \le 10^9$ for each $1 \le i \le N$
$0 \le x_i \le 10^9$ for each $1 \le i \le N$

Examples1

Example 1
Input
```
5
1 3
2 1
1 3
0 10
3 5
```
Expected output
```
7
```