P7681 [COCI 2008/2009 #5] LUBENICA

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.

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 only one line with an integer, representing the total number of watermelons thrown after $h$ lessons.

**[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](https://hsin.hr/coci/archive/2008_2009/) [CONTEST 5](https://hsin.hr/coci/archive/2008_2009/contest5_tasks.pdf) T4 LUBENICA_**, and follows the original testdata settings, with a full score of $100$. Translated and organized by [Eason_AC](https://www.luogu.com.cn/user/112917). Translated by ChatGPT 5