T566561 「PA Mashup #1」摆砖

给定一块 $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)$ 取模后的结果。

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