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

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á \(5\).
• \(1 \le N \le 10^5\)
• \(1 \le S \le E \le 10^9\) (một buổi có thể có độ dài \(0\))

Sample Input

4
2 5
5 5
5 9
1 2
3
7 7
7 7
7 7
2
1 8
2 3
-1

Sample Output

00000015
00000007
00000002

Explanation

Bộ test thứ hai: ba buổi đều là \([7,7]\) (độ dài \(0\)), đôi một xếp được cùng nhau nên mọi tập khác rỗng đều hợp lệ: \(2^3-1=7\). Bộ test thứ ba: hai buổi lồng nhau nên chỉ chọn được từng buổi một, có \(2\) tập.