시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 30 5 4 22.222%

문제

상근이는 고등학교에 다닐 때, 친구들과 함께 아이폰으로 페이스북 게임을 했다. 그 당시에 가장 인기 있던 게임은 TGN에서 만든 수박 던지기이다.

선생님 몰래 게임을 하다가 걸리면 아이폰을 뺏길 수 있기 때문에, 그들은 수업이 시작하는 종이 치면 바로 게임을 한다. (게임을 하는데 드는 시간과 아이폰을 꺼내는 시간, 앱을 실행시키는 시간과 같은 시간은 모두 없다)

게임은 항상 상근이가 시작한다. 일교시가 시작할 때, 상근이는 그들의 친구에게 모두 수박을 하나씩 던진다. 이교시부터 다음 교시가 시작할 때는 다음과 같은 과정을 거치게 된다.

만약, 어떤 학생이 이전 교시까지 맞은 수박의 수가 홀수라면, 그는 모든 친구에게 수박을 하나씩 던진다. 이와 반대로 짝수개인 경우(0도 짝수)에는 수박을 두 개씩 던진다.

상근이네 반의 모든 학생들은 1번부터 N번까지 번호가 매겨져 있다. 상근이는 1번이다.

학생들의 친구 관계가 주어졌을 때, H교시가 끝난 이후에 수박이 총 몇 번 던져졌는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 학생의 수 N과 교시의 수 H가 주어진다. (1 ≤ N ≤ 20, 1 ≤ H ≤ 1,000,000,000)

다음 N개 줄에는 학생들의 친구관계가 행렬 형식으로 주어진다. A번째 행의 B번째 열의 수가 1인 경우에는 A와 B가 친구이고, 0인 경우에는 친구가 아니다.

자기 자신과 친구인 경우는 없고, 행렬은 항상 대칭이다.

출력

첫째 줄에 H교시가 끝난 이후에 학생들이 그때까지 던진 수박의 수를 출력한다.

예제 입력

4 2
0110
1001
1001
0110

예제 출력

14

힌트

1교시가 시작할 때, 상근이는 수박을 두 개 던진다. 2교시에는 1번, 4번 학생은 수박을 2번과 3번에게 두 개씩, 2번과 3번은 1번과 4번에게 한 개씩 던진다.