题目描述

题目译自 BalticOI 2024 Day1「Trains」

你已抵达维尔纽斯，并希望游览立陶宛的一些城市。

立陶宛的城市位于一条直线上，从 $1$ 到 $N$ 依次编号。维尔纽斯的编号为 $1$。

每个城市都有一个火车站，从该火车站出发的列车只有一条线路。你只能在线路的起点上车，但可以在任何站点下车。以第 $i$ 个城市为起点的列车每隔 $d_i$ 个城市停靠一次，其线路包括 $x_i$ 个站点（不包括起点城市）。如果 $d_i = 0$，则从第 $i$ 个城市出发的列车当前停运，因此你无法上车。

更准确地说，如果你在第 $i$ 个城市上车，你可以在编号为 $i + t\cdot d_i$ 的任何城市下车，其中 $1 \le t \le x_i$。 请注意，由于你只想游览立陶宛的城市，因此即使列车路线上有更多的站点，你也不会乘坐列车到达超过第 $N$ 个城市的城市。

你想参观一些城市，所以你会乘坐火车往返于这些城市之间。在计划行程时，你想知道有多少种从维尔纽斯出发的不同的旅程。如果两段旅程按不同的城市序列游览，那么这两段旅程不同。

计算这个值，输出这个值对 $10^9+7$ 取模后的结果。

输入格式

第一行一个整数 $N$，表示城市个数。

接下来 $N$ 行，第 $i$ 行包含两个整数 $d_i$ 和 $x_i$，表示从城市 $i$ 出发的线路。

输出格式

输出一个整数，表示你游览 $N$ 个城市中的一些可以采用的旅程数模 $10^9+7$ 的值。

5
1 3
2 1
1 3
0 10
3 5

7

数据范围与提示

对于所有数据，满足：

• $1\le N\le 10^5$
• $0\le d_i,x_i\le 10^9$（对于所有 $1\le i\le N$）

详细子任务附加限制及分值如下表所示。