题目背景

海曙区“呦呦海贝”月赛即将开始，贝贝正在协助老师设计题目的分值。为了检验自己的方案，贝贝邀请小伙伴们进行了一场模拟挑战。

题目描述

挑战共有 $N$ 道题，从 $1$ 到 $N$ 编号。贝贝需要为第 $k$ 道题确定一个整数分值 $p_k$，满足 $l_k\leq p_k\leq r_k$。

参加挑战的 $2N$ 名选手分成两队，每队有 $N$ 人，各自从 $1$ 到 $N$ 编号：

• 正序队：从第一题开始按顺序答题，其中第 $i$ 名选手恰好做出前 $i$ 道题，即第 $1,2,\ldots,i$ 道题。
• 倒序队：从最后一题开始倒序答题，其中第 $j$ 名选手恰好做出最后 $j$ 道题，即第 $N-j+1,N-j+2,\ldots,N$ 道题。

每名选手的得分等于其做出的所有题目的分值之和。

两队的第 $N$ 名选手都做出了全部题目，他们的得分必然相同。贝贝希望，全场只有这两名选手得分相同，除此以外，任意两名不同选手的得分都不相同。

请你求出满足要求的分值分配方案数。如果两个方案中存在某道题的分值不同，就认为这两个方案不同。由于答案可能很大，请输出答案对 $10^9+7$ 取模后的结果。

输入格式

第一行包含一个整数 $N$，表示题目数量。

接下来 $N$ 行，第 $k$ 行包含两个整数 $l_k,r_k$，表示第 $k$ 道题分值的取值范围。

输出格式

输出一个整数，表示合法分值分配方案数对 $10^9+7$ 取模后的结果。

样例 1

4
1 1
2 2
3 3
10 10

1

样例 1 解释

每道题的分值都已固定，依次为 $1,2,3,10$。

正序队各选手的得分依次为 $1,3,6,16$；倒序队各选手的得分依次为 $10,13,15,16$。

只有两队的第 $4$ 名选手同为 $16$ 分，其余选手的得分互不相同，因此这一方案合法，答案为 $1$。

样例 2

1
1 2000

2000

样例 2 解释

此时只有两名选手，且两人都做出了唯一的一道题。无论这道题的分值取 $1$ 到 $2000$ 中的哪个整数，都满足要求，因此答案为 $2000$。

样例 3

4
1 2
1 2
1 2
1 2

2

样例 3 解释

合法的分值序列只有 $(1,2,2,2)$ 和 $(2,2,2,1)$，因此答案为 $2$。

样例 4

5
1 3
2 4
1 4
1 2
3 3

18

样例 5

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

5120

数据范围

对于所有测试数据，保证 $1\leq N\leq50$，$1\leq l_k\leq r_k\leq2000$。

本题采用子任务计分。只有通过一个子任务内的全部测试点，才能获得该子任务的分数。