U319719 八城堡问题

国际象棋中有一个叫做“城堡”的棋子，它的走法与中国象棋中的“車”相似，都是可以一步走到当前行或当前列的任意位置（除吃子外不能跨越棋子）

仰慕皇后的“城堡们”，也想学着“八皇后”站出“八城堡”的站位。但是就像城堡需要有地基一样，他们也不能随意布局，只能被建造在高地上，洼地则不行（容易倒）。同时任意两个城堡不能布局在同一行或者同一列上，以防两城堡之间发生部落冲突。 “城堡们”不够聪明，于是邀请聪明的你来帮助他们设计城堡布局的方案，快来帮帮他们吧！ “城堡们”在一个给定边长$N$的正方形棋盘上按一定方式排列，棋盘上用`H`字符表示高地：可以建造城堡；`L`字符表示洼地：不可以建造城堡。 “城堡们”需要被布局在高地上，同时任意两个城堡都不能放在正方形棋盘的同一行或者同一列上（要不然就会打架了） 请你设计一个程序，帮“城堡们”算出来对于给定大小和地形的棋盘，要摆放$M$个城堡的话，一共有多少种方案呢？

输入含有多组测试数据（至多不超过 $3$ 组数据）。 每组数据的第一行是用一个空格隔开的两个正整数$N$和$M$，表示了“城堡们”将在一个$N*N$的矩阵内向你描述棋盘，有$M$个城堡需要你同时布局。 随后的$N$行描述了棋盘的地形：每行有$N$个字符，其中 `H` 表示高地， `L` 表示洼地。 当 $N, M$ 都为 $0$ 时表示输入结束。

对于每一组数据，给出一行输出，输出“城堡们”布局的可选方案数$C$（数据保证$C\leq2^{31}-1$）。

## 数据规模 对于 $30\%$ 的数据，$0\lt M\leq N \leq 6$； 对于 $100\%$ 的数据，$0\lt M\leq N \leq 10$，数据组数 $\leq 3$。