牛は最良の草を探し、$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)$ からちょうど $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)$ から $(1,5)$ へちょうど 6 秒の方法は一つだけで、二本の木を回り込む明らかな経路です。
問題作成者：Aram Shatakhtsyan、2007