poly2

Poly2

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

Poveste şi cerinţă...

Un polyomino este o figură geometrică plană compactă formată din una sau mai multe piese de domino, pătrate egale de latură $1$. Două piese se consideră alăturate dacă au o latură comună.
!problema/poly2?1.jpg!
 
Două Polyominouri se consideră identice dacă sunt formate din acelaşi număr de piese şi au aceeaşi configuraţie sau configuraţia unuia se poate obţine prin oglindirea celuilalt. În caz contrar cele două Polyominouri se consideră distincte.
!problema/poly2?2.jpg!
 
Un polyomino poate fi rotit cu 90°, 180° şi 270°, în sens trigonometric. Prin rotaţie se obţin alte Polyominouri, nu neapărat identice cu cel inţial.
!problema/poly2?3.jpg!
 
Niciunul dintre aceste Polyominouri nu este identic cu cel iniţial.
Un polyomino este convex dacă prin parcurgerea succesivă a linilor sau coloanelor nu se întâlnesc găuri.
!problema/poly2?4.jpg!
 
Un polyomino este oblic convex (skew polyomino) dacă este convex şi prin parcurgerea succesivă a coloanelor de la stânga la dreapta acestea nu descresc în înălţime. Altfel spus, partea de jos a coloanei din stânga este întotdeauna mai mică sau egală ca înălţime cu partea de jos a coloanei din dreapta. În mod similar, partea de sus a coloanei din stânga este întotdeauna mai mică sau egală cu partea de sus a coloanei din dreapta.
!problema/poly2?5.jpg!
 
h2. Cerinţă
 
Să se determine numărul de Polyominouri oblice distincte care au perimetrul egal cu $2*N+2$. Acest număr poate să fie mare, de aceea ne interesează rezultatul modulo $30103$.

h2. Date de intrare

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

Fişierul de intrare $poly2.in$ conţine pe prima linie un număr natural $N$.

h2. Date de ieşire

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

Fişierul de ieşire $poly2.out$ conţine pe prima linie un număr natural ce reprezintă numărul de Polyominouri oblice care au perimetrul egal cu $2*N+2$, număr afişat modulo $30103$.

h2. Restricţii

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

* $2 ≤ N ≤ 500$

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

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

| 3
| 5

|
h3. Explicaţie

...

Sunt $5$ Polyominouri care respectă cerinţa:
!problema/poly2?exemplu.jpg!

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

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