D. Письмо счастья
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Письма счастья — сообщения, которые требуют от получателя переслать их копии как можно большему количеству людей, обычно с неким мистическим объяснением. Конечно, это всего лишь суеверие, и вы игнорируете такие письма — чего нельзя сказать о ваших друзьях. Известно, что сегодня такое письмо будет циркулировать среди ваших друзей, и вы хотите знать заранее, сколько его копий вы получите — конечно, пересылать его дальше вы не собираетесь!

Связи между вами и n - 1 вашими друзьями заданы массивом строк f из n элементов: j-ый символ i-ой строки (f[i][j]) — «1», если люди номер i и j будут обмениваться сообщениями (есть в контактах друг у друга), и «0» в противном случае. Человек номер 1 начинает рассылать сообщения всем своим контактам; каждый человек, получая письмо впервые, пересылает его всем своим контактам. Вы — человек номер n, и вы не пересылаете полученные письма.

Сколько копий этого письма вы получите?

Входные данные

Первая строка входных данных содержит целое число n (2 ≤ n ≤ 50) — количество задействованных людей. Следующие n строк содержат элементы массива f — строки длины n, состоящие из символов «0» и «1». Гарантируется, что выполняются равенства: f[i][j] = f[j][i], f[i][i] = 0, для всех i, j (1 ≤ i, j ≤ n).

Выходные данные

Выведите целое число — количество копий письма, которые вы получите со временем.

Примеры
Входные данные
4
0111
1011
1101
1110
Выходные данные
3
Входные данные
4
0110
1010
1100
0000
Выходные данные
0
Входные данные
4
0101
1001
0001
1110
Выходные данные
2
Примечание

В первом случае все посылают письма друг другу, так что вы получите копии от всех троих друзей.

Во втором случае вы не знаете никого из этих людей.

В третьем случае двое друзей посылают вам письма, но третий не знает ни одного из них и не получает письмо.