#P51175. [NOI 2019] Robots

[NOI 2019] Robots

题目描述

小 R 喜欢研究机器人。

最近,小 R 新研制出了两种机器人,分别是 P 型机器人和 Q 型机器人。现在他要测试这两种机器人的移动能力,测试在从左到右排成一排的 nn 个柱子上进行,柱子用 1n1 \sim n 依次编号,ii 号柱子的高度为一个正整数 hih_i。机器人只能相邻柱子间移动,即:若机器人当前在 ii 号柱子上,它只能尝试移动到 i1i − 1 号和 i+1i + 1 号柱子上。

每次测试,小 R 会选取一个起点 ss,并将两种机器人均放置在 ss 号柱子上。随后它们会按自己的规则移动。

P 型机器人会一直向左移动,但它无法移动到比起点 ss 更高的柱子上。更具体地,P 型机器人在 l (ls)l\ (l \le s) 号柱子停止移动,当且仅当下列两个条件均成立:

  • l=1l = 1hl1>hsh_{l−1} > h_s
  • 对于满足 ljsl \le j \le sjj,有 hjhsh_j \le h_s

Q 型机器人会一直向右移动,但它只能移动到比起点 ss 更低的柱子上。更具体地,Q 型机器人在 r (rs)r\ (r \ge s) 号柱子停止移动,当且仅当下列两个条件均成立:

  • r=nr = nhr+1hsh_{r+1} \ge h_s
  • 对于满足 s<jrs < j \le rjj,有 hj<hsh_j < h_s

现在,小 R 可以设置每根柱子的高度,ii 号柱子可选择的高度范围为 [Ai,Bi][A_i, B_i],即 AihiBiA_i \le h_i \le B_i。小 R 希望无论测试的起点 ss 选在哪里,两种机器人移动过的柱子数量的差的绝对值都小于等于 22。他想知道有多少种柱子高度的设置方案满足要求,小 R 认为两种方案不同当且仅当存在一个 kk,使得两种方案中 kk 号柱子的高度不同。请你告诉他满足要求的方案数模 109+710^9 + 7 后的结果。

输入格式

从文件 robot.in 中读入数据。

第一行一个正整数 nn,表示柱子的数量。

接下来 nn 行,第 ii 行两个正整数 Ai,BiA_i, B_i,分别表示 ii 号柱子的最小和最大高度。

输出格式

输出到文件 robot.out 中。

仅一行一个整数,表示答案模 109+710^9 + 7 的值。

样例

5
3 3
2 2
3 4
2 2
3 3
1

柱子高度共两种情况:

  1. 高度为:3,2,3,2,33, 2, 3, 2, 3。此时若起点设置在 55,P 型机器人将停在 11 号柱子,共移动 44 个柱子。Q 型机器人停在 55 号柱子,共移动 00 个柱子,不符合条件;
  2. 高度为:3,2,4,2,33, 2, 4, 2, 3。此时无论起点选在哪,都满足条件,具体见下表:
起点编号 P 型机器人 Q 型机器人
11 停在 11 号柱子,移动过 00 停在 22 号柱子,移动过 11
22 停在 22 号柱子,移动过 00 停在 22 号柱子,移动过 00
33 停在 11 号柱子,移动过 22 停在 55 号柱子,移动过 22
44 停在 44 号柱子,移动过 00 停在 44 号柱子,移动过 00
55 停在 44 号柱子,移动过 11 停在 55 号柱子,移动过 00

样例 2

见附加文件的 robot/robot2.inrobot/robot2.ans

样例 3

见附加文件的 robot/robot3.inrobot/robot3.ans

样例 4

见附加文件的 robot/robot4.inrobot/robot4.ans

数据范围与提示

对于所有测试数据:1n300,1AiBi1091 \le n \le 300 , 1 \le A_i \le B_i \le 10^9

每个测试点的具体限制见下表:

测试点编号 nn\le 特殊性质
1,21,2 77 Ai=Bi,Bi7A_i=B_i,B_i\le 7
3,43,4 Bi7B_i\le 7
575\sim 7 5050 Bi100B_i\le 100
8108\sim 10 300300 Bi104B_i\le 10^4
11,1211,12 5050 Ai=1,Bi=109A_i=1,B_i=10^9
131513\sim 15
16,1716,17 150150
18,1918,19 200200
2020 300300