P10761 [BalticOI 2024] Trains

翻译自 [BalticOI 2024 Day1 T3](https://boi2024.lmio.lt/tasks/d1-trains-statement.pdf)。

你已经抵达维尔纽斯，并希望参观立陶宛的不同城市。立陶宛的城市位于一条直线上，并按顺序从 $1$ 到 $N$ 编号。维尔纽斯是 $1$ 号城市。每个城市都有一个火车站，并且有一条从该站出发的单轨列车运营路线。你只能在该路线起点的城市上车，但可以在其任何一站下车。从第 $i$ 个城市开始的列车每行驶 $d_i$ 个城市就会停靠一站，并且其路线包含 $x_i$ 个停靠站（不包括起始城市）。如果 $d_i = 0$，则从第 $i$ 个城市出发的列车目前处于停运状态，因此你不能乘坐它们。 更具体地说，如果你在第 $i$ 个城市上车，你可以在任何编号为 $i + t \cdot d_i$ 的城市下车，其中 $1 \leq t \leq x_i$。请注意，由于你只希望参观立陶宛的城市，因此即使列车在其路线上有更多的停靠站，你也不会超过第 $N$ 个城市下车。 你打算使用列车前往参观一些城市。在规划你的旅行时，你开始思考从维尔纽斯出发的旅程有多少种不同的选择。如果两次旅行在不同的城市序列中停靠，则它们被视为不同。输出答案对 $10^9 + 7$ 取模的值。

第一行一个整数 $N$。 接下来 $N$ 行每行两个整数 $d_i,x_i$。

输出路线数对 $10^9 + 7$ 取模的值。

对于样例，存在如下七种路线： - $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$ | 子任务编号 | 特殊性质 | 分值 | | :-----------: | :-----------: | :-----------: | | $1$ | $n \leq 15$ | $8$ | | $2$ | $n \leq 10^4$ | $13$ | | $3$ | $d_i = 1$ | $16$ | | $4$ | $x_i = 10^9$ | $34$ | | $5$ | 无特殊性质 | $29$ | 对于所有数据，保证 $1 \leq N \leq 10^5$，$0 \leq d_i,x_i \leq 10^9$。