题目描述

给定一个 $N \times N$ 的方格网格，其中第 $i$ 行第 $j$ 列的方格被涂成黑色当且仅当 $S_{i, j}$ 为 #，被涂成白色当且仅当 $S_{i, j}$ 为 .。
你需要选择 $K$ 个白色方格并将其涂成红色。有多少种涂色方式满足以下条件？

• 涂成红色的方格是连通的。也就是说，你可以通过水平或垂直移动从任意一个红色方格到达任意一个红色方格，而只访问红色方格。

约束条件

• $1 \leq N \leq 8$
• $1 \leq K \leq 8$
• $S_{i, j}$ 的取值为 # 或者 .。
• $N$ 和 $K$ 是整数。

输入

输入数据从标准输入读取，具体格式如下：

$N$
$K$
$S_{1, 1} \quad S_{1, 2} \quad \dots \quad S_{1, N}$
$S_{2, 1} \quad S_{2, 2} \quad \dots \quad S_{2, N}$
$\vdots$
$S_{N, 1} \quad S_{N, 2} \quad \dots \quad S_{N, N}$

输出

打印答案。

示例输入 1

3
5
#.#
...
..#

示例输出 1

5

有 $5$ 种满足条件的涂色方式，如下所示，其中 @ 表示红色方格。

#.# #@# #@# #@# #@#
@@@ .@@ @@. @@@ @@@
@@# @@# @@# .@# @.#

需要注意的是，下面的涂色方式不满足连通性要求，因为我们不考虑对角相邻。

#@#
@.@
@@#

示例输入 2

2
2
#.
.#

示例输出 2

0

无法满足条件。

示例输入 3

8
8
........
........
........
........
........
........
........
........

示例输出 3

64678