태와 도토리는 크기가 N×M인 직사각형 초콜릿을 하나 가지고 있다. 초콜릿은 1×1크기의 칸으로 나누어져 있으며, 각각의 칸은 T, D, U중 하나의 글자가 적혀져 있다. 초콜릿을 먹기 위해 다음과 같은 방법으로 두 조각으로 나누려고 한다.</p>

• 태가 가져가는 조각에는 D가 적혀있는 칸이 있으면 안 된다. 도토리가 가져가는 조각에는 T와 U가 적혀있는 칸이 있으면 안 된다.
• 모든 초콜릿 조각은 연결되어 있어야 한다. 두 칸은 같은 변을 공유할 때, 연결되어 있다고 한다.
• 두 초콜릿 조각의 칸의 개수의 차이는 K를 넘으면 안 된다.
• 초콜릿을 두 조각으로 나누었을 때, 4개의 인접한 칸이 정사각형을 만들면 안 된다. 즉, 아래와 같은 모양이 있으면 안 된다.

XX
XX

초콜릿의 크기와 칸에 쓰여 있는 문자가 주어졌을 때, 초콜릿을 두 조각으로 나누는 방법의 수를 구하는 프로그램을 작성하시오.

입력 형식

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

출력 형식

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

예제 입력

2 2 4
UU
UU

예제 출력

12

힌트

T를 태가 가져간 조각, D를 도토리가 가져간 조각이라고 했을 때, 총 2⁴ = 16가지 방법 중 아래와 같은 4가지 방법은 불가능하다.

TT
TT

DD
DD

DT
TD

TD
DT