Решения: Республиканская олимпиада, Областной этап

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$ -й точки.

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