Description

On a chessboard of a given shape (which may be irregular), place chess pieces that are indistinguishable.
The requirement is that when placing the pieces, no two pieces can be placed in the same row or column of the chessboard. Write a program to determine all feasible placement schemes ( C ) for placing ( k ) pieces on a chessboard of given shape and size.

Input Format

The input contains multiple test cases.
The first line of each test case contains two positive integers ( n ) and ( k ), separated by a space, indicating that the chessboard is described within an ( n \times n ) matrix and the number of pieces to be placed is ( k ). ( (n \leq 8, k \leq n) )
When the input is (-1\ -1), it indicates the end of input.
The following ( n ) lines describe the shape of the chessboard: each line contains ( n ) characters, where # represents a valid chessboard region, and . represents a blank region (it is guaranteed that there are no extra blank rows or columns).

Output Format

For each test case, output a single line containing the number of feasible placement schemes ( C ) (it is guaranteed that ( C < 2^{31} )).

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

2
1