母牛為尋找最好的草，在 $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$ 她在那裡。
FJ 想算整數 $S$，即從 $(R1, C1)$ 恰好 $T$ 秒到 $(R2, C2)$ 的走法數。每秒必須走到上下左右相鄰位置，不能休息。牧場的樹不能通過。
地圖 . 表示空地、* 表示樹，求從 $(R1, C1)$ 在 $T$ 秒到 $(R2, C2)$ 的可能走法數。
輸入格式
- 第 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)$ 恰好 6 秒到 $(1,5)$ 只有一種走法，即明顯繞過兩棵樹的路徑。
題目作者：Aram Shatakhtsyan，2007