暂无测试数据。

小 $R$ 喜欢研究机器人。

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

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

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

• $l = 1$ 或 $h_{l-1} > h_s$

• 对于满足 $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$ 的值。

数据范围

对于所有测试数据： $1 \leq n \leq 300, 1 \leq A_i \leq B_i \leq 10 ^ 9$ 。

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

5
3 3
3 3
3 4
2 2
3 3

1