Chessboard Placement

Problem Background

Special for beginners, ^_^

Problem Description

Place indistinguishable pieces on a given-shaped chessboard (the shape may be irregular). The requirement is that no two pieces may be placed in the same row or the same column of the board. Write a program that, given the shape and size of the board, computes the number $C$ of all feasible placements of $k$ pieces.

Input Format

The input contains multiple test cases.

Each test case's first line contains two positive integers $n, k$, separated by a space, meaning that the board is described within an $n\times n$ matrix and $k$ pieces are to be placed $(n \le 8,\; k \le n)$.

The input ends when -1 -1 is given.

The following $n$ lines describe the board shape: each line has $n$ characters, where # denotes a board cell and . denotes a blank cell (the data guarantees there are no extra blank rows or columns).

Output Format

For each test case, output one line with the number of placement schemes $C$ (the data guarantees $C<2^{31}$).

Sample Input

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

Sample Output

2
1

Constraints

1s, 1024KiB for each test case.