最近，Bajtazar 迷上了卡卡颂（Carcassonne）游戏。在这款游戏中，玩家轮流在棋盘上放置单位正方形瓷砖；每个新瓷砖（第一个除外）必须至少有一条边与之前放置的瓷砖相连。每位玩家在放置完瓷砖后会立即抽取下一块瓷砖，因此 Bajtazar 可以在其他玩家行动时为自己的下一步行动制定策略。然而，他必须考虑多种情况，以防有对手将瓷砖放置在他原本想放置的位置。

在一个 $n \times n$ 的棋盘上（Bajtazar 的桌子有其局限性），已经放置了一些瓷砖。Bajtazar 现在正在等待他的 $k$ 个对手行动。他想知道他需要为多少种可能的情况做好准备，更确切地说：在 $k$ 名玩家完成各自的行动后，可能会形成多少种不同的布局？我们忽略瓷砖上的图案；如果存在一个格子，在一个布局中放置了瓷砖而另一个布局中没有，则这两个布局被视为不同。

输入格式

输入的第一行包含两个整数 $n$ 和 $k$ ($2 \le n \le 3000, 1 \le k \le 4$)，分别表示棋盘的边长和 Bajtazar 的对手数量。接下来的 $n$ 行，每行包含一个长度为 $n$ 的字符串，由字符“#”和“.”组成，描述了棋盘的一行：第 $i$ 行的第 $j$ 个字符表示棋盘第 $i$ 行第 $j$ 列的格子；“.”表示空位，“#”表示已放置瓷砖的格子。棋盘上至少已经放置了一个瓷砖，且至少有 $k$ 个空位。

输出格式

输出一行一个整数，表示在 $k$ 次行动后可能产生的不同布局数量。该结果需对 $10^9 + 7$ 取模。

样例

输入 1

3 2
.#.
##.
#..

输出 1

8