Ngân thích nhiều hoạt động. Cô thích nhào lộn, giả kim thuật, bắn cung, nghệ thuật, khiêu vũ Ả Rập, và nhiều hơn nữa. Cô tham gia một câu lạc bộ cung cấp một số lớp học. Mỗi lớp có một khoảng thời gian trong mỗi tuần. Ngân muốn đăng ký nhiều lớp, nhưng vì chúng trùng nhau về thời gian, cô tìm một tập hợp các lớp không chồng chéo để tham dự. Một tập hợp con không chồng chéo nếu nó không chứa hai lớp trùng nhau về thời gian. Nếu một lớp bắt đầu tại thời điểm một lớp khác kết thúc điều này không được coi là chồng chéo.

Ngân quyết định đếm tất cả các tập con không chồng chéo của các lớp. Sau đó cô ấy sẽ chọn tập hợp con cô ấy thích nhất. Cô ấy muốn bạn trợ giúp tính toán có bao nhiêu tập con này. Bạn hãy viết chương trình nhận đầu vào là danh sách \(N\) lớp học với thời gian bắt đầu và kết thúc. Hãy tính giúp cho cô ấy có bao nhiêu tập con không chồng chéo.

Dữ liệu vào

• Mỗi trường hợp thử nghiệm được mô tả bằng cách sử dụng một số dòng. Dòng đầu tiên chứa một số nguyên \(N\) cho biết số lượng các lớp mà câu lạc bộ cung cấp \((1 \le N \le 3000)\)
• Mỗi \(N\) dòng tiếp theo mô tả một lớp sử dụng hai số nguyên \(S\) và \(E\) tương ứng với thời gian bắt đầu và kết thúc của lớp \((1 \le S \lt E \le 10^9)\)
• Kết thúc của đầu vào được chỉ định bằng một dòng chứa \(-1\)

Dữ liệu ra

• Đối với mỗi trường hợp thử nghiệm, xuất ra một dòng với một số nguyên duy nhất biểu thị số tập con không chồng chéo. Bạn chỉ cần xuất 8 chữ số cuối của kết quả. Nếu kết quả có ít hơn 8 chữ số, hãy viết nó với các số 0 đứng đầu để đủ 8 chữ số.

Input 1

5
1 3
3 5
5 7
2 4
4 6
3
500000000 1000000000
1 500000000
1 500000000
1
999999999 1000000000
-1

Output 1

00000012
00000005
00000001