Background

Translated from BalticOI 2024 Day1 T3.

Problem Description

You have arrived in Vilnius and want to visit different cities in Lithuania. The cities of Lithuania lie on a straight line and are numbered from $1$ to $N$ in order. Vilnius is city $1$. Each city has a train station, and there is a monorail train route operating starting from that station. You can only board the train in the city where the route starts, but you may get off at any of its stops. A train starting from city $i$ stops once every $d_i$ cities, and its route contains $x_i$ stops (not including the starting city). If $d_i = 0$, then the train starting from city $i$ is currently out of service, so you cannot ride it.

More precisely, if you board at city $i$, you may get off at any city numbered $i + t \cdot d_i$, where $1 \leq t \leq x_i$. Note that since you only want to visit cities in Lithuania, even if the train has more stops on its route, you will not get off beyond city $N$.

You plan to use trains to visit some cities. While planning your trip, you start thinking about how many different journeys are possible starting from Vilnius. If two journeys stop in different sequences of cities, they are considered different. Output the answer modulo $10^9 + 7$.

Input Format

The first line contains an integer $N$.

The next $N$ lines each contain two integers $d_i, x_i$.

Output Format

Output the number of routes modulo $10^9 + 7$.

5
1 3
2 1
1 3
0 10
3 5

7

Hint

For the sample, there are the following seven routes:

• $1$.
• $1 \rightarrow 2$.
• $1 \rightarrow 2 \rightarrow 4$.
• $1 \rightarrow 3$.
• $1 \rightarrow 3 \rightarrow 4$.
• $1 \rightarrow 3 \rightarrow 5$.
• $1 \rightarrow 4$.

Constraints: for all testdata, it is guaranteed that $1 \leq N \leq 10^5$ and $0 \leq d_i, x_i \leq 10^9$.

Translated by ChatGPT 5