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 200x200!

!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:

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