Se considera un camp de iarba, un sistem de coordonate $xOy$ si doi tauri, Ollu si Bollu, care sunt legati printr-un fir extensibil si ascutit. Ei sunt initial localizati in punctul $(0, 0)$. Ambii se pot deplasa cu aceeasi viteza doar in $Nord$ si $Est$. Atunci cand se plimba, firul care ii leaga taie iarba pe care o intampina. Ei se deplaseaza in asa fel incat sa taie cat mai multa iarba folosind firul.
Exista si $N$ puncte unde poti pune cate o zambila. Taurii isi vor stabili traseul astfel incat sa viziteze toate zambilele puse de tine. Pentru a nu crea confuzie, trebuie sa alegi punctele unde pui zambilele astfel incat toate sa fie vizitabile, avand in vedere restrictia de mers doar in $Nord$ si $Est$ a taurilor. Am uitat sa precizez: Ollu si Bollu sunt cei mai destepti tauri, ei isi dau seama rapid cand incerci sa ii pacalesti. Din acest motiv, nu poti pune mai putine zambile decat numarul de maxim de zambile pe care le-ai putea pune in cea mai favorabila alegere a punctelor - altfel i-ai irita foarte tare pe Ollu si Bollu.
Exista si $N$ puncte unde poti pune cate o zambila. Taurii isi vor stabili traseul astfel incat sa viziteze toate zambilele puse de tine. Pentru a nu crea confuzie, trebuie sa alegi punctele unde pui zambilele astfel incat toate sa fie vizitabile intr-o singura parcurgere a campului, avand in vedere restrictia de mers doar in $Nord$ si $Est$ a taurilor. Am uitat sa precizez: Ollu si Bollu sunt cei mai destepti tauri, ei isi dau seama rapid cand incerci sa ii pacalesti. Din acest motiv, nu poti pune mai putine zambile decat numarul de maxim de zambile pe care le-ai putea pune in cea mai favorabila alegere a punctelor - altfel i-ai irita foarte tare pe Ollu si Bollu.
Pentru toate modurile corecte in care ai putea alege setul de puncte unde sa pui zambile din cele $N$, Bisisica (un fel de Miorita, doar ca mai incapatanata) calculeaza cantitatea de iarba pe care o vor taia taurii. La final, ea aduna toate aceste numere iar pe suma o denumeste cu numele sau. Care este restul la impartirea cu $10^9^ + 7$ a numarului ei?
Pentru toate modurile corecte in care ai putea alege setul de puncte unde sa pui zambile, Bisisica (un fel de Miorita, doar ca mai incapatanata) calculeaza cantitatea de iarba pe care o vor taia taurii cu firul lor daca isi propun sa viziteze zambilele alese. La final, ea aduna toate aceste numere iar pe suma o denumeste cu numele sau. Care este *restul la impartirea cu $10^9^ + 7$* a numarului ei?
h2. Date de intrare
Fişierul de intrare $bazar.in$ contine pe prima linie numarul $N$ de puncte. Pe urmatoarele $N$ linii se afla cate doua numere naturale, descriind coordonatele punctelor unde se poate afla cate o zambila.
Fişierul de intrare $bazar.in$ contine pe prima linie numarul $N$ de puncte. Pe urmatoarele $N$ linii se afla cate doua numere naturale nenule mai mici sau egale cu $10^9^$, descriind coordonatele punctelor unde se poate afla cate o zambila.
h2. Date de ieşire
În fişierul de ieşire $bazar.out$ se afla restul impartirii numarului $Bisisica$ la $10^9^ + 7$.
În fişierul de ieşire $bazar.out$ se afla *restul impartirii numarului $Bisisica$ la $10^9^ + 7$*.
h2. Restricţii
* $1 ≤ N ≤ 1.000.000$
* Pentru ~5% din punctaj, $N ≤ 7$
* Pentru ~10% din punctaj, $N ≤ 16$
* Pentru ~20% din punctaj, $N ≤ 1.000$
* Pentru ~65% din punctaj, $N ≤ 50.000$
* Pentru ~80% din punctaj, $N ≤ 200.000$
* $1 ≤ N ≤ 200.000$
* Pentru $4%$ din punctaj, $N ≤ 7$
* Pentru $9%$ din punctaj, $N ≤ 16$
* Pentru $23%$ din punctaj, $N ≤ 1.000$
* Pentru $44%$ din punctaj, punctele din input sunt relativ uniform distribuite in plan
* Punctele date in input sunt distincte doua cate doua
* Formal, un mod corect in care ai putea alege setul de puncte unde sa pui zambile corespunde unei submultimi de cardinal maxim a multimii de $N$ puncte date, astfel incat exista o ordonare a punctelor alese in asa fel incat coordonatele $X$, respectiv $Y$, sa fie simultan in ordine nedescrescatoare. Atentie: submultime de cardinal maxim inseamna altceva decat submultime maximala!
h2. Exemplu
table(example). |_. bazar.in |_. bazar.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 9
5 3
9 6
7 7
2 2
6 4
3 1
10 8
6 3
8 5
| 24
|
h3. Explicaţie
...
Numarul maxim de zambile ce pot fi puse pentru a putea fi vizitate dintr-o parcurgere este $7$. Sunt doua feluri de a alege $7$ puncte cu proprietatea ceruta.
Prima varianta de traseu: $(0, 0) - (3, 1) - (5, 3) - (6, 3) - (6, 4) - (8, 5) - (9, 6) - (10, 8)$
A doua varianta de traseu: $(0, 0) - (2, 2) - (5, 3) - (6, 3) - (6, 4) - (8, 5) - (9, 6) - (10, 8)$
Pentru ca taurii se vor deplasa astfel incat sa taie cat mai multa iarba, o posibila plimbare a lor, pentru prima varianta de traseu, este urmatoarea:
Initial, Ollu si Bollu se afla in punctul $(0, 0)$. Ollu se deplaseaza spre $Nord$, iar Bollu spre $Est$. Atunci cand Ollu ajunge in punctul $(0, 1)$, Bollu se afla in punctul $(1, 0)$, deoarece ei au aceeasi viteza. Daca Ollu s-ar deplasa in continuare spre $Nord$, nu ar mai putea ajunge la zambila aflata in punctul $(3, 1)$, deoarece el nu se poate deplasa decat spre $Nord$ sau $Est$. Asa ca isi schimba directie, merge spre $Est$, pana cand ajunge la zambila. Bollu, in schimb, atunci cand ajunge in punctul $(3, 0)$, trebuie sa se indrepte spre $Nord$, pentru ca altfel nu ar ajunge la prima zambila. Cei doi se intalnesc in punctul $(3, 1)$, se bucura de zambila, si isi continua drumul intr-un fel asemanator spre zambila din punctul $(5, 3)$. Practic, aria de iarba taiata pana la prima zambila este aceea a dreptunghiului cu colturile in $(0, 0)$ si $(3, 1)$. Similar, taurii vor taia iarba si din dreptunghiurile $(3, 1) - (5, 3), (5, 3) - (6, 3), (6, 3) - (6, 4), (6, 4) - (8, 5), (8, 5) - (9, 6), (9, 6) - (10, 8)$, rezultand intr-o arie totala de $12$.
In al doilea traseu, ariile dreptunghiurilor vizitate sunt, in ordine, $4 + 3 + 0 + 0 + 2 + 1 + 2 = 12$.
Bisisica aduna ariile obtinute pentru toate traseele corecte, deci $Bisisica = 12 + 12 = 24$.
In fisierul $bazar.out$ trebuie afisat *restul impartirii acestui numar la $10^9^ + 7$*. Conform teoremei impartirii cu rest, $24 = 1000000007 * 0 + {*24*}$, deci restul este $24$.
== include(page="template/taskfooter" task_id="bazar") ==
