Một đoạn thẳng được mô tả bằng một cặp số nguyên \(\lbrack l,r\rbrack\). Hai đoạn thẳng được gọi là giao nhau nếu chung có ít nhất một điểm chung.

Một tập đoạn tốt là một tập các đoạn thẳng sao cho với mỗi đoạn thẳng trong tập, đều giao nhau với ít nhất một đoạn thẳng khác trong tập đó (coi tập đoạn thẳng chỉ có một đoạn thẳng duy nhất là tập đoạn tốt). Ví dụ, tập \(\{\lbrack 1,3\rbrack,\lbrack 4,5\rbrack,\lbrack 5,7\rbrack,\lbrack 3,4\rbrack\}\) hay \(\{\lbrack 1,4\rbrack,\lbrack 2,3\rbrack\}\) là một tập đoạn tốt, còn \(\{\lbrack 1,4\rbrack,\lbrack 3,5\rbrack,\lbrack 6,7\rbrack\}\) thì không phải là tập đoạn tốt. Độ tốt của một tập đoạn tốt là số lượng các đoạn trong tập đó.

Lưu ý: Hai tập đoạn tốt có ít nhất một điểm chung sẽ gộp thành một tập đoạn tốt.

Yêu cầu: Ban đầu tập đoạn thẳng không có đoạn thẳng nào. Cho \(n\) đoạn thẳng, mỗi lần lấy một đoạn thẳng theo thứ tự thêm vào tập đoạn thẳng, yêu cầu tính tích độ tốt của tập đoạn tốt được sinh ra từ tập đoạn thẳng hiện tại. Do kết quả rất lớn, in ra phần dư của đáp án sau khi chia cho \(10^{9} + 7\)

Dữ liệu vào:

+ Dòng dầu tiên chứa số nguyên dương \(n\ (n \leq 10^{5})\) là số đoạn thẳng lần lượt được thêm vào;

+ \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(l,r\ (l \leq r \leq 10^{9})\) mô tả một đoạn thẳng.

Kết quả:

+ Gồm \(n\) dòng, dòng thứ \(i\ (1 \leq i \leq n)\) chứa một số nguyên là kết quả theo yêu cầu đề bài khi thêm đoạn thẳng thứ \(i\).

Ví dụ:

Ràng buộc:

+ Có 20% số test ứng với 20% số điểm thỏa mãn: \(l = r;n \leq 30\);

+ Có 20% số test khác ứng với 20% số điểm thỏa mãn: \(r \leq 1000\);

+ Có 30% số test khác ứng với 30% số điểm thỏa mãn: n\(\leq 2000\);

+ Có 30% số test còn lại ứng với 30% số điểm không có ràng buộc gì thêm.