Farmer John muốn tạo một đồng cỏ hình tam giác cho đàn bò của mình.

Có \(N\) cọc hàng rào (\(3\le N\le 10^5\)) nằm tại các điểm phân biệt \((X_1,Y_1),\ldots,(X_N,Y_N)\) trên bản đồ hai chiều của trang trại. Ông có thể chọn ba cọc làm các đỉnh của đồng cỏ hình tam giác, miễn là một cạnh của tam giác song song với trục \(x\) và một cạnh khác song song với trục \(y\).

Tổng diện tích của tất cả các đồng cỏ mà FJ có thể tạo là bao nhiêu?

Phân nhóm

• Test 2 thỏa mãn \(N=200\).
• Các test 3-4 thỏa mãn \(N\le 5000\).
• Các test 5-10 không có ràng buộc bổ sung.

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(X_i\) và \(Y_i\), mỗi số thuộc đoạn \(-10^4\ldots 10^4\), mô tả vị trí của một cọc hàng rào.

Dữ liệu ra

Vì tổng diện tích không nhất thiết là số nguyên và có thể rất lớn, hãy in phần dư khi hai lần tổng diện tích được chia cho \(10^9+7\).

Ví dụ

4
0 0
0 1
1 0
1 2

3

Nguồn

USACO 2020 February Contest, Silver - Triangles: https://usaco.org/index.php?page=viewproblem2&cpid=1015

Tác giả: Travis Hance và Nick Wu.