题目描述

一个班有 $n$ 个孩子，他们上课时并没有认真听课，而是在玩 Facebook 社交网页上的扔西瓜游戏。

第一节课上，Goran 向他的每个朋友扔了一个西瓜，随后几节课，孩子们都会按照以下方式采取行动：

• 如果上节课一个人被奇数个西瓜扔中，那么这节课他会向所有他的朋友各扔一个西瓜。
• 如果上节课一个人被偶数（包括 $0$）个西瓜扔中，那么这节课他会向所有他的朋友各扔两个西瓜。

孩子们按照 $1\sim n$ 编号，其中 Goran 的编号为 $1$。

现在，给定孩子的个数 $n$ 和他们所有人的朋友关系，请求出 $h$ 节课之后，孩子们一共扔了多少个西瓜。

输入格式

输入共 $n+1$ 行。

第一行，两个整数 $n,h$，分别表示孩子的个数和课程的节数。
随后 $n$ 行，每行 $n$ 个整数（不用空格隔开），形成一个矩阵。第 $i$ 行描述第 $i$ 个孩子的朋友关系，具体地，如果第 $i$ 行第 $j$ 个元素是 $1$，则表示第 $i$ 个孩子和第 $j$ 个孩子是朋友，否则不是。

输入矩阵是对称的（即 $A$ 如果是 $B$ 的朋友，那么 $B$ 也会是 $A$ 的朋友），并且保证不会出现一个孩子和自己成为朋友的情况。

输出格式

输出仅一行，一个整数，表示 $h$ 节课之后孩子们扔出的西瓜总数。

4 1
0110
1001
1001
0110

2

4 2
0110
1001
1001
0110

14

5 3
01000
10110
01000
01001
00010 

26

提示

【样例 1/2 解释】

对于样例 $1/2$，首先，Goran 在第一节课上向第 $2$、$3$ 号孩子扔出一个西瓜，并且没有其他孩子扔出西瓜。因此，样例 $1$ 的答案为 $2$。
第二节课上，第 $2$、$3$ 号孩子都向第 $1$、$4$ 号孩子各扔出一个西瓜，同时第 $1$、$4$ 号孩子由于在上一节课没有被西瓜扔中，因此他们都向第 $2$、$3$ 号孩子各扔出 $2$ 个西瓜。因此第二节课上一共扔出了 $2\times 2\times 1+2\times 2\times 2=12$ 个西瓜。

因此，前两节课一共扔出了 $2+12=14$ 个西瓜，而这就是样例 $2$ 的答案。

【数据范围】

对于 $50\%$ 的数据，满足 $h\leqslant 1000$。
对于所有数据，$1\leqslant n\leqslant 20$，$1\leqslant h\leqslant 10^9$。

【题目来源】

本题来源自 COCI 2008-2009 CONTEST 5 T4 LUBENICA，按照原题数据配置，满分 $100$ 分。

由 Eason_AC 翻译整理提供。