Description

Cows wander on a pasture divided into $N$ rows and $M$ columns ($2 \leq N, M \leq 100$), trying to find the tastiest grass.

At some moment, Farmer John sees Bessie at position $(R_1, C_1)$. Exactly $T$ ($0 < T \leq 15$) seconds later, FJ runs into Bessie at position $(R_2, C_2)$. FJ does not know whether Bessie visited $(R_2, C_2)$ at any time during those $T$ seconds; he only knows that she is there now.

Let $S$ be the number of paths the cow can take to go from $(R_1, C_1)$ to $(R_2, C_2)$ in $T$ seconds. FJ wants a program to compute this value. Each second, the cow moves horizontally or vertically by a distance of $1$ (the cow is always moving and will not stay at the same point in any second). Some places on the pasture have trees. Of course, the cow cannot step on a tree, and she will not leave the pasture.

You are given a map of the whole pasture, where . means open grass and * means a blocking tree. Your task is to compute how many different paths a cow can take to move from $(R_1, C_1)$ to $(R_2, C_2)$ in $T$ seconds.

Input Format

The first line contains $3$ space-separated integers: $N, M, T$.

Then $N$ lines follow: the $i$-th line has $M$ consecutive characters describing row $i$ of the pasture. Each character is guaranteed to be either . or *.

The last line contains $4$ integers $R_1, C_1, R_2, C_2$.

Output Format

Output the number of ways to move from $(R_1, C_1)$ to $(R_2, C_2)$.

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

1

Hint

There is only one way for the cow to go from $(1, 3)$ to $(1, 5)$ in $6$ seconds, by going around the tree in front of her.

Translated by ChatGPT 5