Se citeste un numar natural n . Determinati, folosind Programarea Dinamica, in cate moduri distincte poate fi acoperit complet, fara suprapuneri, un dreptunghi cu 3 linii si n coloane, folosind piese domino de dimensiune 1x2. Daca n este impar, o astfel de acoperire este imposibila.
- Date de intrare
- Se citeste numarul natural n.
- Date de iesire
- Se afiseaza un singur numar: numarul de acoperiri posibile (0 daca n este impar).
- Restrictii
- 0 <= n <= 30
Exemple
Exemplul 1
Intrare
0
Iesire
1
Exemplul 2
Intrare
2
Iesire
3