Como cada vaca lo hace ocasionalmente; ¡Bessie se ha perdido en el bosque! Ella necesita desesperadamente regresar al establo pero no tiene idea de cómo hacerlo.

El bosque puede ser pensado como una cuadrícula $R\times C$ $(1\le R\le 5;1\le C\le 5)$. Bessie está ubicada en la esquina inferior izquierda en la fila $R$, columna $1$. El establo está ubicado en la esquina superior derecha en la fila $1$, columna $C$. Cada cuadrado en la cuadrícula o está vacío (denotado por '.') ó bloqueado por un árbol (denotado por 'T'). El cuadrado de Bessie y el establo siempre estarán vacíos.

Desde un cuadrado dado, Bessie puede moverse a cualquier cuadrado adyacente (uno con el cual comparte un lado con el cuadrado actual de Bessie) en tanto que esté vacío. Como Bessie es una vaca algo inteligente, ella nunca visita un cuadrado más de una vez en su camino de regreso al establo.

Determine el número de maneras distintas que Bessie puede tomar que la lleven desde su posición inicial de regreso al establo visitando a lo más $K$ cuadrados diferentes $(1\le K\le R\ast C)$.

Como ejemplo, considere este bosque:

....
.T..
....

Bessie tiene un número de maneras de llegar desde la esquina inferior izquierda hasta la esquina superior derecha; aquí están todas las siete posibilidades y los tamaños de los caminos (el número de cuadrados visitados):

           cdef     ...f     ..ef     ..gh     cdeh     cdej     ...f  
           bT..     .T.e     .Td.     .Tfe     bTfg     bTfi     .Tde  
           a...     abcd     abc.     abcd     a...     a.gh     abc.  
Longitud:  6        6        6        8        8        10       6

Entrada

• Línea 1: Tres enteros separados por espacios: $R$, $C$, y $K$.

• Líneas 2…R+1: La línea $i+1$ contiene $C$ caracteres que representan la fila $i$ del bosque (sin espacios).

Ejemplo de Entrada

3 4 6
....
.T..
....

Detalles de la Entrada

El bosque es una cuadrícula $3\times 4$. Un solo árbol que está casi en el medio, como se muestra. No se pueden usar más de seis pasos.

Salida

• Línea 1: Un solo entero que es el número de caminos diferentes que visitan a lo más $K$ cuadrados, que Bessie puede tomar para regresar al establo. Note que este número siempre entrará en un entero de $32$ bits.

Ejemplo de Salida

4

Detalles de la Salida

De las maneras diferentes de completar el recorrido, únicamente cuatro de ellas emplean no más de seis cuadrados a lo largo de la ruta.