Banca Dudașu are forma unei matrice cu linii și coloane. Fiecare element al matricei reprezintă o cameră iar fiecare cameră are uși care realizează comunicarea cu exteriorul sau cu camerele vecine. O bandă formată din 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 trasee nu este relevant ce traseu va parcurge fiecare dintre cei 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 hoți trebuie să participe la spargere.
Cerință
Cunoscând 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 al acestui număr.
Date de intrare
Pe prima linie a fișierului de intrare labirint.in se va afla un singur număr natural cu semnificația din enunț.
Date de ieșire
În fișierul de ieșire labirint.out se va afișa un singur număr natural care va reprezenta restul modulo a numărului de variante în care poate fi realizat planul spargerii.
Restricții si precizări
- ;
- Dudașu = localitate din apropierea municipiului Drobeta Turnu-Severin.
Exemplu
labirint.in
3
labirint.out
9
Explicație
Una dintre cele 9 soluții posibile este:
