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.
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$.
* dreptunghiul care are colţul stânga sus pe linia $3$, coloana $0$ şi colţul dreapta jos pe linia $0$, coloana $1$.

- dreptunghiul care are colţul stânga sus pe linia $4$, coloana $0$ şi colţul dreapta jos pe linia $3$, coloana $1$.
- dreptunghiul care are colţul stânga sus pe linia $3$, coloana $0$ şi colţul dreapta jos pe linia $0$, coloana $1$.

În total el poate desena $33$ de astfel de dreptunghiuri care respectă proprietăţile cerute.

El nu poate desena, de exemplu:
* dreptunghiul cu colţul stânga sus pe linia $4$, coloana $0$ şi colţul dreapta jos pe linia $1$, coloana $4$.
* dreptunghiul cu colţul stânga sus pe linia $4$, coloana $0$ şi colţul dreapta jos pe linia $2$, coloana $2$.
* dreptunghiul cu colţul stânga sus pe linia $4$, coloana $0$ şi colţul dreapta jos pe linia $2$, coloana $4$.
 
Bulănel vă cere să-l ajutaţi să numere câte dreptunghiuri valide poate desena pe foaia primită. Deoarece acest număr poate fi foarte mare, se cere sa se afişeze $modulo 10{^9^} + 7$.
 

h2. Date de intrare