* $HkC{~1~}C{~2~}$ – se trasează linia *orizontală* la poziţia $k$, se segmentează şi numerotează dreptunghiul de sus conform codului $C{~1~}$, apoi se continuă cu segmentarea şi numerotarea dreptunghiului de jos conform codului $C{~2~}$;
* $VkC{~1~}C{~2~}$ – se trasează linia *verticală* la poziţia $k$, se segmentează şi numerotează dreptunghiul din stânga conform codului $C{~1~}$, apoi se continuă cu segmentarea şi numerotarea dreptunghiului din dreapta conform codului $C{~2~}$.

De exemplu, dreptunghiul de dimensiuni $8 \times 6$ (8 linii, 6 coloane) segmentat şi numerotat conform codului

!>problema/dreptunghi3?dreptunghi.png!
 
De exemplu, dreptunghiul de dimensiuni $8 * 6$ (8 linii, 6 coloane) segmentat şi numerotat conform codului

$C = H5H3V2**V3**V5V2***$,  va arăta ca în _Figura 1 (dreapta)_.

!>problema/dreptunghi3?dreptunghi.png!

Un cod de segmentare şi numerotare $C$ este *valid* pentru un dreptunghi de dimensiuni $N * M$ dacă şi numai dacă pentru fiecare operaţie de tipul $HkC{~1~}C{~2~}$ şi de tipul $VkC{~1~}C{~2~}$ din cadrul lui $C$, poziţia $k$ la care se trage linia orizontală, sau verticală respectiv, se află *strict* în interiorul dreptunghiului curent (adică pe *ambele* părţi ale liniei trasate există cel puţin o linie si cel puţin o coloană rămase care vor fi ulterior numerotate conform definiţiei recursive a codului $C$).

h2. Date de ieşire

* *Dacă valoarea citită pentru $P$ este 1*, atunci în fişierul de ieşire $dreptunghi3.in$ se va tipări numărul de subdiviziuni pe care codul $C$ le generează;
* *Dacă valoarea citită pentru $P$ este 2*, atunci în fişierul de ieşire $dreptunghi3.in$ se vor tipări două numere $N$ şi $M$ separate printr-un spaţiu, dimensiunile unui dreptunghi de arie minimă pentru care codul $C$ citit este valid. În caz că există mai multe se acceptă oricare;
* *Dacă valoarea citită pentru $P$ este 3*, atunci în fişierul de ieşire $dreptunghi3.in$ se va tipări numărul de codificări distincte *modulo 1 000 000 007* echivalente cu codul citit (in acest număr va fi inclus şi codul $C$ citit).
* *Dacă valoarea citită pentru $P$ este 4*, atunci în fişierul de ieşire $dreptunghi3.in$ se va tipări primul cod în ordine lexicografică echivalent cu cel dat;

* *Dacă valoarea citită pentru $P$ este 1*, atunci în fişierul de ieşire $dreptunghi3.out$ se va tipări numărul de subdiviziuni pe care codul $C$ le generează;
* *Dacă valoarea citită pentru $P$ este 2*, atunci în fişierul de ieşire $dreptunghi3.out$ se vor tipări două numere $N$ şi $M$ separate printr-un spaţiu, dimensiunile unui dreptunghi de arie minimă pentru care codul $C$ citit este valid. În caz că există mai multe se acceptă oricare;
* *Dacă valoarea citită pentru $P$ este 3*, atunci în fişierul de ieşire $dreptunghi3.out$ se va tipări numărul de codificări distincte *modulo 1 000 000 007* echivalente cu codul citit (in acest număr va fi inclus şi codul $C$ citit).
* *Dacă valoarea citită pentru $P$ este 4*, atunci în fişierul de ieşire $dreptunghi3.out$ se va tipări primul cod în ordine lexicografică echivalent cu cel dat;

h2. Restricţii