소의 여행

소들이 가장 좋은 풀을 찾아 목초지를 돌아다니고 있습니다. 목초지는 $N$행 $M$열 격자로 표현됩니다 ($2 \le N \le 100$, $2 \le M \le 100$). 관찰력이 뛰어난 농부는 어느 시각에 소 베시의 위치를 $(R_1, C_1)$로 기록했고, 정확히 $T$초 ($0 < T \le 15$) 뒤에 $(R_2, C_2)$로 기록했습니다. 소가 $T$초가 되기 전에 $(R_2, C_2)$를 지나쳤는지는 알 수 없지만, 시각 $T$에 그곳에 있다는 것은 확실합니다.

매초 소는 현재 칸에서 상하좌우로 인접한 칸 중 하나로 반드시 이동합니다 (제자리에 머무를 수 없습니다). 목초지에는 나무가 있으며, 소는 나무가 있는 칸을 지날 수 없습니다.

'.'은 빈 목초지, '*'는 나무를 나타내는 목초지 지도가 주어질 때, $(R_1, C_1)$에서 출발하여 정확히 $T$초 만에 $(R_2, C_2)$에 도착하는 서로 다른 이동 방법의 수 $S$를 구하세요.

• 첫째 줄: 공백으로 구분된 세 정수 $N$, $M$, $T$
• 둘째 줄부터 $N+1$째 줄까지: 목초지의 각 행을 나타내며, 각 줄은 '.' 또는 '*'로 이루어진 정확히 $M$개의 문자로 구성됩니다
• $N+2$째 줄: 공백으로 구분된 네 정수 $R_1$, $C_1$, $R_2$, $C_2$

위에서 설명한 정수 $S$를 한 줄에 출력합니다.

예를 들어 목초지가 4행 5열이고 소가 (1행, 3열)에서 (1행, 5열)로 정확히 6초에 걸쳐 이동한다면, 두 그루의 나무를 돌아가는 경로가 유일하므로 정확히 6초 만에 이동하는 방법은 한 가지뿐입니다.