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

Một tập đoạn tốt là tập các đoạn thẳng sao cho với mỗi một đ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 \(\{[1, 3], [4, 5], [5, 7], [3, 4]\}\) hay \(\{[1, 4], [2, 3]\}\) là một tập đoạn tốt, còn \(\{[1, 4], [3, 5], [6, 7]\}\) 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 thẳng trong tập đó.

Lưu ý: Hai tập đoạn tốt có ít nhất một điểm chung sẽ được 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 các 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\).

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) (\(N \le 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 \le R \le 10^9\)) mô tả một đoạn thẳng.

Output

• Gồm \(N\) dòng, dòng thứ \(i\) (\(1 \le i \le 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\).

Example

6
1 3
4 5
5 7
3 4
8 10
9 11

1
1
2
4
4
8

Scoring

• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(L = R; N \le 30\).
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(R \le 1000\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(N \le 2000\).
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm không có ràng buộc gì thêm.