Xếp lịch học không trùng

Một trung tâm ngoại ngữ mở \(N\) buổi học ngoại khoá, buổi thứ \(i\) diễn ra từ thời điểm \(S_i\) đến thời điểm \(E_i\). Bạn Lan muốn tham gia một số buổi trong đó, nhưng không muốn bị trùng giờ.

Hai buổi học được gọi là xếp được cùng nhau nếu buổi này kết thúc không muộn hơn thời điểm buổi kia bắt đầu (buổi này kết thúc đúng lúc buổi kia bắt đầu vẫn hợp lệ). Một tập các buổi học là hợp lệ nếu mọi cặp buổi trong tập đều xếp được cùng nhau. Tập rỗng không được tính.

Hãy đếm số tập khác rỗng các buổi học hợp lệ. Hai tập khác nhau nếu chúng chứa những chỉ số buổi học khác nhau (hai buổi có cùng \(S, E\) vẫn được xem là hai buổi khác nhau).

Vì đáp số có thể rất lớn nên chỉ in ra 8 chữ số cuối cùng của kết quả; nếu kết quả có ít hơn 8 chữ số thì thêm các chữ số \(0\) vào đầu cho đủ 8 chữ số.

Input

Dữ liệu gồm nhiều bộ test, kết thúc bằng một dòng chứa \(-1\). Mỗi bộ test gồm:

Dòng đầu chứa số nguyên \(N\) là số buổi học.
\(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(S\) và \(E\) là thời điểm bắt đầu và kết thúc của một buổi.

Output

Với mỗi bộ test, in ra một dòng gồm đúng 8 chữ số là 8 chữ số cuối của số tập hợp lệ (có thể có các số \(0\) ở đầu).

Constraints

Số bộ test không quá \(20\).
\(1 \le N \le 3000\)
\(1 \le S < E \le 10^9\)

Sample Input

Sample Output

00000007
00000002
00000005

Explanation

Bộ test đầu: có 4 tập một buổi và 3 tập hai buổi hợp lệ là \(\{1,4\}\), \(\{2,3\}\), \(\{2,4\}\) (theo chỉ số), tổng cộng \(7\). Bộ test thứ hai: hai buổi trùng nhau hoàn toàn nên chỉ có 2 tập một buổi. Bộ test thứ ba: buổi 1 \([20,30]\) ghép được với buổi 2 \([1,20]\) và buổi 3 \([1,10]\), còn buổi 2 và 3 trùng nhau, nên có \(3 + 2 = 5\) tập.

Điều hướng chính

Ngôn ngữ

Phím tắt