Фермер Джон имеет на своей ферме \(N\)(\(2 \leq N \leq 2\cdot 10^5\)) коров,
последовательно пронумерованных \(1 \dots N\). Корова \(i\) расположена
в целочисленных координатах \((x_i, y_i)\) (\(1\le x_i,y_i\le N\)).
ФД хочет выбрать две команды для игры в мумбол.
Одна из команд будет "красная команда"; другая - "синяя".
Имеется несколько требований к командам.
Ни одна команда не будет пустая.
Каждая из коров должна быть не более чем в одной команде (возможно ни в одной).
Команды могут быть разделены горизонтальной или вертикальной прямой на плоскости
с нецелочисленной координатой, например, \(x = 0.5\).
Помогите ФД. Вычислите количество способов составить пару из красной и синей
команды, при выполнении вышеуказанных ограничений. Ответ выводить по модулю
\(10^9+7\).
ФОРМАТВВОДА (с клавиатуры / stdin):
Первая строка содержит одно целое число
\(N.\)
Каждая из последующих \(N\) строк содержит два разделённых одиночным
пробелом целых числа \(x_i\) и \(y_i\). Гарантируется, что \(x_i\) формирует
перестановку чисел из интервала \(1\dots N\), аналогично и \(y_i\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Одно целое число, обозначающее количество способов выбрать красную и синюю команды
удовлетворяющие указанным выше ограничениям - по модулю \(10^9+7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 2
2 1
|
2
|