rectangles

„Lumea reală este oribilă și cumplită.”

Într-un final, Alex s-a decis să se întoarcă acasă ... dar totuși, care casă? Acesta încă nu și-a construit casa. Orășelul Jluc poate fi privit ca și o matrice de M × M. Alex dorește să își construiască o casă într-o sub-matrice a acestei matrici. Totuși, pe drum spre Piezișă, el a pus capcane în N celule ale matricei (cu cât mai puțini oameni ajung pe Piezișă, cu atât mai mult lapte pentru Alex). Evident, el nu dorește să își construiască casa pe niște capcane (și pe deasupra, capcanele încă pot fi folositoare), așa că se întreabă în câte moduri își poate construi casa.

Protocol de interacțiune

Pentru a rezolva problema, trebuie să implementați funcția:

int countRectangles(int M, std::vector <std::pair <int , int >> points );

M reprezintă dimensiunea matricei, iar parametrul points reprezintă celulele în care se află capcanele. Valoarea returnată este numărul de dreptunghiuri totale, modulo 6700417. Funcția va fi apelată o singură dată pe test.

Restricţii

• 0 ≤ N ≤ 200 000
• $1 ≤ M ≤ 10^9$
• $0 ≤ x_i, y_i < M$ pentru oricare 0 ≤ i ≤ N − 1
• $x_i ≠ x_j$ sau $y_i ≠ y_j$ pentru oricare i ≠ j
• Atenție! punctajele la această problemă au fost generate în mod aleatoriu.
• Trebuie să includeți "rectangles.h"

Subtask 1 (2 puncte)

• 1 ≤ M ≤ 20

Subtask 2 (4 puncte)

• 1 ≤ M ≤ 100

Subtask 3 (7 puncte)

• 0 ≤ N ≤ 20

Subtask 4 (4 puncte)

• 1 ≤ M ≤ 700

Subtask 5 (8 puncte)

• 0 ≤ N ≤ 80

Subtask 6 (3 puncte)

• $1 ≤ M^2N ≤ 50 \ 000 \ 000$

Subtask 7 (9 puncte)

• 0 ≤ N ≤ 700

Subtask 8 (2 puncte)

• 1 ≤ M ≤ 1 600

Subtask 9 (4 puncte)

• 1 ≤ M ≤ 5 000

Subtask 10 (4 puncte)

• 1 ≤ M ≤ 25 000 și 0 ≤ N ≤ 2 500

Subtask 11 (5 puncte)

• 0 ≤ N ≤ 3 000

Subtask 12 (10 puncte)

• 0 ≤ N ≤ 5 000

Subtask 13 (9 puncte)

• 0 ≤ N ≤ 20 000 și 1 ≤ M ≤ 200 000

Subtask 14 (8 puncte)

• 0 ≤ N ≤ 20 000

Subtask 15 (21 puncte)

• Nu există alte restricții

Exemple

stdin

3 2
0 1
2 2

stodut

17

Explicații

Matricea arată astfel:

o # o
o o o
o o #

Sunt:
7 sub-matrice de 1×1
3 sub-matrice de 1×2
1 sub-matrice de 1×3
4 sub-matrice de 2×1
1 sub-matrice de 3×1
1 sub-matrice de 2×2

stdin

5 3
1 2
2 2
2 3

stodut

108

Explicații

În total sunt 108 sub-matrice

stdin

1000000000 0

stdout

1974342