turnuri5

Turnuri5

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

* 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.

* Se vor acorda $10$ puncte din oficiu (testele 19 şi 20 sunt din exemple).

* 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") ==