Chủ tịch K quan tâm đến chuột túi và quyết định quan sát hành vi của chúng. Có \(N\) con chuột túi được đánh số từ \(1\) đến \(N\), mỗi con có một chiếc túi. Con thứ \(i\) có kích thước cơ thể là \(A_i\) và kích thước túi là \(B_i\). Túi luôn nhỏ hơn cơ thể của chính con chuột túi đó, tức là \(B_i < A_i\).

Ban đầu, không có con chuột túi nào nằm trong túi của con khác. Chúng lặp lại thao tác sau cho đến khi không thể thực hiện thêm thao tác nào:

Chọn hai con chuột túi \(i\) và \(j\) sao cho \(A_i < B_j\), con \(i\) không nằm trong túi của bất kỳ con nào khác và túi của con \(j\) đang trống. Khi đó, con \(i\) chui vào túi của con \(j\).

Thao tác này vẫn được phép nếu trong túi của con \(i\) đã có một con chuột túi khác, hoặc nếu con \(j\) đang nằm trong túi của một con khác. Khi con \(i\) di chuyển, tất cả những con nằm bên trong nó cũng di chuyển theo. Nếu có nhiều cặp \((i,j)\) hợp lệ, không biết cặp nào sẽ được chọn.

Yêu cầu

Cho kích thước cơ thể và kích thước túi của từng con chuột túi, hãy tính số trạng thái cuối cùng khác nhau có thể xuất hiện, lấy phần dư khi chia cho \(1\,000\,000\,007\).

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn:

• Dòng đầu tiên chứa số nguyên \(N\), là số con chuột túi.
• Dòng thứ \(i+1\) (\(1 \le i \le N\)) chứa hai số nguyên \(A_i\) và \(B_i\), cách nhau bởi dấu cách, lần lượt là kích thước cơ thể và kích thước túi của con thứ \(i\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa phần dư của số trạng thái cuối cùng khác nhau khi chia cho \(1\,000\,000\,007\).

Ràng buộc

• \(1 \le N \le 300\).
• \(1 \le B_i < A_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\).

Phân nhóm

• Các bộ kiểm thử chiếm \(50\%\) tổng số điểm thỏa mãn \(N \le 30\).
• Các bộ kiểm thử chiếm \(70\%\) tổng số điểm thỏa mãn \(N \le 70\).

Các tỉ lệ trên là các điều kiện tích lũy; không cộng chúng thành các nhóm điểm độc lập.

Ví dụ

5
4 3
3 1
6 5
2 1
4 2

4

20
7 6
7 3
10 1
7 2
10 7
10 7
8 6
3 2
5 4
7 2
3 2
10 9
9 4
7 2
8 6
5 4
8 6
7 4
10 5
9 3

21060