题目描述

给出一个带障碍的迷宫。你必须从起点出发，恰好走 $k$ 步到达终点。每步只能向上、下、左、右移动一格，不能进入障碍，且同一个格子不能重复经过。

请判断是否存在这样的路线。

输入格式

第一行输入 $n,m,k$。第二行输入起点与终点坐标 $s_x,s_y,t_x,t_y$。接下来 $n$ 行输入迷宫，. 表示可通行，# 表示障碍。

输出格式

存在则输出 YES，否则输出 NO。

样例

4 4 6
1 1 4 4
....
.#..
..#.
....

YES

数据规模与约定

• $1\le n,m\le8$；$0\le k\le20$；
• 起点、终点均可通行；同一个格子不能重复经过。