题目描述

题目译自 PA 2017 Runda 5 Carcassonne

最近，Bajtazar 成为了一款名为卡卡松的游戏的粉丝。在这款游戏中，玩家依次在棋盘上放置边长为单位的正方形卡片；除了第一个卡片外，每个新卡片必须至少与一个已放置的卡片相邻。每个玩家在放置上一个卡片后立即抽取一个新卡片，因此 Bajtazar 可以在其他玩家的回合中规划自己下一回合的策略。然而，他必须考虑多种可能的走法，以防某个对手将卡片放在他希望放置的位置上。

在一个尺寸为 $n \times n$ 的棋盘上（Bajtazar 的桌子有空间限制），已经放置了一些卡片。Bajtazar 正在等待他的 $k$ 个对手完成他们的回合。他想知道自己需要为多少种可能的情况做好准备，具体来说：在 $k$ 个玩家完成回合后，可能形成多少种不同的布局？我们忽略卡片上的图案；如果某个位置在一个布局中有卡片而在另一个布局中没有，则认为这两个布局不同。

输入格式

输入数据的第一行包含两个整数 $n$ 和 $k$ $(2 \leq n \leq 3000, 1 \leq k \leq 4)$，分别表示棋盘边长和 Bajtazar 的对手数量。

接下来的 $n$ 行描述棋盘的每一行，每行是一个由 $n$ 个字符组成的字符串，字符为 #（井号）和 .（点号）：第 $i$ 行第 $j$ 个字符表示棋盘第 $i$ 行第 $j$ 列的位置；点号表示空位，井号表示该位置已放置卡片。棋盘上至少有一个卡片，且至少有 $k$ 个空位。

输出格式

输出应包含一个整数，表示在 $k$ 个回合后可能形成的不同布局数量。结果需取模 $10^{9}+7$。

3 2
.#.
##.
#..

8