У Фермера Джона есть большое поле, и он собирается посадить в некоторых его местах
сладкую пшеницу. ФД представил поле квадратом с размерами \((N-1) \times (N-1)\).
Юго-западный угол поля имеет координаты \((0,0)\), а северо-восточный конец поля
имеет координаты \((N-1,N-1)\).
В некоторых целочисленных координатах имеются двухглавые разбрызгиватели,
оба разбразгивают воду и удобрения. Разбрызгиватель в координатах \((i,j)\)
разбрызгивает воду на часть поля к северу и востоку от себя и разбрызгивает
удобрения к югу и западу от себя. Формально, он поливает водой все вещественные
координаты \((x,y)\) для которых \(N \geq x \geq i\) и \(N \geq y \geq j\), и удобряет
все вещественные координаты \((x,y)\) для которых \(0 \leq x \leq i\) and \(0 \leq y \leq j\).
Фермер Джон хочет засадить сладкой пшеницей некоторые прямоугольные области,
параллельные осям координат, с углами в целочисленных координатах. Однако,
чтоыб сладкая пшеница росла, надо чтобы все точки такого прямоугольника поливались
и удобрялись. И конечно, прямоугольник должен иметь положительную площадь.
Помогите ФД определить количество прямоугольников с положительной площадью,
на которых он может растить сладкую пшеницу. Поскольку число может быть очень
большим, выводите его по модулю \(10^9 + 7\).
ФОРМАТ ВВОДА (файл sprinklers.in):
Первая строка ввода содержит целое число
\(N\), определяющее размер поля.
(
\(1 \leq N \leq 10^5\)).
Каждая из последующих \(N\) строк содержит два разделённых пробелом целых числа
\(i\) и \(j\), (\(0 \leq i,j \leq N-1\)), они обозначают, что разбрызгиватель находится
в позиции \((i,j)\).
Гарантируется, что ровно один разбрызгиватель находится в каждой колонке и
ровно один разбрызгиватель находится в каждой строке. То есть, никакие два
разбрызгивателя не имеют одинаковую \(x\)-координату, и никакие два разбрызгивателя
не имеют одинаковую \(y\)-координату.
ФОРМАТ ВЫВОДА (файл sprinklers.out):
Вывод должен содержать одно целое число - количество прямоугольников положительной
площади, которые полностью поливаются и удобряются, по модулю \(10^9 + 7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
0 4
1 1
2 2
3 0
4 3
|
21
|