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

立陶宛的城市位于一条直线上，并按顺序编号为 $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$ 取模。

样例

样例输入 1

5
1 3
2 1
1 3
0 10
3 5

样例输出 1

7

说明 1

共有 7 种可能的旅程： $1$ $1 \to 2$ $1 \to 2 \to 4$ $1 \to 3$ $1 \to 3 \to 4$ $1 \to 3 \to 5$ * $1 \to 4$

数据范围

• $1 \le N \le 10^5$
• $0 \le d_i \le 10^9$（对于每个 $1 \le i \le N$）
• $0 \le x_i \le 10^9$（对于每个 $1 \le i \le N$）

子任务