题目描述

在不规则棋盘的可用格上放置 k 个无区别棋子，任意两个棋子不在同一行或同一列，求方案数。

输入格式

多组数据，每组 n,k、n 行棋盘，# 表示可用，. 表示不可用；以 -1 -1 结束。

输出格式

每组输出方案数。

样例

3 2
###
.#.
###
-1 -1

10

数据范围

n≤8，k≤n。