UOJ Logo Universal Online Judge

UOJ

#479. 【NOI2019】机器人

统计

小 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$ 后的结果。

输入格式

从标准输入中读入数据。

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

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

输出格式

输出到标准输出中。

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

样例一

input

5
3 3
3 3
3 4
2 2
3 3

output

1

explanation

柱子高度共两种情况: 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 个

样例二至样例四

见样例数据下载。

限制与约定

对于所有测试数据:$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$$7$$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$

时间限制:$3\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载