---
# System prepended metadata

title: 'USACO 2021 US OPEN, Silver'

---

# USACO 2021 US OPEN, Silver
## Vấn đề 1. MAZE TAC TOE
---
Cô bò Bessie thích rất thích giải mê cung. Song, cô cũng thích chơi $Tic-Tac-Toe$ (phiên bản dành cho những cô bò). Anh nông dân John đã nảy ra ý tưởng giúp cô có thể chơi cùng lúc cả 2 trò.

Đầu tiên, ở trò $Tic-Tac-Toe$ dành cho bò, thay vì điền $X$ hoặc $O$ vào bảng ô vuông $3\times3$, cô bò sẽ điền kí tự $M$ hoặc $O$. Ở mỗi lượt chơi, cô có thể đặt hoặc là $M$ hoặc là $O$ tại một ô trống (khác với phiên bản thông thường là một người chỉ được điền $X$ và người còn lại điền $O$). Người chiến thắng của trò chơi này chính là người đầu tiên có thể điền được từ $MOO$ bất kể hàng ngang, hàng dọc, hay đường chéo. Và chiều ngược lại cũng được tính, ví dụ người chơi có thể có $OOM$ trên một hàng. Tuy nhiên như bản gốc, trường hợp người chơi không thể thắng cũng có thể xảy ra. Mỗi lượt chơi được kí hiệu bởi 3 kí tự $Mij$ hoặc $Oij$, với $i,j \in [1,3]$ ($i$ là số dòng, $j$ là số cột), thể hiện cho vị trí trong bảng mà ta điền vào kí tự $M$ hoặc $O$ tương ứng. 

Để thử thách Bessie, anh nông dân John đã thiết kế một mê cung hình vuông có kích thước $N \times N$, $(3 \leq N \leq 25)$ được tạo từ các ô vuông đơn vị. Một số ô, bao gồm tất cả các ô ở cạnh bảng, sẽ có chướng ngại vật ngăn không cho Bessie đi tới. Bessie có thể di chuyển tự do ở các ô không có chướng ngại vật theo 4 hướng **ĐÔNG, TÂY, NAM, BẮC**. Một số ô sẽ có 1 mảnh giấy chứa thông tin của một lượt chơi của trò $Tic-Tac-Toe$ dành cho Bessie. Trong khi giải mê cung, mỗi khi Bessie bước đến các ô có mảnh giấy chứa thông tin về lượt chơi, cô buộc phải thực hiện lượt chơi ấy (trường hợp cô đã đến ô này trước đó thì cô không làm gì). Cô không có đối thủ cùng tham gia trò chơi. Tuy nhiên một số ô trong mê cung sẽ ngăn cô ấy hoàn thành từ $MOO$.

Giả sử Bessie dừng trò chơi ngay khi thắng, hãy xác định số cấu hình chiến thắng phân biệt trong trò chơi $Tic-Tac-Toe$ mà cô ấy có thể đạt được trong quá trình giải mê cung.

## INPUT (nhập từ bàn phím / stdin)

Dòng đầu tiên là $N$.

$N$ dòng tiếp theo chứa $3 \times N$ kí tự. 

>Mỗi ô trong mê cung được mô tả bởi một khối gồm 3 kí tự, **'###'** là chứa ngại vật, **'...'** là không gian trống, **'BBB'** là vị trí của Bessie. Khi di chuyển Bessie đến ô có thông tin lượt chơi, cô bắt buộc phải thực hiện lượt chơi đó. Vị trí của Bessie là duy nhất.

## OUTPUT (màn hình / stdout)
In ra số lượng cấu hình thỏa yêu cầu đề bài.
> Số cấu hình có thể là 0.

## VÍ DỤ
### Input:
```
7
#####################
###O11###...###M13###
###......O22......###
###...######M22######
###BBB###M31###M11###
###...O32...M33O31###
#####################
```

### Output:

```8```
Ở ví dụ trên, 8 là số cấu hình chiến thắng tối đa mà Bessie có thể đạt được.
    
```
O.M
.O.
MOM
```

```
O..
.O.
.OM
```

```
O.M
.O.
.OM
```

```
O..
.O.
MOM
```

```
O..
...
OOM
```

```
..M
.O.
OOM
```

```
...
.O.
OOM
```

```
...
...
OOM
```

Để giải thích một các kết quả trên, xét trường hợp sau:
```
O..
...
OOM
```

Ở đây Bessi có thể thăm ô $O11$ đầu tiên rồi di chuyển đến các ô $O32$ rồi $M33$ rồi $O31$. Trò chơi dừng lại sau đó khi Bessie đã thắng (chính vì vậy mà Bessie sẽ không thể đi đến ô $M11$).



