T566561 「PA Mashup #1」摆砖

给定一块 $n\times n$ 的棋盘，上面可能已经放了若干块 $1\times 1$ 的砖。 现在要再放置 $k$ 块 $1\times 1$ 砖。如果放置的砖不是这个棋盘上的第一块砖，则要求放置的这块砖必须和之前棋盘上有的砖至少有一条公共边。 求方案数对 $(10^9+7)$ 取模后的结果。 称两个方案是不同的，当且仅当存在一个格子，仅在一个方案中放了砖。

无

无

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