Tae and Dotori split a chocolate bar

Tae and Dotori have one rectangular chocolate bar of size $N \times M$. The bar is divided into $1 \times 1$ cells, and each cell has one of the letters T, D, U written on it. The two of them want to break the bar into two pieces and take one piece each. Every cell goes to one of the two people, and each person takes at least one cell.

A way of splitting the bar has to follow all of these rules.

• A cell with T goes to Tae, and a cell with D goes to Dotori. A cell with U can go to either one.
• All cells one person takes have to form a single connected piece. Two cells touch when they share a side.
• The difference between the numbers of cells the two people take must not exceed $K$.
• Four cells taken by the same person must not form a $2 \times 2$ square. That is, the shape below must not appear.

XX
XX

Given the size of the bar and the letter written in each cell, write a program that counts the ways to split the bar into two pieces. Two ways are different when the sets of cells the two people take are different.

The first line has $N$, $M$, $K$ ($1 \le N, M \le 8$, $0 \le K \le N \times M$). Each of the next $N$ lines has the letters written in the cells of one row of the bar. Each line has $M$ characters, and each character is T, D, or U.

Print the number of ways to split the chocolate into two pieces on the first line.

If all four cells of a $2 \times 2$ bar have U and $K$ is 4, there are $2^4 = 16$ assignments. Writing T for a cell Tae takes and D for a cell Dotori takes, the 4 assignments below break the rules.

TT
TT

DD
DD

DT
TD

TD
DT

In the first two, four cells of the same person form a $2 \times 2$ square. In the last two, the cells each person takes are split apart. The other 12 follow the rules.