Obława

Limit pamięci: 64 MB

Fifolandia ponownie jest w stanie wojny z Wielką Barańską Gogolską Dżamahirijją Ludową. Ostała się już tylko ostatnia jednostka nieprzyjaciela, która ukryła się gdzieś w lesie. Kapral Fifuś jest odpowiedzialny za zorganizowanie obławy na oddział nieprzyjaciela.

W związku z tym Fifuś szybko znalazł mapę lasu o rozmiarze , na której dla każdego jednostkowego kwadratu oznaczone jest, czy znajdują się na nim bagna, czy też nie. Na mapie pola, na których jest bagno, są oznaczone jako , natomiast pozostałe pole, na których nie ma bagien, są oznaczone jako . Oczywiście oddziały Fifusia nie mogą stacjonować na obszarze, na którym znajduje się bagno. Ponadto w wojskowym prawie Fifolandii jest dokładnie określone, jak powinna wyglądać obława, a Fifuś musi przestrzegać tych zasad.

Zgodnie z wojskowym prawem Fifolandzkim otaczając przeciwnika, należy tak rozmieścić wojska, aby tworzyły obwód kwadratu o boku co najmniej . Podobno takie rozmieszczenie gwarantuje, że wojskom przeciwnika nie uda się uciec. Na nieszczęście Fifuś nie ma najmniejszego pojęcia, gdzie mogą znajdować się wojska przeciwnika. Dlatego zanim Fifuś zdecyduje, w którym miejscu rozpocząć obławę, zastanawia się, na ile sposobów można to zrobić.

Zakładamy, że wojska Fifolandii nie będą miały problemów z dotarciem w dowolne miejsce, które nie jest bagnem - mogą do tego użyć np. helikopterów.

Wejście

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą (), oznaczającą długość boku mapy. Następnie na wejściu pojawi się wierszy. W -tym wystąpi ciąg cyfr - zera lub jedynki. Jeżeli , oznacza to, że na danym polu jest bagno, natomiast oznacza, że na danym polu nie ma bagna.

Możesz założyć, że w testach wartych około zachodzi dodatkowy warunek .

Wyjście

Pierwszy wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą, równą liczbie sposobów, na które Fifuś może rozmieścić wojska.

Przykład

Dla danych wejściowych:

6
111110
101010
011111
011101
101011
011111

poprawną odpowiedzią jest:

5

Wyjaśnienie do przykładu: Fifuś może rozmieścić wojsko na obwodzie kwadratów, których współrzędne lewego górnego rogu to:

• , bok długości ,
• , bok długości ,
• , bok długości .

Autor zadania: Łukasz Jocz.