بحثًا عن أفضل عشب تجوب الأبقار مرعى من $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)$. لا يعرف إن مرت بـ$(R2, C2)$ قبل انقضاء $T$ ثانية، لكنها هناك بالوقت $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