À la recherche de la meilleure herbe, les vaches parcourent une grille de $N$ lignes et $M$ colonnes, $(2 \le N \le 100; 2 \le M \le 100)$. Farmer John, observateur attentif, note Bessie en $(R1, C1)$ puis exactement $T$ secondes après en $(R2, C2)$, $(0 \lt T \le 15)$. Il ignore si elle a déjà traversé $(R2, C2)$ avant $T$ secondes, mais elle y est au temps $T$.

Calculez l'entier $S$, nombre de façons d'aller de $(R1, C1)$ à $(R2, C2)$ en exactement $T$ secondes. À chaque seconde elle se déplace vers un voisin vertical ou horizontal, sans repos. Les arbres sont infranchissables.

Sur la carte . est un espace libre, * un arbre. Comptez les trajets de $(R1, C1)$ à $(R2, C2)$ en $T$ secondes.

Entrée

• Ligne 1 : trois entiers $N$, $M$, $T$ séparés par des espaces.
• Lignes $2,\ldots,N+1$ : la ligne $i+1$ décrit la rangée $i$ par exactement $M$ caractères . ou *.
• Ligne $N+2$ : quatre entiers $R1$, $C1$, $R2$, $C2$ séparés par des espaces.

Sortie

• Ligne 1 : l'entier $S$ sur une ligne.

Exemples

Entrée 1

4 5 6
...*.
...*.
.....
.....
1 3 1 5

Sortie 1

1

Remarque

Le pâturage a 4 lignes, 5 colonnes. De ligne 1 colonne 3 à ligne 1 colonne 5, il faut exactement 6 secondes.

De $(1,3)$ à $(1,5)$ en exactement 6 secondes, il n’y a qu’un trajet, celui, évident, qui contourne les deux arbres.

Auteur du problème : Aram Shatakhtsyan, 2007