Sau một ngày Giáng Sinh đầy niềm vui với những trò chơi và thử thách thú vị, ABNL muốn kết lại ngày lễ bằng một hoạt động thật đặc biệt: trượt tuyết. Sau một hồi tìm kiếm, ABNL đã phát hiện ra một sân trượt tuyết tuyệt đẹp – một mạng lưới \(N \times N\) được phủ đầy tuyết trắng. Nhưng chơi một mình không vui, ABNL quyết định rủ tất cả coder đến trượt tuyết cùng.

Sân trượt tuyết này có cấu trúc thú vị:

• Các ô tuyết bình thường là khoảng trống, được ký hiệu là .
• Một số ô đặc biệt được gọi là nền trượt tuyết (ký hiệu P), nơi các coder có thể đứng và bắt đầu cuộc hành trình lướt đi trên mặt tuyết.

ABNL đề xuất một luật chơi: mỗi người chơi sẽ chọn một nền trượt tuyết làm điểm xuất phát, và từ đó, họ sẽ trượt sang phải hoặc trượt xuống dưới đến các nền trượt tuyết khác. Để tăng thêm phần thú vị, ABNL đặt thêm một quy tắc "quay đầu là bờ": nếu một coder trượt ra khỏi mép sân, họ sẽ quay ngược lại từ mép đối diện và tiếp tục trượt theo hướng ban đầu. Đồng thời, người chơi không thể nhảy vượt qua một nền trượt tuyết để đến một nền khác. Xem hình minh họa:

Vì tất cả các coder đều rất hào hứng, mỗi nền trượt tuyết P ban đầu sẽ có đúng một coder đứng sẵn. Nhưng sau khi trượt, nếu hai người chơi cùng trượt đến một nền trượt tuyết, họ sẽ va vào nhau, khiến cuộc chơi bị gián đoạn. Để tránh điều này, ABNL quyết định đặt mũi tên chỉ hướng trên mỗi nền trượt tuyết P để điều chỉnh hướng di chuyển của các người chơi. Các coder phải tuân thủ hướng mũi tên để trượt, và không được chọn hướng khác. Ở mỗi lượt chơi, các coder trượt lần lượt theo thứ tự ABNL chỉ định, coder đứng ở một nền tuyết sẽ trượt theo hướng mũi tên được chỉ định của ô đó và dừng ở ô đầu tiên họ gặp (xem hình minh họa ở trên). Hai coder sẽ va chạm nhau chỉ khi hai bạn đó cùng dừng chân ở chung một nền trượt tuyết trong lượt đó.

Vì đang bận sắp xếp vị trí cho mọi người, ABNL nhờ bạn giúp tính toán: có bao nhiêu cách khác nhau để đặt mũi tên chỉ hướng (chỉ sang phải hoặc xuống dưới) cho tất cả các nền trượt tuyết P sao cho không có hai coder nào va vào nhau?

Input

• Dòng đầu tiên chứa số nguyên \(N\) \((1 \leq N \leq 800)\) là kích thước sân trượt tuyết
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) ký tự:
  • . đại diện cho tuyết bình thường
  • P đại diện cho nền trượt tuyết
• Dữ liệu đảm bảo sẽ luôn có ít nhất một nền trượt tuyết P trong sân.

Output

• In ra một số nguyên duy nhất: số cách khác nhau để gắn mũi tên chỉ hướng cho tất cả các nền trượt tuyết P mà không để xảy ra va chạm giữa các coder. Mặc dù đáp án có thể rất lớn, dữ liệu đảm bảo đáp án nằm trong phạm vi của một số nguyên có dấu 64-bit (giúp ABNL có thể dễ dàng lưu trữ và phân tích hơn).

Example

6
P.P...
.P...P
P.P.P.
.P..P.
..P..P
......

8

3
...
.P.
...

2