#P11808. [PA 2017] 摆砖 / Carcassonne

[PA 2017] 摆砖 / Carcassonne

题目背景

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

题目描述

给定一块 n×nn\times n 的棋盘,上面可能已经放了若干块 1×11\times 1 的砖。

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

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

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

输入格式

第一行两个正整数 n,kn,k

接下来 nn 行,第 ii 行一个长度为 nn 的字符串 sis_i

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

输出格式

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

3 2
.#.
##.
#..
8

提示

  • 2n3×1032\le n\le 3\times 10^3
  • 1k41\le k\le 4