Mỗi ngày có nhiều container được tàu thủy đưa đến cảng JOI, rồi được xe tải vận chuyển đi khắp cả nước.

Cảng JOI rất hẹp và chỉ có hai khu vực để đặt container. Tại mỗi khu vực, có thể xếp chồng một số lượng bất kỳ container theo phương thẳng đứng.

Vì lý do an toàn, khi một container đến bằng tàu thủy, nó phải được đặt vào một trong hai khu vực; nếu khu vực đó đã có container thì container mới phải được đặt lên trên cùng. Khi một container rời cảng bằng xe tải, nó phải được lấy từ trên cùng của một trong hai chồng.

Hôm nay có \(N\) container đến cảng JOI và sau đó tất cả đều sẽ rời cảng bằng xe tải. Với mỗi container, bạn biết thời điểm nó đến và thời điểm nó rời cảng.

Yêu cầu

Tính số cách đặt và lấy các container hợp lệ, lấy phần dư theo \(1\,000\,000\,007\).

Hai cách được xem là khác nhau nếu có ít nhất một container được đặt vào hai khu vực khác nhau trong hai cách đó.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\), là số container.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên \(A_i,B_i\): container thứ \(i\) đến cảng tại thời điểm \(A_i\) và rời cảng tại thời điểm \(B_i\).

Dữ liệu ra

In ra số cách đặt và lấy container hợp lệ, lấy phần dư theo \(1\,000\,000\,007\).

Ràng buộc

• \(1 \le N \le 1\,000\,000\).
• \(1 \le A_i,B_i \le 2N\) với mọi \(1 \le i \le N\).
• \(A_i<B_i\) với mọi \(1 \le i \le N\).
• \(2N\) số \(A_1,\ldots,A_N,B_1,\ldots,B_N\) đôi một khác nhau.

Phân nhóm

1. Subtask 1 (10 điểm): \(N \le 20\).
2. Subtask 2 (12 điểm): \(N \le 2\,000\).
3. Subtask 3 (56 điểm): \(N \le 100\,000\).
4. Subtask 4 (22 điểm): Không có ràng buộc bổ sung.

Giới hạn

• Thời gian: 3.5 giây.
• Bộ nhớ: 1024 MB.

Ví dụ

4
1 3
2 5
4 8
6 7

4

3
1 4
2 5
3 6

0

5
1 4
2 10
6 9
7 8
3 5

8

8
1 15
2 5
3 8
4 6
14 16
7 9
10 13
11 12

16