Фермер Джон хочет создать треугольное пастбище для своих коров.
Всего имеется N столбов забора (3 ≤ N ≤ 10
5) как различных (X
1,Y
1)…(X
N,Y
N) точек на карте фермы. Он может выбрать три из них чтобы сформировать вершины треугольного пастбища, но так чтобы одна из сторон была параллельна оси x, а другая - параллельно оси y.
Какова сумма площадей всех возможных пастбищ, которые может сформировать ФД?
Входные данные
Первая строка содержит N.
Каждая из последующих N строк содержит два целых числа Xi и Yi, каждое в интервале −10
4…10
4 включительно, описывающих положение столба.
Выходные данные
Поскольку сумма площадей может быть числом не целым и очень большим, выведите остаток от деления удвоенной суммы площадей на 10
9+7.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
4
0 0
0 1
1 0
1 2
|
3 |
Точки (0,0), (1,0), (1,2) образуют треугольник с площадью 1.
Точки (0,0), (1,0), (0,1) образуют треугольник с площадью 0.5.
Поэтому ответ 2⋅(1+0.5)=3. |