AT_abc211_e [ABC211E] Red Polyomino

题目描述

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

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

输入格式

第一行一个整数 $N$。

第二行一个整数 $K$。

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

输出格式

可能的答案。

样例 1

输入

3
5
#.#
...
..#

输出

5

样例 2

输入

2
2
#.
.#

输出

0

样例 3

输入

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

输出

64678

说明/提示

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