Cow Grazing Paths

Farmer John observes that cows wander on an $N \times M$ grid (with $2 \leq N, M \leq 100$) in search of the tastiest grass. At one moment, he sees Bessie at $(R_1, C_1)$ and exactly $T$ seconds later, he finds her at $(R_2, C_2)$. In each second the cow moves one unit in either the horizontal or vertical direction (it never stands still). Some cells of the grid contain trees (denoted by *) which block the cow, while open grass cells are denoted by .. Given the grid and the start and end positions, compute the number $S$ of distinct paths by which the cow can move from $(R_1, C_1)$ to $(R_2, C_2)$ in exactly $T$ seconds without ever stepping into a cell containing a tree or leaving the grid.

inputFormat

The first line contains three integers: N, M, and T.

The second line contains two integers: R1 and C1, the starting coordinates.

The third line contains two integers: R2 and C2, the destination coordinates.

The following N lines each contain a string of M characters representing the grid, where a dot (.) denotes grass and an asterisk (*) denotes a tree.

outputFormat

Output a single integer representing the number of distinct valid paths from the starting position to the destination in exactly T seconds.

sample

3 3 2
1 1
1 3
...
...
...

1