수박 던지기 게임

상근이는 고등학교에 다닐 때 친구들과 함께 휴대전화 게임을 했다. 그때 가장 인기 있던 게임은 수박 던지기였다.

수업이 시작된 뒤 게임을 하다가 걸리면 휴대전화를 빼앗길 수 있으므로, 친구들은 수업 시작 종이 치는 순간 바로 게임을 한다. 휴대전화를 꺼내는 시간, 앱을 실행하는 시간, 게임을 진행하는 시간은 모두 없다고 본다.

게임은 항상 상근이가 시작한다. 1교시가 시작될 때 상근이는 자기 친구 모두에게 수박을 하나씩 던진다. 2교시부터는 각 교시가 시작될 때, 모든 학생이 바로 이전 교시에 자신이 맞은 수박의 수에 따라 행동한다.

이전 교시에 맞은 수박의 수가 홀수라면 그 학생은 모든 친구에게 수박을 하나씩 던진다. 짝수라면, 0개인 경우도 포함하여 모든 친구에게 수박을 두 개씩 던진다.

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

학생들의 친구 관계가 주어졌을 때, H교시가 끝날 때까지 던져진 수박의 총 개수를 구하는 프로그램을 작성하시오.

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

다음 N개 줄에는 학생들의 친구 관계가 행렬 형식으로 주어진다. A번째 줄의 B번째 문자가 1이면 A번 학생과 B번 학생이 친구이고, 0이면 친구가 아니다.

자기 자신과 친구인 학생은 없으며, 행렬은 항상 대칭이다.

H교시가 끝날 때까지 학생들이 던진 수박의 총 개수를 출력한다.

두 번째 공개 테스트 케이스에서는 1교시가 시작될 때 상근이가 수박을 총 두 개 던진다. 2교시에는 1번과 4번 학생이 각각 2번과 3번 학생에게 수박을 두 개씩 던지고, 2번과 3번 학생은 각각 1번과 4번 학생에게 수박을 하나씩 던진다.