在程式設計競賽中，海狸（beavers）會依序從第一題解到最後一題。另一方面，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

此範例滿足第二個子任務的限制。