Chain Letter

2000ms

262144K

Description:

A chain letter is a kind of a message which urges the recipient to forward it to as many contacts as possible, usually with some kind of mystic explanation. Of course, this is only a superstition, and you don't believe in it, but all your friends do. You know that today there will be one of these letters going around, and you want to know how many times you'll receive it — of course, not that you'll be sending it yourself!

You are given an array of strings f with n elements which describes the contacts between you and n - 1 of your friends: j-th character of i-th string (f[i][j]) is "1" if people i and j will send messages to each other, and "0" otherwise. Person 1 starts sending the letter to all his contacts; every person who receives the letter for the first time sends it to all his contacts. You are person n, and you don't forward the letter when you receive it.

Calculate the number of copies of this letter you'll receive.

Input:

The first line of the input contains an integer n (2 ≤ n ≤ 50) — the number of people involved. Next n following lines contain elements of f, strings of length n. Each character in f is either "0" or "1". It's guaranteed that two following equations hold: f[i][j] = f[j][i], f[i][i] = 0, for all i, j (1 ≤ i, j ≤ n).

Output:

Output a single integer — the number of copies of the letter you will receive eventually.

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Note:

In the first case, everybody sends letters to everyone, so you get copies from all three of your friends.

In the second case, you don't know any of these people, so they don't bother you with their superstitious stuff.

In the third case, two of your friends send you copies of the letter but the third friend doesn't know them so he is unaffected.

Informação

Provedor Codeforces

Código CF345D