В поисках лучшей травы коровы путешествуют по пастбищу из $N$ строк и $M$ столбцов, $(2 \le N \le 100; 2 \le M \le 100)$. Наблюдательный Farmer John записал Bessie в $(R1, C1)$, а ровно через $T$ секунд в $(R2, C2)$, $(0 \lt T \le 15)$. Не знает, бывала ли она в $(R2, C2)$ раньше, чем прошло $T$ секунд, но в момент $T$ она там.

Нужно целое $S$ — число путей из $(R1, C1)$ в $(R2, C2)$ ровно за $T$ секунд. Каждую секунду корова идёт в вертикального или горизонтального соседа, без отдыха. Через деревья идти нельзя.

На карте . — свободное место, * — дерево. Посчитайте пути из $(R1, C1)$ в $(R2, C2)$ за $T$ секунд.

Входные данные

• Строка 1: три целых $N$, $M$, $T$ через пробел.
• Строки $2,\ldots,N+1$: строка $i+1$ задаёт ряд $i$, ровно $M$ символов . или *.
• Строка $N+2$: четыре целых $R1$, $C1$, $R2$, $C2$ через пробел.

Выходные данные

• Строка 1: целое $S$ одной строкой.

Примеры

Входные данные 1

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

Выходные данные 1

1

Примечание

Пастбище 4 на 5, путь из строки 1 столбца 3 в строку 1 столбец 5 занимает ровно 6 секунд.

Из $(1,3)$ в $(1,5)$ за ровно 6 секунд есть лишь очевидный путь вокруг двух деревьев.

Автор задачи: Aram Shatakhtsyan, 2007