8703번 - Obława 다국어

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 n × n, 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 0, natomiast pozostałe pole, na których nie ma bagien, są oznaczone jako 1. 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 2. 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.

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

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.

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

• (3, 3), bok długości 4,
• (1, 3), bok długości 3,
• (3, 2), (3, 3), (5, 5), bok długości 2.