P10761 [BalticOI 2024] Trains

Translated from [BalticOI 2024 Day1 T3](https://boi2024.lmio.lt/tasks/d1-trains-statement.pdf).

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$.

The first line contains an integer $N$. The next $N$ lines each contain two integers $d_i, x_i$.

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

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$. | Subtask ID | Special property | Points | | :-----------: | :-----------: | :-----------: | | $1$ | $n \leq 15$ | $8$ | | $2$ | $n \leq 10^4$ | $13$ | | $3$ | $d_i = 1$ | $16$ | | $4$ | $x_i = 10^9$ | $34$ | | $5$ | No special property | $29$ | 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