[Usaco2008 Mar]Cow Travelling游荡的奶牛

奶牛们在一片被划分为 $N$ 行 $M$ 列的草地上游走，寻找美味的牧草。

Farmer John 在某一时刻看到贝茜位于 $(R_1,C_1)$。恰好 $T$ 秒后，他又在 $(R_2,C_2)$ 遇到了贝茜。Farmer John 不知道贝茜在这 $T$ 秒内是否曾提前到达 $(R_2,C_2)$，只能确定她在第 $T$ 秒结束时位于该位置。

每秒钟，奶牛必须向水平或垂直方向移动 $1$ 格，不能停留在原地。草地上的一些位置生长着树，奶牛不能进入这些位置，也不能走出草地边界。

用字符 . 表示平坦的草地，用字符 * 表示挡路的树。请计算贝茜在恰好 $T$ 秒内从 $(R_1,C_1)$ 移动到 $(R_2,C_2)$ 的路径总数 $S$。

输入格式

第一行包含 $3$ 个以空格分隔的整数 $N$、$M$、$T$，分别表示草地的行数、列数和移动时间。

接下来 $N$ 行，每行包含 $M$ 个连续字符，描述草地对应一行的地形。每个字符均为 . 或 *。

最后一行包含 $4$ 个以空格分隔的整数 $R_1$、$C_1$、$R_2$、$C_2$，分别表示起点和终点的行、列坐标。

输出格式

输出一个整数 $S$，表示奶牛在恰好 $T$ 秒内从 $(R_1,C_1)$ 移动到 $(R_2,C_2)$ 的路径总数。

样例输入

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

样例输出

1

样例解释

草地共有 $4$ 行 $5$ 列。奶牛需要在恰好 $6$ 秒内从第 $1$ 行第 $3$ 列移动到第 $1$ 行第 $5$ 列。满足条件的路径只有 $1$ 条，即绕过起点右侧的树。

数据范围

• $2\le N\le 100$；
• $2\le M\le 100$；
• $0<T\le 15$。

来源与许可

本题为 USACO 2008 March 试题「Cow Travelling（游荡的奶牛）」，题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

1