== include(page="template/taskheader" task_id="dreptunghi4") ==

Poveste şi cerinţă...

Se consideră un grid dreptunghiular cu $H$ rânduri si $W$ coloane. În câte moduri putem acoperi acest grid cu dreptunghiuri mici de dimensiune $1x1$, $1x2$ sau $2x1$? Fiecare celulă trebuie să fie acoperită exact o dată. Calculaţi rezultatul modulo 10^9^+7.

h2. Date de intrare

Fişierul de intrare $dreptunghi4.in$ ...

Fişierul de intrare $dreptunghi4.in$ conţine pe prima linie numărul de teste $T$. Fiecare test este format dintr-o singură linie, ce conţine numerele întregi $H$ şi $W$ separate prin spaţiu.

h2. Date de ieşire

În fişierul de ieşire $dreptunghi4.out$ ...

În fişierul de ieşire $dreptunghi4.out$ afişaţi pentru fiecare test numărul cerut.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $0 ≤ T ≤ 100$
* $0 < H, W &le; 1000$
* $min(H, W) &le; 6$

h2. Exemplu