Bulănel îşi propune să deseneze dreptunghiuri pe foaia primită, însă acestea trebuie să fie valide. Dreptunghiurile valide trebuie să aibă arie strict mai mare decât $0$, să aibă colţurile în punctele existente, să aibă laturile paralele cu marginile foii şi să nu aibă nici un punct comun cu niciunul din turnuri.
!problema/turnuri5?fin.jpg 250x250!
De exemplu, dacă Bulănel primeşte o foaie cu $N=5$ linii şi $M=6$ coloane şi un singur turn cu înălţime $h{~1~}=2$ care se întinde de la $l{~1~}=2$ la $r{~1~}=3$, atunci el poate desena dreptunghiuri cum ar fi:
* dreptunghiul care are colţul stânga sus pe linia $4$, coloana $0$ şi colţul dreapta jos pe linia $3$, coloana $1$.
h2. Date de intrare
Fişierul de intrare $turnuri.in$ conţine pe prima linie trei numere naturale $N$ $M$ şi $T$ care reprezintă, $N$ - numărul de linii, $M$ - numărul de coloane şi $T$ - numărul de turnuri.
Fişierul de intrare $turnuri5.in$ conţine pe prima linie trei numere naturale $N$ $M$ şi $T$ care reprezintă, $N$ - numărul de linii, $M$ - numărul de coloane şi $T$ - numărul de turnuri.
Pe următoarele $T$ linii se află turnurile. Pe linia $i$ se găsesc trei numere naturale $h{~i~}$, $l{~i~}$ şi $r{~i~}$ care reprezintă $h{~i~}$ - înălţimea turnului, $l{~i~}$ - capătul stâng al intervalului turnului pe coloane, $r{~i~}$ - capătul drept al intervalului turnului pe coloane.
h2. Date de ieşire
Fişierul de ieşire $turnuri.out$ trebuie să conţină o linie. Pe aceea linie se afla un număr natural D care reprezintă numărul de dreptunghiuri valide pe care le poate desena $modulo 10^9^ + 7$.
Fişierul de ieşire $turnuri5.out$ trebuie să conţină o linie. Pe aceea linie se afla un număr natural D care reprezintă numărul de dreptunghiuri valide pe care le poate desena $modulo 10^9^ + 7$.
h2. Restricţii
* 2 ≤ N, M ≤ 109
* 0 ≤ T ≤ 100 000
* 0 ≤ hi ≤ N - 1, 0 ≤ li < ri ≤ M - 1
* $2 ≤ N, M ≤ 10^9^$
* $0 ≤ T ≤ 100 000$
* $0 ≤ hi ≤ N - 1, 0 ≤ li < ri ≤ M - 1$
* Două dreptunghiuri sunt diferite dacă colţul stânga sus sau colţul dreapta jos diferă.
* Pentru teste în valoare de 5 puncte, se garantează N, M, T ≤ 10
* Pentru teste în valoare de 10 puncte, se garantează N, M ≤ 50, T ≤ 10
* Pentru teste în valoare de 20 puncte, se garantează N, M ≤ 100
* Pentru teste în valoare de 30 puncte, se garantează N, M ≤ 1 000
* Pentru teste în valoare de 50 puncte, se garantează N, T ≤ 1 000, M ≤ 109
* Problema va fi evaluată pe teste în valoare de 90 de puncte.
* Se vor acorda $10$ puncte din oficiu (testele 19 şi 20 sunt din exemple).
* Pentru teste în valoare de $5$ puncte, se garantează $N, M, T ≤ 10$
* Pentru teste în valoare de $10$ puncte, se garantează $N, M ≤ 50, T ≤ 10$
* Pentru teste în valoare de $20$ puncte, se garantează $N, M ≤ 100$
* Pentru teste în valoare de $30$ puncte, se garantează $N, M ≤ 1 000$
* Pentru teste în valoare de $50$ puncte, se garantează $N, T ≤ 1 000, M ≤ 10^9^$
* Problema va fi evaluată pe teste în valoare de $90$ de puncte.
* Exemplele vor reprezenta teste în valoare de $10$ puncte "din oficiu".
h2. Exemplu
table(example). |_. turnuri5.in |_. turnuri5.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 6 1
2 2 3
| 33
|
| 10 12 3
5 1 4
1 7 9
8 10 11
| 507
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="turnuri5") ==
