Bedao Regular Contest 05 - DOMROOKS

View as PDF

Submit solution


Points: 0.40 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
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.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.