Connected Brick Placement

You are given an \(n\times n\) chessboard. Some of the cells may already have a \(1\times 1\) brick placed in them. You are required to place an additional \(k\) bricks (each of size \(1\times 1\)) on empty cells. However, there is one constraint:

• If the brick you place is not the first brick on the board (i.e. if there is already at least one brick on the board at the time of placement), then the cell where you place the brick must share at least one common side with some brick that is already on the board.

In other words, if the board is initially empty then the first placed brick can go anywhere, but subsequent placements must be adjacent (via one of the four sides) to at least one brick already present (whether originally placed or placed earlier). If the board already has some bricks, then every newly placed brick must be adjacent to one of the previously existing bricks.

Two placement schemes are considered different if and only if there exists at least one cell which contains a brick in one scheme and is empty in the other.

Your task is to count the number of valid placement schemes modulo \(10^9+7\).

inputFormat

The first line contains two integers \(n\) and \(k\) (\(1 \le n \le 10\), \(0 \le k \le n^2\)).

The following \(n\) lines each contain \(n\) integers. Each integer is either 0 or 1, where 0 represents an empty cell and 1 represents a cell that already contains a brick.

outputFormat

Output a single integer — the number of valid ways to place the \(k\) bricks satisfying the given condition, modulo \(10^9+7\).

sample

2 1
0 0
0 0

4