Một cô bò Bessie rất thích chơi giải mê cung. Ngoài ra, cô ấy cũng thích chơi cờ Caro (nói đúng hơn là cờ Caro dành cho bò mà ta sẽ nói tới ở phía dưới). Bác nông dân John đã tìm ra một cách để cô bò Bessie có thể chơi cả 2 trò cùng lúc. Đầu tiên, ta định nghĩa trò Caro bò như sau: Thay vì đặt các dấu 'X' và 'O' trên bàn cờ 3x3 thì các chú bò sẽ dùng 'M' và 'O'. Trong một bước đi, chú bò có thể đặt 'M' hoặc 'O' lên bất kì một ô trống nào trên bàn (khác với trò Caro thông thường khi một người chơi chỉ có thể dùng 'X' và người còn lại chỉ có thể dùng 'O'). Người chiến thắng trong trò chơi này là người có thể viết được chữ 'MOO' hoặc ngược lại('OOM'). Một nước đi được biểu diễn bằng 3 kí tự, 'Mij' hay 'Oij' với i,j nằm trong khoảng 1...3 và nó thể hiện số hàng và cột mà dấu 'M' hoặc 'O' được đặt. Để thử thách cô bò Bessie, bác John đã tạo ra mê cung vuông NxN ô (3 ≤ N ≤ 25). Một số ô, bao gồm những ô ở rìa mê cung chứa đống rơm lớn nhằm ngăn Bessie đi qua. Bessie có thể di chuyển tự do trong các ô còn lại, theo 4 hướng Đông, Tây, Nam và Bắc. Một số ô sẽ có mảnh giấy ghi một bước đi trên cờ Caro. Khi Bessie đi vào ô đó, cô bắt buộc phải đi nước đó trên bàn cờ Caro mà cô đang chơi trừ trường hợp ô đó đã bị đánh dấu trên trên bàn cờ. Trong trò này, Bessie không có đối thủ, tuy nhiên một số ô trong mê cung ngăn cản mục tiêu viết được chữ 'MOO'( hoặc 'OOM') của cô ấy. Giả sử, Bessie dừng trò chơi ngay khi cô ấy chiến thắng, hãy xác định có tất cả bao nhiêu cách để cô ấy có thể chiến thắng bằng cách di chuyển trong mê cung. **Input** --- Dòng đầu tiên chứa *N* số nguyên. Mê cung được biểu diễn thành *N* dòng, mỗi dòng chứa *3N* kí tự. Mỗi ô được biểu thị bằng 3 kí tự liên tiếp, '###' là đống rơm, '...' là ô trống, 'BBB' là vị trí của Bessie, và các ô chứa mảnh giấy ghi bước đi như đã định nghĩa ở trên. Chỉ duy nhất một ô là 'BBB'. **Output** --- In ra một số nguyên thể hiện số cách chiến thắng trò Caro bò (có thể bằng 0) mà Bessie có thể đạt được thông qua mê cung. **Sample Input** --- ``` 7 ##################### ###O11###...###M13### ###......O22......### ###...######M22###### ###BBB###M31###M11### ###...O32...M33O31### ##################### ``` **Sample output** --- ``` 8 ``` Trong ví dụ này, có 8 cách Bessie có thể chiến thắng là: ``` O.M O.. .O. .O. MOM .OM O.M O.. .O. .O. .OM MOM O.. ..M ... .O. OOM OOM ... ... .O. ... OOM OOM ``` Để giải thích cho các cách trên, ta lấy một ví dụ sau đây ``` O.. ... OOM ``` Bessie bắt đầu di chuyển đến vị trí ô O11, sau đó đến O32,M33 và O31. Trò chơi ngay lập tức dừng lại vì cô ấy đã chiến thắng (trong ví dụ này, cô ấy không thể di chuyển đến ô M11 phía trên vị trí đang đứng của cô ấy O31).