Problem Description

In a class of $n$ children, they are not paying attention to the lesson but playing a watermelon-throwing game on Facebook.

During the first lesson, Goran throws a watermelon to each of his friends. In the subsequent lessons, the children act according to the following rules:

• If a person is hit by an odd number of watermelons in the previous lesson, they will throw one watermelon to each of their friends in this lesson.
• If a person is hit by an even number (including $0$) of watermelons in the previous lesson, they will throw two watermelons to each of their friends in this lesson.

The children are numbered from $1$ to $n$, with Goran being number $1$.

Given the number of children $n$ and their friendship relationships, find out how many watermelons are thrown in total after $h$ lessons.

Input Format

The input consists of $n+1$ lines.

The first line contains two integers $n$ and $h$, representing the number of children and the number of lessons, respectively.
The next $n$ lines, each containing $n$ integers (without spaces), form a matrix. The $i$-th line describes the friendship relationships of the $i$-th child. Specifically, if the $j$-th element in the $i$-th line is $1$, it means that the $i$-th child and the $j$-th child are friends; otherwise, they are not.

The input matrix is symmetric (i.e., if $A$ is a friend of $B$, then $B$ is also a friend of $A), and it is guaranteed that no child is friends with themselves.

Output Format

Output a single line containing an integer, representing the total number of watermelons thrown after $h$ lessons.

Sample Input and Output

Sample Input #1

4 1
0110
1001
1001
0110

Sample Output #1

2

Sample Input #2

4 2
0110
1001
1001
0110

Sample Output #2

14

Sample Input #3

5 3
01000
10110
01000
01001
00010

Sample Output #3

26

Notes

[Sample 1/2 Explanation]

For Sample $1/2$, initially, Goran throws a watermelon to the $2$nd and $3$rd children in the first lesson, and no other children throw watermelons. Thus, the answer for Sample $1$ is $2$.
In the second lesson, the $2$nd and $3$rd children each throw a watermelon to the $1$st and $4$th children, while the $1$st and $4$th children, having not been hit by watermelons in the previous lesson, each throw two watermelons to the $2$nd and $3$rd children. Therefore, a total of $2 \times 2 \times 1 + 2 \times 2 \times 2 = 12$ watermelons are thrown in the second lesson.

Thus, a total of $2 + 12 = 14$ watermelons are thrown in the first two lessons, which is the answer for Sample $2$.

[Data Range]

For $50\%$ of the test cases, $h \leq 1000$.
For all test cases, $1 \leq n \leq 20$, $1 \leq h \leq 10^9$.

[Problem Source]

This problem is from COCI 2008-2009 CONTEST 5 T4 LUBENICA, configured with the original problem data, worth $100$ points.

Translated and provided by Eason_AC.

见题面 Input 部分

见题面 Output 部分