Counting Two-House Construction Plans

Given an N × N grid representing a building site, each cell is either a wall represented by # or an empty space represented by .. Houses can only be built on empty spaces. Xiaolan wants to construct exactly two houses. In the construction plan, a house is defined as a set of empty cells that are connected horizontally or vertically. Due to limited construction materials, exactly K empty cells must be used to build the houses and all of them must be used. Furthermore, the K cells must divide into exactly two connected components (i.e. two houses).

Count the number of distinct construction plans that satisfy the above conditions.

Note: Two construction plans are considered different if the set of K cells chosen is different.

The connectivity condition can be mathematically defined using 4-directional connectivity. That is, for any two cells in a house, there exists a sequence of cells in that house connecting them where each consecutive pair of cells in the sequence are adjacent in one of the four directions (up, down, left, right).

Expressing the connectivity formally: Let \( S \) be the set of chosen cells. Then, there exist exactly two disjoint subsets \( S_1 \) and \( S_2 \) with \( S_1 \cup S_2 = S \) such that for every cell \(a, b \in S_i\), there is a path within \( S_i \) connecting \( a \) and \( b \) (using moves of the form \((i,j) \to (i+1,j)\), \((i,j) \to (i-1,j)\), \((i,j) \to (i,j+1)\), \((i,j) \to (i,j-1)\) for \(i,j \in \mathbb{Z}\)), and no cell in \( S_1 \) is adjacent to any cell in \( S_2 \> under this connectivity.

inputFormat

The first line contains two integers N and K (1 ≤ N ≤ 10, 1 ≤ K ≤ N×N), where N is the dimension of the grid and K is the exact number of empty cells to be used.

The following N lines each contain a string of length N consisting only of characters # and ., representing the grid.

outputFormat

Print a single integer representing the number of distinct construction plans that yield exactly two houses.

sample

2 2
..
..

2