Park
Jednog lijepog sunčanog dana Ivica se odlučio prošetati lokalnim parkom. U parku se nalazi ukupno N+1 fontana, od kojih je najveća u sredini parka. Okolne fontane su označene brojevima od 1 do N u smjeru obrnutom od kazaljke na satu, a središnja brojem N+1. N okolnih fontana je stazama povezano u krug. Također, svaka od njih je stazom povezana s središnjom fontanom. Tako park sadrži ukupno 2*N staza. Pojedine staze u parku nisu prohodne jer ih čiste i ureñuju lokalni dobrovoljci. Primjer parka s nekim
neprohodnim stazama dan je na desnoj slici.
Image: dsadsa
Primjer parka za N=6. ----------------- Isti park s nekim neprohodnim stazama.
Sve staze su prohodne.
Svoju šetnju Ivica počinje kod neke fontane. Zatim šeće stazama tako da nijednu fontanu ne posjeti dvaput i da nijednom stazom ne proñe dvaput. Šetnja završava kad se Ivica vrati do fontane od koje je krenuo. Napišite program koji odreñuje broj različitih šetnji koje Ivica može napraviti. Dvije šetnje su različite
ako ne sadrže sve iste staze (dakle, početna fontana i smjer kretanja nisu bitni). Za park na desnoj slici postoje tri različite šetnje: 1-2-3-7-6-1, 1-2-3-7-4-5-6-1, 4-5-6-7-4.
InputU prvom redu nalazi se prirodni broj N (2 ≤ N ≤ 100 000), broj "rubnih" fontana u parku. U svakom od sljedeća dva reda nalazi se niz od po N znakova '0' ili '1' koji opisuje prohodnost staza. Nula na nekoj poziciji u nizu označava da staza nije prohodna, dok jedinica označava da je prohodna.
Nizovi predstavljaju:
1. Prohodnost staza koje povezuju fontane u krug. Staze su dane redom obrnutim od kazaljke na satu, počevši sa stazom koja povezuje fontanu N s fontanom 1.
2. Prohodnost staza koje povezuju rubne fontane sa središnjom. Staze su također dane redom obrnutim od kazaljke na satu. Prvi znak označava prohodnost staze koja povezuje fontanu 1 sa središnjom.
Nizovi predstavljaju:
1. Prohodnost staza koje povezuju fontane u krug. Staze su dane redom obrnutim od kazaljke na satu, počevši sa stazom koja povezuje fontanu N s fontanom 1.
2. Prohodnost staza koje povezuju rubne fontane sa središnjom. Staze su također dane redom obrnutim od kazaljke na satu. Prvi znak označava prohodnost staze koja povezuje fontanu 1 sa središnjom.
OutputU prvi i jedini red izlaza ispišite broj različitih šetnji.
Ulaz
3
111
111 Izlaz
7Ulaz
6
111011
001101 Izlaz
3Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.