Tìm cỏ tốt nhất, bò đi trên lưới $N$ hàng $M$ cột, $(2 \le N \le 100; 2 \le M \le 100)$. Farmer John tinh mắt ghi Bessie tại $(R1, C1)$ rồi đúng $T$ giây sau ở $(R2, C2)$, $(0 \lt T \le 15)$. Không biết đã qua $(R2, C2)$ trước khi $T$ giây trôi qua chưa, nhưng thời điểm $T$ cô ở đó.

Tính số nguyên $S$, số cách từ $(R1, C1)$ đến $(R2, C2)$ trong đúng $T$ giây. Mỗi giây phải đi sang ô kề dọc hoặc ngang, không nghỉ. Cây không đi qua được.

. là đất trống, * cây. Đếm đường từ $(R1, C1)$ đến $(R2, C2)$ trong $T$ giây.

Dữ liệu vào

• Dòng 1: ba số nguyên $N$, $M$, $T$ cách bởi khoảng trắng.
• Dòng $2,\ldots,N+1$: dòng $i+1$ mô tả hàng $i$ bằng đúng $M$ ký tự . hoặc *.
• Dòng $N+2$: bốn số nguyên $R1$, $C1$, $R2$, $C2$ cách bởi khoảng trắng.

Dữ liệu ra

• Dòng 1: số nguyên $S$ trên một dòng.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1

Ghi chú

Đồng cỏ 4 hàng 5 cột. Từ hàng 1 cột 3 đến hàng 1 cột 5 mất đúng 6 giây.

Từ $(1,3)$ đến $(1,5)$ đúng 6 giây chỉ có đường hiển nhiên vòng hai cây.

Tác giả bài toán: Aram Shatakhtsyan, 2007