题目背景

译自 Potyczki Algorytmiczne 2017 R5 Carcassonne [B] (CAR)。$\texttt{5s,256M}$。

题目描述

给定一块 $n\times n$ 的棋盘，上面可能已经放了若干块 $1\times 1$ 的砖。

现在要再放置 $k$ 块 $1\times 1$ 砖。如果放置的砖不是这个棋盘上的第一块砖，则要求放置的这块砖必须和之前棋盘上有的砖至少有一条公共边。

求方案数对 $(10^9+7)$ 取模后的结果。

称两个方案是不同的，当且仅当存在一个格子，仅在一个方案中放了砖。

输入格式

第一行两个正整数 $n,k$。

接下来 $n$ 行，第 $i$ 行一个长度为 $n$ 的字符串 $s_i$。

$s_{i,j}=\texttt{\#}$，代表 $(i,j)$ 上放了砖；否则 $s_{i,j}=\texttt{.}$，代表没有放砖。

输出格式

输出一行一个整数，即方案数对 $(10^9+7)$ 取模后的结果。

3 2
.#.
##.
#..

8

提示

• $2\le n\le 3\times 10^3$；
• $1\le k\le 4$。