Trong các cuộc thi lập trình, hải ly giải các bài toán theo thứ tự từ đầu đến cuối. Ngược lại, Revaeb là một loài gặm nhấm đặc biệt giải các bài toán theo thứ tự ngược lại, từ cuối lên đầu.

$N$ chú hải ly và $N$ chú revaeb sẽ thi đấu với nhau trong cuộc thi lập trình sắp tới! Cuộc thi bao gồm $N$ bài toán, bài toán thứ $k$ có số điểm nguyên $p_k$ nằm trong khoảng từ $l_k$ đến $r_k$ (bao gồm cả hai đầu). Điểm số của một thí sinh là tổng số điểm của các bài toán mà họ giải được.

Vào ngày thi, người ta biết rằng hải ly thứ $i$ đã giải được $i$ bài toán đầu tiên, và revaeb thứ $j$ đã giải được $j$ bài toán cuối cùng. Ngoài ra, cặp thí sinh duy nhất có cùng điểm số là hai thí sinh đã giải được tất cả các bài toán, đó là hải ly thứ $N$ và revaeb thứ $N$. Với thông tin này, hãy đếm số cách gán giá trị điểm cho các bài toán trong cuộc thi. Vì số lượng này có thể rất lớn, hãy in ra phần dư của nó khi chia cho $10^9 + 7$.

Dữ liệu vào

Dòng đầu tiên chứa $N$ ($1 \leq N \leq 50$), số lượng bài toán trong cuộc thi.

$N$ dòng tiếp theo, dòng thứ $k$ chứa hai số nguyên cách nhau bởi dấu cách là $l_k$ và $r_k$ ($1 \le l_k \le r_k \le 2000$).

Dữ liệu ra

In ra một dòng chứa kết quả: số lượng các dãy giá trị điểm thỏa mãn theo modulo $10^9+7$.

Nhiệm vụ con

• ($10$ điểm) $N \leq 8$ và $r_k \leq 8$ với mọi $k$.
• ($30$ điểm) $l_k = 1$ với mọi $k$ và tồn tại một giá trị $R$ cố định sao cho $r_k = R$ với mọi $k$.
• ($30$ điểm) $r_k \leq 100$ với mọi $k$.
• ($30$ điểm) Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

4
1 1
2 2
3 3
10 10

Kết quả 1

1

Ví dụ 2

1
1 2000

Kết quả 2

2000

Ví dụ 3

4
1 2
1 2
1 2
1 2

Kết quả 3

2

Ví dụ 4

5
1 3
2 4
1 4
1 2
3 3

Kết quả 4

18

Ví dụ 5

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

Kết quả 5

5120

Ghi chú

Giải thích ví dụ 1

Các giá trị điểm của các bài toán chỉ có thể là $1, 2, 3, 10$. Sử dụng các giá trị điểm này, điểm số của các chú hải ly lần lượt là $1, 3, 6, 16$ và điểm số của các chú revaeb lần lượt là $10, 13, 15, 16$. Tất cả các điểm số này đều khác nhau ngoại trừ điểm số $16$ đạt được bởi hải ly thứ $4$ và revaeb thứ $4$, vì vậy dãy giá trị này là hợp lệ, dẫn đến kết quả là $1$.

Giải thích ví dụ 2

Ví dụ này thỏa mãn các ràng buộc của nhiệm vụ con thứ hai.

Giải thích ví dụ 3

Ví dụ này thỏa mãn các ràng buộc của nhiệm vụ con thứ hai.

Các dãy giá trị điểm hợp lệ duy nhất là $1, 2, 2, 2$ và $2, 2, 2, 1$, dẫn đến kết quả là $2$.

Giải thích ví dụ 5

Ví dụ này thỏa mãn các ràng buộc của nhiệm vụ con thứ hai.