labirint

Labirint

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

Poveste şi cerinţă...

Banca $Dudaşu$ are forma unei matrice cu $N$ linii şi $6$ coloane. Fiecare element al matricei reprezintă o cameră iar fiecare cameră are $4$ uşi care realizează comunicarea cu exteriorul sau cu camerele vecine. O bandă formată din $N+6$ hoţi vrea să dea o spargere la această bancă, dar pentru asta le trebuie un plan care să ţină cont de sistemele de securitate ale băncii. Fiecare hoţ va trebui sa intre printr-o uşa exterioară, să treacă printr-una sau mai multe camere şi sa părăsească banca printr-o altă uşa exterioara. Un hoţ nu are voie să treacă de două ori prin aceeaşi cameră. Doi hoţi diferiţi nu au voie să treacă prin aceeaşi cameră. Prin fiecare cameră trebuie sa treacă exact un hoţ. Pentru un plan de atac sensul în care un hoţ îşi parcurge traseul nu este relevant. Odată fixate cele N+6 trasee nu este relevant ce traseu va parcurge fiecare dintre cei N+6 hoţi. Se observă că, din modul in care e conceput un plan rezultă că fiecare uşă exterioara trebuie să fie folosită şi toţi cei $N+6$ hoţi trebuie să participe la spargere.
 
h2. Cerinta
 
Cunoscând $N$ să se calculeze în câte moduri poate fi realizat planul. Deoarece numărul calculat poate fi foarte mare se va afişa restul $modulo 44449$ al acestui număr.

h2. Date de intrare

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

Pe prima linie a fişierului de intrare $labirint.in$ se va afla un singur număr natural $N$ cu semnificaţia din enunţ.

h2. Date de ieşire

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

În fişierul de ieşire $labirint.ou$t se va afişa un singur număr natural care va reprezenta restul $modulo 44449$ a numărului de variante în care poate fi realizat planul spargerii.

h2. Restricţii

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

* $1 ≤ N ≤ 100000$
* $Dudaşu$=localitate din apropierea municipiului Drobeta Turnu-Severin.

h2. Exemplu

table(example). |_. labirint.in |_. labirint.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie

table(example). |_. labirint.in |_. labirint.out |_. Exemplu |
| 3
| 9
| Una dintre cele 9 soluţii posibile este:
!problema/labirint?image.png!
|

...

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