题目描述

请注意校徽和校园的区别。

廿四金普的校徽可以用一个大小为 $n\times n$ 的 $01$ 矩阵表示；
一开始，廿四金普校园只有一块大小为 $1\times 1$ 草地；
廿四金普校园将连续进行 $k$ 次扩建；
一次扩建表述如下：

1. 将当前廿四金普校园整体复制 $n\times n$ 遍，使廿四金普校园的长和宽都变为原来的 $n$ 倍
2. 将校徽的 $01$ 矩阵的每个位置，与刚刚复制出来的 $n\times n$ 个地块一一对应
3. 将校徽矩阵中 $0$ 所对应的区域中的所有位置盖上教学楼

请你算一算扩建后的廿四金普校园中，有多少个极大的草坪连通块。
极大的草坪联通块：一个草坪的集合，集合中任意两块草坪可通过上下左右移动不经过校园外互相达到，且再加入任意一个集合外的草坪将破坏上述性质
你可以参照样例更好地理解题意

输入格式

从 $exp.in$ 读入数据。
第一行三个整数 $n,k,c$，$n,k$ 含义见题目描述，$c$ 为子任务编号，
接下来 $n$ 行，每行 $n$ 个整数，描述 $01$ 矩阵。

输出格式

输出答案到 $ex p.out$。
一行一个整数，表示极大的草坪连通块数量。

样例

2 2 2
0 1
0 1

1

样例解释

用 $1$ 代表草地，$0$ 代表教学楼；
未扩建时：

1 

第一次扩建：

• 先复制 $n\times n=2\times 2$ 份

1 1 
1 1 

• 将 $01$ 矩阵中 $0$ 对应位置全部盖满教学楼

0 1 
0 1 

第二次扩建：

• 先复制 $n\times n=2\times 2$ 份

0 1 0 1 
0 1 0 1 
0 1 0 1 
0 1 0 1 

• 将 $01$ 矩阵中 $0$ 对应位置全部盖满教学楼

0 0 0 1
0 0 0 1
0 0 0 1
0 0 0 1 

扩建完成，显然校园右侧有唯一的极大草坪连通块。

3 3 6
1 0 0 
1 1 1 
0 0 1 

13

样例解释

每次扩建之后的校园如下所示：

1 0 0 
1 1 1 
0 0 1 

1 0 0 0 0 0 0 0 0 
1 1 1 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 0 
1 0 0 1 0 0 1 0 0 
1 1 1 1 1 1 1 1 1 
0 0 1 0 0 1 0 0 1 
0 0 0 0 0 0 1 0 0 
0 0 0 0 0 0 1 1 1 
0 0 0 0 0 0 0 0 1 

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 
1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 
1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 

7 4 6
1 0 0 1 1 1 0 
0 1 0 0 1 0 1 
1 1 1 0 1 1 0 
0 1 1 1 1 1 1 
0 0 1 0 0 1 1 
0 1 1 0 1 0 0 
1 1 1 1 0 1 1 

81143

子任务与数据范围

对于所有数据，保证 $1\leq n\leq 7,~0\leq k\leq 4$，
测评使用捆绑测试，本题不卡常，短时限是为了防止卡评测。