Słowa 2

Limit pamięci: 64 MB

Niniejsze zadanie to istotnie trudniejsza wersja zadania Słowa z finału XVI OI. Nie wystąpiła ona w samym konkursie, a stanowi jedynie rozszerzenie dla tych, którym po zadaniu "Słowa" jeszcze mało :-).

Niech będzie funkcją określoną na napisach złożonych z cyfr 0 i 1. Funkcja przekształca napis , zastępując (niezależnie i równocześnie) każdą cyfrę 0 przez 1 i każdą cyfrę 1 przez napis . Na przykład , (tzn. funkcja zastosowana do pustego napisu jest pustym napisem). Zauważmy, że jest różnowartościowa. Przez oznaczmy -krotne złożenie funkcji ze sobą. W szczególności, to funkcja identycznościowa .

Interesują nas napisy postaci dla Oto kilka pierwszych takich napisów:

, , , , , .

Mówimy, że napis jest podsłowem napisu , jeżeli występuje w nim jako spójny (tj. jednokawałkowy) podciąg. Mamy dany ciąg liczb naturalnych . Celem zadania jest sprawdzenie, czy napis postaci jest podsłowem dla pewnego , a jeżeli tak, to wyznaczenie najmniejszego takiego . Przy tym operacja oznacza sklejenie (konkatenację) napisów.

Wejście

Pierwszy standardowego wejścia zawiera jedną liczbę całkowitą , . W drugim wierszu znajduje się nieujemnych liczb całkowitych () pooddzielanych pojedynczymi odstępami.

Wyjście

Twój program powinien wypisać na standardowe wyjście wiersz zawierający najmniejszą taką liczbę całkowitą nieujemną , dla której jest podsłowem , lub jedno słowo NIE, jeżeli żadne takie nie istnieje.

Przykład

Dla danych wejściowych:

2
1 2

poprawną odpowiedzią jest:

4

natomiast dla danych wejściowych:

2
2 0

poprawnym wynikiem jest:

NIE

Wyjaśnienie do przykładu: Słowo z pierwszego testu to - jest ono podsłowem słowa . W drugim teście występuje słowo , które nie jest podsłowem żadnego słowa postaci .

Autor zadania: Bartosz Walczak.