Description

There are $n$ children in a class. During lessons, they do not listen carefully and instead play a watermelon-throwing game on the Facebook social website.

In the first lesson, Goran throws one watermelon to each of his friends. In the following lessons, the children act as follows:

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

The children are numbered from $1$ to $n$, and Goran's number is $1$.

Now, given the number of children $n$ and all friendship relations among them, find the total number of watermelons thrown after $h$ lessons.

Input Format

The input has $n+1$ lines.

The first line contains two integers $n, h$, representing the number of children and the number of lessons.
Then follow $n$ lines, each containing $n$ integers (without spaces), forming a matrix. The $i$-th line describes the friendships of the $i$-th child. Specifically, if the $j$-th element in line $i$ is $1$, then child $i$ and child $j$ are friends; otherwise they are not.

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

Output Format

Output only one line with an integer, representing the total number of watermelons thrown after $h$ lessons.

4 1
0110
1001
1001
0110

2

4 2
0110
1001
1001
0110

14

5 3
01000
10110
01000
01001
00010 

26

Hint

[Explanation for Samples 1/2]

For Sample $1/2$, first, in the first lesson, Goran throws one watermelon to children $2$ and $3$, and no other child throws any watermelons. Therefore, the answer for Sample $1$ is $2$.
In the second lesson, children $2$ and $3$ each throw one watermelon to children $1$ and $4$. Meanwhile, since children $1$ and $4$ were not hit by any watermelons in the previous lesson, they each throw $2$ watermelons to children $2$ and $3$. Therefore, a total of $2\times 2\times 1+2\times 2\times 2=12$ watermelons are thrown in the second lesson.

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

[Constraints]

For $50\%$ of the testdata, $h\leqslant 1000$.
For all testdata, $1\leqslant n\leqslant 20$, $1\leqslant h\leqslant 10^9$.

[Source]

This problem comes from COCI 2008-2009 CONTEST 5 T4 LUBENICA, and follows the original testdata settings, with a full score of $100$.

Translated and organized by Eason_AC.

Translated by ChatGPT 5