Problem Description

The school emblem of 24JP can be represented by an $n \times n$ binary matrix.
Initially, 24JP has only a $1 \times 1$ grassland.
24JP will undergo $k$ consecutive expansions.
Each expansion is described as follows:

1. Copy the current 24JP $n \times n$ times, making the length and width of 24JP $n$ times larger.
2. Map each position of the $01$ matrix representing the school emblem to the $n \times n$ copied plots.
3. Cover all positions in the regions corresponding to $0$ in the matrix with buildings.

Please calculate the number of maximal connected grassland blocks in 24JP after the expansions.
A maximal connected grassland block: a collection of grasslands where any two grasslands can be reached by moving up, down, left, or right without passing outside the campus, and adding any grassland outside the collection would break this property.
You can refer to the sample for a better understanding of the problem.

Calculate the number of maximum connected grassland blocks in dl24jp after the expansions.
Maximum connected grassland block: A set of grasslands where any two pieces of grassland in the set can be reached through up, down, left, or right movements without leaving the campus. Adding any grassland outside this set will destroy the property.

Refer to the examples for better understanding.

Input Format

Read data from exp.in.

The first line contains three integers $n$, $k$, and $c$, where $n$ and $k$ are as described in the problem, and $c$ is the subtask ID.
The next $n$ lines each contain $n$ integers, describing the $01$ matrix.

Output Format

Output the answer to exp.out.

Output a single integer representing the number of maximal connected grassland blocks.

Samples

2 2 2
0 1
0 1
1

1

Sample Explanation

Use $1$ to represent grassland and $0$ to represent buildings.

Before expansion:

1 

First expansion:

• Copy $n \times n = 2 \times 2$ times:

1 1 
1 1 

• Cover all positions corresponding to $0$ in the $01$ matrix with buildings:

0 1 
0 1 

Second expansion:

• Copy $n \times n = 2 \times 2$ times:

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

• Cover all positions corresponding to $0$ in the $01$ matrix with buildings:

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

After expansion, it is clear that there is only one maximal connected grassland block on the right side of the campus.

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

13

Sample Explanation

The campus after each expansion is as follows:

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

Subtasks and Constraints

For all data, it is guaranteed that $1 \leq n \leq 7$, $0 \leq k \leq 4$.

Subtasks are used in this task.

Subtask ID	$n$	$k$	Special Properties	Score
1	$\leq 1$		N/A	10
2	$\leq 2$			30
3	$\leq 7$	$\leq 0$		10
4		$\leq 4$	The matrix contains no $1$
5			The matrix contains no $0$
6			N/A	30