Un poliomino este o figură geometrică conexă formată din pătrate de arie cu vârfurile în puncte de coordonate întregi. Evident, pătratele au laturile paralele cu axele de coordonate. Două pătrate se numesc adiacente dacă au o latură comună. O figură este conexă dacă din orice pătrat al figurii se poate ajunge în orice alt pătrat, trecând printr-o succesiune de pătrate în care oricare două pătrate consecutive sunt adiacente.
Două poliominouri sunt considerate identice dacă unul poate fi obţinut din celălalt printr-o translaţie.
O latură orizontală a unui poliomino este formată dintr-o succesiune de pătrate de arie ale poliominoului, astfel încât oricare două pătrate consecutive au o latură verticală comună.
Un poliomino este orizontal-convex dacă orice linie orizontală (dreapta paralelă cu axa Ox) intersectează o singură latură orizontală a poliominoului sau niciuna.
De exemplu, poliominoul din Figura este orizontal convex, dar poliominoul din Figura nu este orizontal convex.
Cerinţă
Scrieţi un program care să determine numărul de poliominouri orizontal convexe de arie .
Date de intrare
Fişierul de intrare poli.in conţine o singură linie pe care se află un număr natural nenul .
Date de ieșire
Fişierul de ieşire poli.out conţine o singură linie pe care se află numărul de poliominouri orizontal convexe de arie .
Restricții și precizări
Exemplul 1
poli.in
3
poli.out
6
Exemplul 2
poli.in
9
poli.out
6466