题目描述

在一个 $n×n$ 的棋盘的部分区域摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定的棋盘，摆放 $k$ 个棋子的所有可行的摆放方案 $C$。

输入格式

输入含有多组测试数据。 每组数据的第一行是两个正整数 $n,k$，用一个空格隔开，表示了将在一个 $n×n$ 的矩阵内描述棋盘，以及摆放棋子的数目。 $k≤n≤10$。 当为 -1 -1 时表示输入结束。 随后的 $n$ 行描述了棋盘的形状：每行有 $n$ 个字符，其中 # 表示可摆放棋子的区域， . 表示不可放置棋子的区域。

输出格式

对于每一组数据，给出一行输出，输出摆放的方案数目$C$ （数据保证 $C<2^{31}$）。

样例

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

2
1

提示