Für das beste Gras durchstreifen Kühe eine Weide mit $N$ Zeilen und $M$ Spalten, $(2 \le N \le 100; 2 \le M \le 100)$. Der aufmerksame Farmer John beobachtete Bessie in $(R1, C1)$, genau $T$ Sekunden später in $(R2, C2)$, $(0 \lt T \le 15)$. Ob sie $(R2, C2)$ schon passierte, bevor $T$ Sekunden vergangen waren, ist unklar, doch zum Zeitpunkt $T$ ist sie dort.

Gesucht ist Ganzzahl $S$, Zahl der Wege von $(R1, C1)$ nach $(R2, C2)$ in genau $T$ Sekunden. Jede Sekunde geht sie in einen vertikalen oder horizontalen Nachbarn, ohne Pause. Bäume sind unpassierbar.

. ist freies Weideland, * ein Baum. Zähle Wege von $(R1, C1)$ nach $(R2, C2)$ in $T$ Sekunden.

Eingabe

• Zeile 1: drei Ganzzahlen $N$, $M$, $T$ durch Leerzeichen getrennt.
• Zeilen $2,\ldots,N+1$: Zeile $i+1$ beschreibt Reihe $i$ mit genau $M$ Zeichen . oder *.
• Zeile $N+2$: vier Ganzzahlen $R1$, $C1$, $R2$, $C2$ durch Leerzeichen getrennt.

Ausgabe

• Zeile 1: Ganzzahl $S$ in einer Zeile.

Beispiele

Eingabe 1

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

Ausgabe 1

1

Hinweis

Die Weide hat 4 Reihen und 5 Spalten. Von Reihe 1 Spalte 3 nach Reihe 1 Spalte 5 dauert es genau 6 Sekunden.

Von $(1,3)$ nach $(1,5)$ in genau 6 Sekunden gibt es nur den offensichtlichen Weg um beide Bäume.

Aufgabenautor: Aram Shatakhtsyan, 2007