시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

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 ti,1, ti,2, ..., ti,n - zera lub jedynki. Jeżeli ti,j = 0, oznacza to, że na danym polu jest bagno, natomiast ti,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.

예제 입력 1

6
111110
101010
011111
011101
101011
011111

예제 출력 1

5

힌트

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.