태와 도토리의 초콜릿 나누기

태와 도토리는 크기가 $N \times M$인 직사각형 초콜릿을 하나 가지고 있다. 초콜릿은 $1 \times 1$ 크기의 칸으로 나누어져 있고, 각 칸에는 T, D, U 중 한 글자가 적혀 있다. 두 사람은 초콜릿을 두 조각으로 나눠서 한 조각씩 가져가려고 한다. 모든 칸은 둘 중 한 사람에게 가고, 두 사람 모두 적어도 한 칸을 가져간다.

나누는 방법은 다음 규칙을 모두 지켜야 한다.

• T가 적힌 칸은 태가 가져가고, D가 적힌 칸은 도토리가 가져간다. U가 적힌 칸은 둘 중 누가 가져가도 된다.
• 한 사람이 가져가는 칸은 전체가 연결되어 있어야 한다. 두 칸은 변을 공유할 때 서로 붙어 있다고 한다.
• 두 사람이 가져가는 칸 개수의 차이는 $K$를 넘으면 안 된다.
• 같은 사람이 가져간 칸 4개가 $2 \times 2$ 정사각형을 이루면 안 된다. 즉 아래와 같은 모양이 있으면 안 된다.

XX
XX

초콜릿의 크기와 각 칸에 적혀 있는 문자가 주어졌을 때, 초콜릿을 두 조각으로 나누는 방법의 수를 구하는 프로그램을 작성하시오. 두 사람이 가져가는 칸의 집합이 다르면 서로 다른 방법으로 센다.

첫째 줄에 $N$, $M$, $K$가 주어진다. ($1 \le N, M \le 8$, $0 \le K \le N \times M$) 둘째 줄부터 $N$개의 줄에는 초콜릿의 칸에 적혀 있는 문자가 주어진다. 각각의 줄은 총 $M$개의 문자로 이루어져 있으며, 각 문자는 T, D, U 중 하나이다.

첫째 줄에 초콜릿을 두 조각으로 나누는 방법의 수를 출력한다.

$2 \times 2$ 초콜릿의 네 칸에 모두 U가 적혀 있고 $K$가 4이면 배정은 $2^4 = 16$가지다. 태가 가져간 칸을 T, 도토리가 가져간 칸을 D로 표시하면 이 중 아래 4가지는 규칙을 어긴다.

TT
TT

DD
DD

DT
TD

TD
DT

앞의 두 가지는 같은 사람의 칸 4개가 $2 \times 2$ 정사각형을 이루고, 뒤의 두 가지는 각자가 가져간 칸이 서로 떨어져 있다. 나머지 12가지가 규칙을 지킨다.