题目描述

给你边长为 $N$ 的且仅由字符 # 和 . 组成的正方形阵列，其中 # 表示黑色格子， . 表示白色格子。

你需要在白色格子中选择 $K$ 个涂成红色，且使红色格子互相连接（仅包括上下左右相邻），求有多少种可能的方案。

输入格式

第一行一个整数 $N$。

第二行一个整数 $K$。

以下 $N$ 行每行 $N$ 个字符表示给出的阵列。

输出格式

可能的答案。

3
5
#.#
...
..#

5

2
2
#.
.#

0

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

64678

说明/提示

保证数据满足 $1 \leq n, k \leq 8$。