在编程竞赛中，海狸（beaver）按顺序从第一题到最后一题解决问题。而 Revaeb 是一种特殊的啮齿动物，它们以相反的顺序，从最后一题到第一题解决问题。

$N$ 只海狸和 $N$ 只 revaeb 将在即将到来的编程竞赛中相互竞争！比赛共有 $N$ 道题，第 $k$ 道题的分值 $p_k$ 是一个介于 $l_k$ 和 $r_k$ 之间的整数（包含边界）。选手的得分为其所解决问题的分值之和。

比赛当天，已知第 $i$ 只海狸解决了前 $i$ 道题，第 $j$ 只 revaeb 解决了最后 $j$ 道题。此外，唯一得分相同的选手对是解决了所有题目的那两位，即第 $N$ 只海狸和第 $N$ 只 revaeb。给定这些信息，计算可能的题目分值分配方案数。由于该数字可能很大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $N$ ($1 \leq N \leq 50$)，表示比赛中的题目数量。

接下来 $N$ 行，第 $k$ 行包含两个空格分隔的整数 $l_k$ 和 $r_k$ ($1 \le l_k \le r_k \le 2000$)。

输出格式

输出一行，包含答案：即分值序列的方案数对 $10^9+7$ 取模的结果。

子任务

• ($10$ 分) $N \leq 8$ 且对于所有 $k$，$r_k \leq 8$。
• ($30$ 分) 对于所有 $k$，$l_k = 1$，且存在一个固定的 $R$ 使得对于所有 $k$，$r_k = R$。
• ($30$ 分) 对于所有 $k$，$r_k \leq 100$。
• ($30$ 分) 无额外限制。

样例

输入 1

4
1 1
2 2
3 3
10 10

输出 1

1

输入 2

1
1 2000

输出 2

2000

输入 3

4
1 2
1 2
1 2
1 2

输出 3

2

输入 4

5
1 3
2 4
1 4
1 2
3 3

输出 4

18

输入 5

6
1 5
1 5
1 5
1 5
1 5
1 5

输出 5

5120

说明

样例解释 1

题目分值只能是 $1, 2, 3, 10$。使用这些分值，海狸的得分分别为 $1, 3, 6, 16$，revaeb 的得分分别为 $10, 13, 15, 16$。除了第 $4$ 只海狸和第 $4$ 只 revaeb 的得分均为 $16$ 外，其余得分均不相同，因此该序列有效，答案为 $1$。

样例解释 2

该样例满足第二个子任务的限制。

样例解释 3

该样例满足第二个子任务的限制。

唯一有效的题目分值序列是 $1, 2, 2, 2$ 和 $2, 2, 2, 1$，因此答案为 $2$。

样例解释 5

该样例满足第二个子任务的限制。