3-й этап Республиканской олимпиады по информатике 2022-2023, 1й тур

Задача C. Суммарная площадь

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

Альтаиру часто дарят интересные подарки. На этот раз Ариф подарил множество различных точек на плоскости, он конечно поблагодарил Арифа. Но он совсем не знает что делать с этими точками, поэтому он придумал задачу. Альтаир определил функцию $f(S)$, которая считает площадь минимального прямоугольника со сторонами параллельными осям координат, который покрывает все точки из множества $S$ (точка покрыта прямоугольником, когда находится внутри него или на его границе). Но подсчет такой функции кажется ему чем-то слишком простым и скучным, поэтому он хочет посчитать сумму значений функции $f$ по всем возможным непустым подмножествам точек. Так как Альтаир не умеет использовать большие числа, а ответ может быть уж слишком большим, поэтому нужно посчитать его остаток при делении на $10^9 + 7$.

Формат входного файла

В первой строке дано одно натуральное число $n$ ($1 <= n <= 10^5$) — количество точек в подарке. Далее следуют $n$ строк, в $i$-й записана пара чисел $x_i$, $y_i$ ($1 <= x_i, y_i <= 10^9$) — координаты $i$-й точки.

Формат выходного файла

Выведите одно число - ответ на задачу по модулю $10^9 + 7$.

Пример:

Вход

3
4 10
5 7
7 9

Ответ

19

Замечание

Рассмотрим пример. В этом примере есть 7 непустых подмножеств. Площадь прямоугольника для подножества из первой и второй точки: $f(\{1, 2\}) = 3$. $f(\{1\}) = f(\{2\}) = f(\{3\}) = 0$ $f(\{1, 2\}) = 3$ $f(\{1, 3\}) = 3$ $f(\{2, 3\}) = 4$ $f(\{1, 2, 3\}) = 9$ Сумма по всем $f(S)$ -- $19$. ( Altair Ashurov )

Комментарий/решение