가장 좋은 풀을 찾아 소들이 $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)$입니다. $T$초 전에 $(R2, C2)$를 지났는지는 모르지만 시각 $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