学校里的孩子们没有听课，而是在找乐子。他们用自己的 iPhone 手机在 Facebook 社交网站上互相扔西瓜。

当天第一节课期间，Goran 向他的每一个朋友各扔了一个西瓜，游戏由此开始。在随后的每节课中，所有的孩子（包括 Goran）都按以下规则行动：

• 如果他们在上一节课中被奇数个西瓜砸中，他们会向自己的每一个朋友各扔恰好一个西瓜；
• 如果他们在上一节课中被偶数个（包括零个）西瓜砸中，他们会向自己的每一个朋友各扔两个西瓜。

孩子们被编号为 $1$ 到 $N$，Goran 显然是 $1$ 号。孩子们之间的朋友关系也是已知的。

编写一个程序，计算在 $H$ 节课后总共扔出的西瓜数量。

输入格式

第一行包含两个整数 $N$ 和 $H$（$1 \le N \le 20$，$1 \le H \le 1\,000\,000\,000$），分别表示孩子的数量和课时数。

接下来的 $N$ 行，每行包含一个长度为 $N$ 且仅由字符 '0' 或 '1' 组成的字符串。该矩阵中第 $A$ 行第 $B$ 列的字符（即 $(A, B)$）为 '1' 表示孩子 $A$ 和孩子 $B$ 是朋友，否则为 '0'。

没有孩子会是自己的朋友。输入矩阵是对称的。

输出格式

输出在 $H$ 节课后扔出的西瓜总数。

子任务

在占总分 $50\%$ 的测试数据中，$H$ 最多为 $1000$。

样例

输入样例 1

4 1
0110
1001
1001
0110

输出样例 1

2

输入样例 2

4 2
0110
1001
1001
0110

输出样例 2

14

输入样例 3

5 3
01000
10110
01000
01001
00010

输出样例 3

26

说明

在第二个样例中，Goran 在第一节课期间扔了两个西瓜。在第二节课期间，孩子 $1$ 和孩子 $4$ 分别向孩子 $2$ 和孩子 $3$ 各扔了两个西瓜，而孩子 $2$ 和孩子 $3$ 分别向孩子 $1$ 和孩子 $4$ 各扔了一个西瓜。第二节课期间总共扔了 $12$ 个西瓜。两节课后总共扔了 $2 + 12 = 14$ 个西瓜。