Cow Travelling

Searching for the very best grass, the cows are travelling about the pasture, which is represented as a grid with $N$ rows and $M$ columns ($2 \le N \le 100$, $2 \le M \le 100$). A keen observer, the farmer, recorded cow Bessie's position as $(R_1, C_1)$ at a certain time and then as $(R_2, C_2)$ exactly $T$ ($0 < T \le 15$) seconds later. He is not sure whether she passed through $(R_2, C_2)$ before $T$ seconds, but he knows she is there at time $T$.

Every second, a cow must move from its current cell to a vertically or horizontally adjacent cell (the cows never rest). The pasture also contains trees, and no cow can travel through a tree.

Given the pasture map, where '.' marks open pasture and '*' marks a tree, compute the number $S$ of distinct ways to travel from $(R_1, C_1)$ to $(R_2, C_2)$ in exactly $T$ seconds.

• Line 1: Three space-separated integers $N$, $M$, and $T$
• Lines 2..$N+1$: Each line describes one row of the pasture with exactly $M$ characters, each of which is '.' or '*'
• Line $N+2$: Four space-separated integers $R_1$, $C_1$, $R_2$, and $C_2$

Output the single integer $S$ described above on one line.

For example, if the pasture is 4 rows by 5 columns and the cow travels from (row 1, column 3) to (row 1, column 5) in exactly 6 seconds, there is exactly one such way, since the only route travels around the two trees.