Vinh chuẩn bị đi thi Olympic Tin học thành phố. Sau khi xếp vào túi mọi giấy tờ cần thiết Vinh vào Internet tra cứu đường đi. Thật thú vị khi trên đường đi có một công viên. Bản đồ chỉ rõ công viên được chia thành các ô vuông kích thước , mỗi ô có thể được trồng cỏ và có đường đi qua, có thể đó là ô có đặt phù điêu, có cây to hoặc là ô có bồn hoa, những ô này dĩ nhiên không có đường đi. Trên bản đồ có một đánh dấu chỉ lối vào và ô đánh dấu chỉ lối ra. Các ô này không
nhất thiết nằm ở biên (được dẫn vào hay ra bằng đường ngầm). Một hàng rào bao quanh công viên (trừ lối vào/ra nếu có).
Vinh tính ra rằng để đi qua hết một ô cần giây và nếu đi theo đường ngắn nhất từ lối vào đến lối ra thì dự trữ thời gian vẫn còn giây! Không thể lãng phí thời gian, Vinh quyết định dạo chơi thêm giây trong công viên và di chuyển liên tục, từ một ô có thể tiến lên phía trước, rẽ trái, phải hoặc quay lui.
Hãy xác định số lượng đường đi khác nhau có thể thực hiện và đưa ra kết quả theo mô đun . Hai đường đi gọi là khác nhau nếu chứa ô mới không có trong đường đi kia hoặc chứa ô đi lặp lại khác nhau.
Dữ liệu vào:
Dòng đầu tiên chứa hai số nguyên và ;
Mỗi dòng trong dòng sau chứa xâu độ dài xác định một dòng của bản đồ công viên, các ký tự trong xâu thuộc tập , trong đó ký tự . chỉ ô có đường đi, ký tự # chỉ ô không đi qua được. Chỉ có đúng một ô 𝑬 và một ô 𝑿.
Dữ liệu ra:
Ghi ra một số nguyên duy nhất là kết quả tìm được. Nếu không tồn tại đường đi từ đến thì đưa ra số .
