You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

不要被平日做惯的模板牵着鼻子走。你觉得该怎么做正确就怎么做！

题目描述

你在自己最不喜欢的课上睡着了，做了一个白日梦，在梦里依然不能摆脱信息学噩梦的笼罩：

你梦见自己身处一个 $N$ 行 $M$ 列的迷宫，每一秒必须垂直或水平移动 $1$ 个格子，永不停歇；当然，必须在迷宫范围内移动，且遇到迷宫内的障碍物时只能避开。

迷宫地图中，. 表示空地，* 表示障碍物。

既然必须不停移动，闲着也是闲着，你干脆给自己出了一道非常应景的题：统计一下，正好花费 $T$ 秒，从格子 $(R_1, C_1)$ 走到 $(R_2, C_2)$ 一共有多少条不同的路径。

提醒：不管你是怎么走的，反正只要从 $(R_1, C_1)$ 出发，第 $T$ 秒到达 $(R_2, C_2)$ 即可。

输入格式

第一行包含 $3$ 个用空格隔开的整数：$N,M,T$。

接下来 $N$ 行：第 $i$ 行为 $M$ 个连续的字符，描述了迷宫第 $i$ 行各点的情况，保证一定是字符 . 或 *。

最后一行 $4$ 个整数 $R_1,C_1,R_2,C_2$。

输出格式

输出从 $(R_1, C_1)$ 移动到 $(R_2, C_2)$ 且正好花费 $T$ 秒的路径方案总数。

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

1

提示

花费 $6$ 秒从 $(1,3)$ 走到 $(1,5)$ 的方法只有一种：$(1,3) \rightarrow (2,3) \rightarrow (3,3) \rightarrow (3,4) \rightarrow (3,5) \rightarrow (2,5) \rightarrow (1,5)$

数据范围

• $2 \leq N,M \leq 100$
• $0<T\le 15$