Cercando l'erba migliore, le mucche percorrono una griglia di $N$ righe e $M$ colonne, $(2 \le N \le 100; 2 \le M \le 100)$. L’attento Farmer John osserva Bessie in $(R1, C1)$ e dopo esattamente $T$ secondi in $(R2, C2)$, $(0 \lt T \le 15)$. Non sa se ha già attraversato $(R2, C2)$ prima di $T$ secondi, ma lì è al tempo $T$.
Calcola l'intero $S$, modi di andare da $(R1, C1)$ a $(R2, C2)$ in esattamente $T$ secondi. Ogni secondo passa al vicino verticale o orizzontale, senza riposo. Non attraversa alberi.
. è spazio aperto, * albero. Conta percorsi da $(R1, C1)$ a $(R2, C2)$ in $T$ secondi.
Input
- Riga 1: tre interi $N$, $M$, $T$ separati da spazi.
- Righe $2,\ldots,N+1$: la riga $i+1$ descrive la riga $i$ con esattamente $M$ caratteri
.o*. - Riga $N+2$: quattro interi $R1$, $C1$, $R2$, $C2$ separati da spazi.
Output
- Riga 1: intero $S$ su una riga.
Esempi
Input 1
4 5 6 ...*. ...*. ..... ..... 1 3 1 5
Output 1
1
Nota
Il pascolo ha 4 righe e 5 colonne. Da riga 1 colonna 3 a riga 1 colonna 5 servono esattamente 6 secondi.
Da $(1,3)$ a $(1,5)$ in 6 secondi esatti c'è solo il percorso ovvio attorno ai due alberi.
Autore del problema: Aram Shatakhtsyan, 2007