#P1191. 列车

列车

当前没有测试数据。

由于测试点个数限制,此题暂不开放评测。

题目描述

你已经抵达维尔纽斯,并希望参观立陶宛的不同城市。立陶宛的城市位于一条直线上,并按顺序从 11NN 编号。维尔纽斯是 11 号城市。每个城市都有一个火车站,并且有一条从该站出发的单轨列车运营路线。你只能在该路线起点的城市上车,但可以在其任何一站下车。从第 ii 个城市开始的列车每行驶 did_i 个城市就会停靠一站,并且其路线包含 xix_i 个停靠站(不包括起始城市)。如果 di=0d_i = 0,则从第 ii 个城市出发的列车目前处于停运状态,因此你不能乘坐它们。

更具体地说,如果你在第 ii 个城市上车,你可以在任何编号为 i+tdii + t \cdot d_i 的城市下车,其中 1txi1 \leq t \leq x_i。请注意,由于你只希望参观立陶宛的城市,因此即使列车在其路线上有更多的停靠站,你也不会超过第 NN 个城市下车。

你打算使用列车前往参观一些城市。在规划你的旅行时,你开始思考从维尔纽斯出发的旅程有多少种不同的选择。如果两次旅行在不同的城市序列中停靠,则它们被视为不同。输出答案对 109+710^9 + 7 取模的值。

输入格式

第一行一个整数 NN

接下来 NN 行每行两个整数 di,xid_i,x_i

输出格式

输出路线数对 109+710^9 + 7 取模的值。

样例 #1

样例输入 #1

5
1 3
2 1
1 3
0 10
3 5

样例输出 #1

7

提示

本题采用捆绑测试。

对于样例,存在如下七种路线:

  • 11
  • 121 \rightarrow 2
  • 1241 \rightarrow 2 \rightarrow 4
  • 131 \rightarrow 3
  • 1341 \rightarrow 3 \rightarrow 4
  • 1351 \rightarrow 3 \rightarrow 5
  • 141 \rightarrow 4
子任务编号 特殊性质 分值
11 n15n \leq 15 88
22 n104n \leq 10^4 1313
33 di=1d_i = 1 1616
44 xi=109x_i = 10^9 3434
55 无特殊性质 2929

对于所有数据,保证 1N1051 \leq N \leq 10^50di,xi1090 \leq d_i,x_i \leq 10^9