#3157. 「NOI2019」机器人

内存限制:512 MiB 时间限制:3000 ms 输入文件:robot.in 输出文件:robot.out
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

小 R 喜欢研究机器人。

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

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

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

  • l = 1 h_{l−1} > h_s
  • 对于满足 l \le j \le s j ,有 h_j \le h_s

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

  • r = n h_{r+1} \ge h_s
  • 对于满足 s < j \le r j ,有 h_j < h_s

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

输入格式

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

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

接下来 n 行,第 i 行两个正整数 A_i, B_i ,分别表示 i 号柱子的最小和最大高度。

输出格式

输出到文件 robot.out 中。

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

样例

样例输入 1

5
3 3
3 3
3 4
2 2
3 3

样例输出 1

1

样例说明 1

柱子高度共两种情况:

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

样例 2

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

样例 3

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

样例 4

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

数据范围与提示

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

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

测试点编号 n\le 特殊性质
1,2 7 A_i=B_i,B_i\le 7
3,4 B_i\le 7
5\sim 7 50 B_i\le 100
8\sim 10 300 B_i\le 10^4
11,12 50 A_i=1,B_i=10^9
13\sim 15
16,17 150
18,19 200
20 300