Mê Cung Tic-Tac-Toe

Bessie di chuyển trong một mê cung $N\times N$ và đồng thời chơi trò tic-tac-toe trên bảng $3\times 3$.

Luật tic-tac-toe phiên bản bò: Bảng $3\times 3$ sử dụng ký tự M và O. Điều kiện thắng: tạo chuỗi MOO theo hàng, cột hoặc đường chéo (bao gồm cả chiều ngược OOM).

Mê cung: Lưới $N\times N$, mỗi ô biểu diễn bằng 3 ký tự:

• ###: tường (không đi qua được)
• ...: ô trống
• BBB: vị trí xuất phát của Bessie
• Mij hoặc Oij: khi Bessie bước vào ô này, ký tự M hoặc O được đặt vào vị trí $(i,j)$ trên bảng tic-tac-toe (nếu ô đó còn trống)

Bessie di chuyển theo 4 hướng (trên, dưới, trái, phải). Viền mê cung và các ô ### là tường. Trò chơi kết thúc ngay khi bảng tic-tac-toe đạt trạng thái thắng.

Hãy đếm số trạng thái bảng thắng phân biệt mà Bessie có thể đạt được.

Dữ liệu vào

• Dòng 1: Số nguyên $N$ ($3\le N\le 25$)
• $N$ dòng tiếp theo: Mỗi dòng gồm $3N$ ký tự mô tả mê cung

Dữ liệu ra

Một số nguyên: số trạng thái bảng thắng phân biệt.

Ràng buộc

• $3\le N\le 25$

Ví dụ