31970번 - Trains 서브태스크다국어

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$ sequentially. Vilnius is assigned the number $1$.

Each city has a train station with a single train route that operates from that station. You can only get on a train at the start of its route, though you can get off at any of its stops. Trains starting their route at the $i$-th city make a stop every $d_i$ cities, and their route consists of $x_i$ stops (not including the starting city). If $d_i = 0$, the trains operating from the $i$-th city are currently out of service, so you cannot get on them.

To be more precise, if you get on a train in the $i$-th city, you can get off the train in any city numbered $i + t \cdot d_i$, where $1 ≤ t ≤ x_i$. Note that since you only want to visit cities in Lithuania, you won't ride further than the $N$-th city, even if the train has more stops on its route.

You are going to visit some cities, using trains to travel between them. As you plan your trip, you start to wonder how many different options you have for your journey that starts at Vilnius. Two journeys are different if they make stops at different sequences of cities.

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

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$ – the numbers describing the route starting in the $i$-th city.

Output a single integer – the number of ways you can visit some of the $N$ cities taken modulo $10^9 + 7$.

• $1 ≤ N ≤ 10^5$
• $0 ≤ d_i ≤ 10^9$ (for each $1 ≤ i ≤ N$)
• $0 ≤ x_i ≤ 10^9$ (for each $1 ≤ i ≤ N$)