Đàn bò đang di chuyển trên một bãi cỏ kích thước . Bãi cỏ có một số ô vuông là cây và không thể di chuyển qua nó. Tại mỗi phút, đàn bò có thể di chuyển đến một trong bốn ô kề cạnh, thỏa mãn chúng không bao giờ đi vào ô có cây hoặc đi ra ngoài đồng cỏ.
Nông dân John đã ghi lại được: đàn bò di chuyển từ ô đến ô trong đúng phút (lũ bò có thể đến ô trước đó hay không, John không thể xác định được, nhưng anh biết chắc chắn sau phút lũ bò đang đứng tại ô ). Xác định số cách di chuyển thỏa mãn ghi chép của John (hai cách di chuyển được gọi là khác nhau, nếu tồn tại một phút nào đó đàn bò di chuyển theo hai hướng khác nhau.
Dữ liệu vào:
Dòng đầu tiên chứa ba số nguyên ;
Trong dòng tiếp theo, dòng thứ chứa xâu kí tự chữ cái. Chữ cái . mô tả một ô trống, * mô tả một ô có cây;
Dòng tiếp theo chứa bốn số nguyên . Dữ liệu đảm bảo các ô và ) là ô trống.
Dữ liệu ra:
Ghi ra một số nguyên duy nhất là số cách đàn bò di chuyển từ ô đến ô .
