Watermelon Throwing Game

During high school, Sanggeun played a phone game with his friends. At that time, the most popular game was Watermelon Throwing.

Because they might lose the phone if they were caught playing after class started, they begin the game exactly when the bell rings. Ignore all time needed to take out the phone, launch the app, or play a turn.

Sanggeun always starts the game. At the beginning of period 1, Sanggeun throws one watermelon to each of his friends. From period 2 onward, at the beginning of each period, every student acts according to how many watermelons hit them during the previous period.

If that number is odd, the student throws one watermelon to each friend. If that number is even, including 0, the student throws two watermelons to each friend.

The students in Sanggeun's class are numbered from 1 to N, and Sanggeun is student 1.

Given the friendship relations, write a program that computes the total number of watermelons thrown by the end of period H.

The first line contains the number of students N and the number of periods H. (1 <= N <= 20, 1 <= H <= 1,000,000,000)

The next N lines give the friendship relations as a matrix. If the B-th character of the A-th line is 1, students A and B are friends. If it is 0, they are not friends.

No student is their own friend, and the matrix is always symmetric.

Print the total number of watermelons thrown by all students through the end of period H.

In the second visible test case, Sanggeun throws two watermelons in total at the beginning of period 1. During period 2, students 1 and 4 each throw two watermelons to students 2 and 3, while students 2 and 3 each throw one watermelon to students 1 and 4.