primar

Primarul orașului tocmai a aprobat un proiect pentru construirea unui ștrand la periferia localității. Zona pe care se dorește a fi amplasat ștrandul se poate identifica cu planul 2D (infinit). Aceasta conține $N$ arbori, aflați la coordonate întregi, cu lățimea de $1$ metru. Nu există doi arbori la aceeași coordonată $x$ sau $y$. Mai exact, $x_i \neq x_j$ și $y_i \neq y_j$ pentru orice $i \neq j$.

Figura 1 din enunțul original al problemei primar.Mărește schema ↗

Ștrandul nu poate fi amplasat decât în locații de forma unui dreptunghi cu laturile paralele cu axele, care, din motive de sustenabilitate, nu trebuie să conțină în interiorul său niciunul dintre arbori.

Mai mult, deoarece bugetul pentru acest proiect este foarte generos, primarul este interesat doar de acele zone maximale (care nu pot fi extinse). Cu alte cuvinte, o regiune $S$ nu este validă dacă există o altă regiune $S' \neq S$ dreptunghiulară, cu laturile paralele cu axele, care nu conține niciun arbore, iar $S \subset S'$.

De exemplu, pentru cazul ilustrat în figura alăturată (primul din secțiunea de exemple) se disting două posibilități valide de amplasare a ștrandului: cea roșie (de arie $2 \times 6 = 12$) și cea albastră (de arie $4 \times 5 = 20$).

Care este suma ariilor tuturor regiunilor valide posibile?

Rezultatul se va afișa modulo $10^9 + 7$.

Date de intrare

Fișierul de intrare primar.in conține pe prima linie $N$, numărul de arbori. Pe următoarele $N$ linii se vor găsi câte două valori întregi $x_i$, $y_i$ ($1 \leq i \leq N$) separate printr-un spațiu, reprezentând coordonatele arborilor.

Date de ieșire

Fișierul de ieșire primar.out va conține un singur număr natural, reprezentând suma ariilor tuturor regiunilor valide, modulo $10^9 + 7$.

Restricții și precizări

• Pentru toate subtask-urile, $x_i \neq x_j$ și $y_i \neq y_j$, pentru orice $i \neq j$.

Exemplul 1

primar.in

5
1 4
4 3
2 2
6 6
3 9

primar.out

32

Exemplul 2

primar.in

2
1 1
2 3

primar.out

0

Exemplul 3

primar.in

7
1 1
2 5
4 2
3 7
8 3
9 6
10 4

primar.out

52