题目描述

在遥远的银河系边缘，人类发现了一片由 N×N 个星域组成的矩形空间。由于星际尘埃的影响，并非所有星域都适合建立通信基站，只有标记为 # 的星域是安全的，标记为 . 的星域则存在辐射危险，不可使用。

现在，指挥部计划在这片安全星域中部署 K 个量子通信基站。为了信号互不干扰，任意两个基站不能位于同一行或同一列的星域中棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。

请编写程序，计算在给定的星域地图中，部署 K 个基站的所有可行方案总数 C。

输入格式

输入含有多组测试数据。 每组数据的第一行是两个正整数$n,k$，用一个空格隔开，分别表示星域矩阵的大小和需要部署的基站数量。($n≤8,k≤n$)

当为$−1−1$时表示输入结束。

接下来$N$行，每行包含$N$个字符，“#”表示安全星域，“.”表示危险星域。（数据保证不出现多余的空白行或者空白列）。

输出格式

对于每一组数据，给出一行输出，表示可行的部署方案总 数（数据保证$C<2^{31}$）。

输入输出样例

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

2
1