棋盘放置

题目描述

在一个 $n \times n$ 的棋盘上，有些格子可以放棋子（#），有些不能（.）。

要放上 $k$ 枚完全相同的棋子，要求：

• 只能放在 # 上；
• 任意两枚棋子不能同一行或同一列。

问有多少种放置方案？

输入格式

第一行两个整数 $n, k$（$1 \le k \le n \le 8$）。

接下来 $n$ 行，每行 $n$ 个字符（. 或 #）。

输出格式

输出一个整数，表示方案数。

输入示例 1

2 1
#.
.#

输出示例 1

2

输入示例 2

4 4
...#
..#.
.#..
#...

输出示例 2

1

数据范围

• $1 \le k \le n \le 8$