机器人

题目背景

时限3秒，内存512MB

题目描述

小 R 喜欢研究机器人。

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

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

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

• l = 1l=1 或 h_{l-1} > hshl−1>hs。

• 对于满足 l \leq j \leq sl≤j≤s 的 jj，有 h_j \leq h_shj≤hs。

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

• r = nr=n 或 h_{r+1} \geq h_shr+1≥hs。

• 对于满足 s < j \leq rs<j≤r 的 jj，有 h_j < h_shj<hs。

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

输入输出格式

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

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

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

输入输出样例

5
3 3
3 3
3 4
2 2
3 3

1

说明

柱子高度共两种情况：

• 高度为：3 2 3 2 3。此时若起点设置在 55，P 型机器人将停在 11 号柱子，共移动44 个柱子。Q 型机器人停在 55 号柱子，共移动 00 个柱子，不符合条件。

-高度为：3 2 4 2 3。此时无论起点选在哪，都满足条件，具体见下表：

对于所有测试数据：1 \leq n \leq 3001≤n≤300 , 1 \leq A_i \leq B_i \leq 10^91≤Ai≤Bi≤109。

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