Оросители
У фермера Джона есть большое поле, и он подумывает о том, чтобы на какой-то его части засеять сладкую кукурузу. Изучив свое поле, ФД обнаружил, что оно образует квадрат (n − 1) * (n − 1). Юго-западный угол находится в координате (0, 0), а северо-восточный угол находится в (n - 1, n - 1 ).
В некоторых целочисленных координатах есть двухголовые оросители, каждый из которых разбрызгивает воду и удобрения. Двунаправленный ороситель в координате (i, j) разбрызгивает воду на части поля к северу и востоку от него и разбрызгивает удобрения на части поля к югу и западу от него. Формально он поливает все координаты (x, y), для которых n ≥ x ≥ i и n ≥ y ≥ j, и удобряет все координаты (x, y), для которых 0 ≤ x ≤ i и 0 ≤ y ≤ j
Фермер Джон хочет посадить сладкую кукурузу в некотором выровненном по оси прямоугольнике на своем поле с целочисленными угловыми координатами. Однако для того, чтобы сахарная кукуруза росла, все точки в прямоугольнике необходимо поливать и удобрять двусторонними оросителями. И, конечно же, прямоугольник должен иметь положительную площадь, иначе фермер Джон не смог бы выращивать в нем кукурузу!
Помогите фермеру Джону определить количество прямоугольников положительной площади, на которых он мог бы выращивать сладкую кукурузу. Поскольку это число может быть большим, выведите остаток от этого числа по модулю 10^9 + 7.
Входные данные
Первая строка содержит число n (1 ≤ n ≤ 10^5) - размер поля. Каждая из следующих n строк содержит два целых числа. Если эти целые числа i и j, где 0 ≤ i, j ≤ n − 1, то они обозначают ороситель, расположенный в (i, j).
Гарантируется, что имеется ровно по одному оросителю в каждом столбце и ровно по одному оросителю в каждом ряду. То есть нет двух оросителей с одинаковой координатой x, и нет двух оросителей с одинаковой координатой y.
Выходные данные
Выведите единственное целое число: количество прямоугольников положительной площади, которые полностью орошены и полностью удобрены, по модулю 10^9 + 7.