题目描述

有一个由 $N$ 行 $N$ 列方格组成的建筑用地，每个方格，我们用 # 表示这是一堵墙，. 表示是一片空地，其中只有在空地上才可以进行房屋建造。小蓝想要在这片区域上建造两个房屋：通过水平/垂直方向可以连通在一起的区域属于同一个房屋。由于建筑物料有限，小蓝最多只能在 $K$ 个空地上进行房屋建造，同时他希望自己的房屋面积尽可能的大，所以他必须用光所有的 $K$ 块空地来建造房屋。

请问一共有多少种不同的建造方案。

输入格式

第一行输入三个整数 $N$、$K$。

接下来输入 $N$ 行，每行输入一个长度为 $N$ 的字符串，表示方格布局。

输出格式

输出一个整数表示答案。

3 3
###
.##
##.

0

3 3
.#.
.##
..#

5

提示

样例说明

• 对于样例 $1$：$K = 3$，但只有两个空地，所以没有符合题意的解，答案为 $0$。
• 对于样例 $2$，答案如下所示，我们用 @ 表示建筑物：

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

评测用例规模与约定

• 对于 $50\%$ 的评测用例：$1 \leq N \leq 5$，$1 \leq K \leq 5$。
• 对于 $100\%$ 的评测用例：$1 \leq N \leq 8$，$1 \leq K \leq 8$。