Carcassonne

Bajtazar는 최근 Carcassonne 게임에 빠졌다. 이 게임에서 플레이어들은 차례로 한 변의 길이가 1인 정사각형 타일을 보드에 놓는다. 첫 번째 타일을 제외한 새 타일은 이전에 놓인 타일과 적어도 한 변을 맞대고 있어야 한다. 각 플레이어는 이전 타일을 놓자마자 새 타일을 뽑으므로, Bajtazar는 다른 플레이어가 움직이는 동안 자신의 다음 수를 미리 정할 수 있다. 다만 상대가 Bajtazar가 두려던 칸에 타일을 놓을 경우에 대비해 여러 수를 고려해야 한다.

보드는 $n \times n$ 칸이다(Bajtazar의 테이블에는 크기 제약이 있다). 이미 타일이 일부 놓여 있다. Bajtazar는 이제 $k$ 명의 상대 플레이어가 움직이기를 기다린다. $k$ 명이 수를 둔 뒤 나올 수 있는 서로 다른 배치가 몇 가지인지 구하라. 타일의 그림은 무시한다. 어떤 칸에 한 배치에서는 타일이 있고 다른 배치에서는 없다면, 두 배치는 다른 것이다.

첫 줄에 정수 $n$과 $k$가 주어진다($2 \le n \le 3000$, $1 \le k \le 4$). $n$은 보드의 한 변 길이이고, $k$는 Bajtazar의 상대 플레이어 수다. 이어지는 $n$ 줄에는 #와 .으로 이루어진 $n$ 글자 문자열이 하나씩 주어진다. $i$ 번째 줄의 $j$ 번째 글자는 $i$ 행 $j$ 열의 칸을 뜻한다. .은 빈 칸, #은 타일이 놓인 칸이다. 보드에는 타일이 적어도 하나 있고, 빈 칸은 적어도 $k$ 개 있다.

$k$ 번의 수 이후 나올 수 있는 서로 다른 배치의 개수를 정수 하나로 출력한다. 답은 $10^9 + 7$로 나눈 나머지로 출력한다.