Buscando la mejor hierba, las vacas recorren una cuadrícula de $N$ filas y $M$ columnas, $(2 \le N \le 100; 2 \le M \le 100)$. Farmer John observó a Bessie en $(R1, C1)$ y exactamente $T$ segundos después en $(R2, C2)$, $(0 \lt T \le 15)$. No sabe si pasó por $(R2, C2)$ antes de $T$ segundos, pero allí está al tiempo $T$.
Calcula el entero $S$, formas de ir de $(R1, C1)$ a $(R2, C2)$ en exactamente $T$ segundos. Cada segundo va a un vecino vertical u horizontal, sin descansar. No puede atravesar árboles.
En el mapa . es espacio abierto, * árbol. Cuenta caminos de $(R1, C1)$ a $(R2, C2)$ en $T$ segundos.
Entrada
- Línea 1: tres enteros $N$, $M$, $T$ separados por espacios.
- Líneas $2,\ldots,N+1$: la línea $i+1$ describe la fila $i$ con exactamente $M$ caracteres
.o*. - Línea $N+2$: cuatro enteros $R1$, $C1$, $R2$, $C2$ separados por espacios.
Salida
- Línea 1: entero $S$ en una línea.
Ejemplos
Entrada 1
4 5 6 ...*. ...*. ..... ..... 1 3 1 5
Salida 1
1
Nota
El pastizal tiene 4 filas y 5 columnas. De fila 1 columna 3 a fila 1 columna 5 toma exactamente 6 segundos.
De $(1,3)$ a $(1,5)$ en 6 segundos exactos solo existe la ruta obvia que rodea los dos árboles.
Autor del problema: Aram Shatakhtsyan, 2007