[NOI2019] 机器人

时限 3 秒，内存 512MB

小 R 喜欢研究机器人。 最近，小 R 新研制出了两种机器人，分别是 `P` 型机器人和 `Q` 型机器人。现在他要测试这两种机器人的移动能力，测试在从左到右排成一排的 $n$ 个柱子上进行，柱子用$1 - n$ 依次编号，$i$ 号柱子的高度为一个正整数 $h_i$。机器人**只能在相邻柱子间移动**，即：若机器人当前在 $i$ 号柱子上，它只能尝试移动到 $i - 1$ 号和 $i + 1$ 号柱子上。 每次测试，小 R 会选取一个起点 $s$，并将两种机器人均放置在 $s$ 号柱子上。随后它们会按自己的规则移动。 `P` 型机器人会一直**向左**移动，但它**无法**移动到比起点 $s$ **更高**的柱子上。更具体地，`P` 型机器人在 $l (l \leq s)$ 号柱子停止移动，**当且仅当**下列两个条件均成立： - $l = 1$ 或 $h_{l-1} > hs$。 - 对于满足 $l \leq j \leq s$ 的 $j$，有 $h_j \leq h_s$。 `Q` 型机器人会一直**向右**移动，但它**只能**移动到比起点 $s$ **更低**的柱子上。更具体地，`Q` 型机器人在 $r (r \geq s)$ 号柱子停止移动，**当且仅当**下列两个条件均成立： - $r = n$ 或 $h_{r+1} \geq h_s$。 - 对于满足 $s < j \leq r$ 的 $j$，有 $h_j < h_s$。 现在，小 R 可以设置每根柱子的高度，$i$ 号柱子可选择的高度范围为 $[A_i, B_i]$，即$A_i \leq h_i \leq B_i$。小 R 希望**无论**测试的起点 $s$ 选在哪里，两种机器人移动过的柱子数量的差的绝对值都**小于等于**$2$。他想知道有多少种柱子高度的设置方案满足要求，小 R 认为两种方案不同当且仅当存在一个 $k$，使得两种方案中 $k$ 号柱子的高度不同。请你告诉他满足要求的方案数模 $10^9 + 7$ 后的结果。

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

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

5
3 3
3 3
3 4
2 2
3 3

1

### 更多样例 您可以通过附加文件获得更多样例。 #### 样例 2 见附加文件的 `robot/robot2.in` 与 `robot/robot2.ans`。 #### 样例 3 见附加文件的 `robot/robot3.in` 与 `robot/robot3.ans`。 #### 样例 4 见附加文件的 `robot/robot4.in` 与 `robot/robot4.ans`。 ### 样例 1 解释 柱子高度共两种情况： - 高度为：`3 2 3 2 3`。此时若起点设置在 $5$，`P` 型机器人将停在 $1$ 号柱子，共移动$4$ 个柱子。`Q` 型机器人停在 $5$ 号柱子，共移动 $0$ 个柱子，不符合条件。 - 高度为：`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 \leq n \leq 300$ , $1 \leq A_i \leq B_i \leq 10^9$。 每个测试点的具体限制见下表： | 测试点编号 | $n\le$ | 特殊性质 | | :----------: | :----------: | :----------: | | $1,2$ | $7$ | $A_i=B_i,B_i\le 7$ | | $3,4$ | $7$ | $B_i\le 7$ | | $5,6,7$ | $50$ | $B_i\le 100$ | | $8,9,10$ | $300$ | $B_i\le 10^4$ | | $11,12$ | $50$ | $A_i=1,B_i=10^9$ | | $13,14,15$ | $50$ | 无 | | $16,17$ | $150$ | 无 | | $18,19$ | $200$ | 无 | | $20$ | $300$ | 无 |