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

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

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

h2. Exemplu
table(example). |_. dreptunghi4.in |_. dreptunghi4.out |

| 4
  1 2
  1 10
  2 2
  3 4
| 2
  89
  7
  823

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

La primul test avem un grid format dintr-un singur rând şi două coloane. Acesta poate fi pavat în două moduri: cu două piese $1x1$ sau cu o singură piesă $1x2$.

...

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