Bedao Regular Contest 05 - DOMROOKS

Xem dạng PDF

Gửi bài giải


Điểm: 0,40 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

~Neko~ có ~1~ bàn cờ kích cỡ ~2*10^5 \times 2*10^5~ ô, trên bàn cờ được đặt sẵn ~n~ quân xe sao cho trên mỗi hàng và mỗi cột không có quá ~2~ quân xe. Cậu ta thấy rằng một hàng hoặc một cột được gọi là bị "thống trị" nếu như trên đó có duy nhất ~1~ quân xe. Biết rằng được phép chọn tùy ý một số các quân xe và bỏ chúng khỏi bàn cờ, bạn hãy giúp cậu ấy đếm số trạng thái bàn cờ sao cho không có hàng hoặc cột bị thống trị.

Input

  • Dòng đầu tiên chứa số nguyên ~n~ là số quân xe ~( 1 \leq n \leq 2*10^5 )~
  • ~n~ dòng tiếp theo, mỗi dòng gồm ~1~ cặp số nguyên ~(x, y)~ lần lượt là tọa độ hàng và cột của một quân xe, đảm bảo không có 2 quân xe ở cùng vị trí.

Output

  • Một số duy nhất là số trạng thái bàn cờ thỏa mãn yêu cầu, do đáp án có thể rất lớn nên in ra kết quả với phần dư của phép chia ~10^9+7~

Sample Input

5
1 1
5 5
1 5
5 1
3 3

Sample Output

2

Subtask

  • ~20~% số test với ~1 \le n \le 10~.
  • ~80~% số test tiếp theo không ràng buộc gì thêm.

Note

Bỏ quân xe ở tọa độ ~(3, 3)~ hoặc bỏ toàn bộ các quân xe.


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.