Hội hoa

View as PDF

Submit solution

Points: 0.86 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VNOI Online 2011Tác giả: Khúc Anh Tuấn
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Năm ~2011~, thành phố quyết định tổ chức một lễ hội hoa xuân. Trong lễ hội, có ~N~ giỏ hoa được trưng bày tại các vị trí (~x_1, y_1~), (~x_2, y_2~), ..., (~x_n, y_n~). Để ngăn chặn tình trạng hái trộm hoa, một hàng rào được dựng lên thỏa mãn ~2~ điều kiện sau:

  • Tất cả ~N~ giỏ hoa đều nằm trong hoặc trên biên của hàng rào.

  • Hàng rào có dạng hình chữ nhật với các cạnh song song với trục tọa độ và chu vi nhỏ nhất có thể.

Ngoài ra, thành phố còn xét đến trường hợp các giỏ hoa bị lấy cắp. Do đã có sẵn hàng rào, chỉ các trường hợp lấy cắp mà không làm ảnh hưởng đến hàng rào mới được tính đến. Ví dụ, nếu ta có ~4~ giỏ hoa ở vị trí ~(1, 1)~, ~(1, 2)~, ~(2, 2)~, ~(3, 3)~, hàng rào sẽ là hình chữ nhật ~[(1, 1)-(3, 3)]~. Lấy cắp giỏ hoa thứ ~2~ và thứ ~3~ sẽ không làm thay đổi hàng rào. Tuy nhiên, nếu lấy cắp giỏ hoa thứ nhất và thứ ~3~, hàng rào sẽ trở thành hình chữ nhật ~[(1, 2)-(3, 3)]~. Có tất cả ~3~ khả năng lấy cắp trong ví dụ này: lấy giỏ ~2~, lấy giỏ ~3~ hoặc lấy cả ~2~ giỏ ~2~ và ~3~.

Nhiệm vụ của bạn là phải đếm số trường hợp được tính đến. Hai trường hợp khác nhau nếu có ~1~ giỏ hoa bị lấy cắp ở trường hợp này nhưng không bị lấy cắp ở trường hợp kia.

Input

  • Dòng đầu ghi số ~N~. ~(1 \le N \le 100)~
  • ~N~ dòng sau, mỗi dòng ghi cặp số tự nhiên (xi, yi), không có ~2~ giỏ hoa cùng nằm ở một vị trí. ~(1 \le~ xi, yi ~\le 10000)~

Output

  • Gồm một số duy nhất là số trường hợp được tính đến. Do kết quả có thể rất lớn, bạn chỉ cần in ra theo modulo ~1000000007~.

Giới hạn

  • ~50\%~ số test có ~N \le 20~.

Sample Input

4
1 1
1 2
2 2
3 3

Sample Output

3

Comments

Please read the guidelines before commenting.


There are no comments at the moment.