Nhiệm vụ của bạn là tạo một lưới \(n \times n\) mà mỗi hàng và cột có chính xác một A và B. Một số kí tự đã được đặt. Bạn có thể hoàn thành lưới bằng bao nhiêu cách?

Input

• Dòng đầu vào đầu tiên chứa một số nguyên \(n\): kích thước của lưới
• Sau đó, có \(n\) dòng mô tả lưới. Mỗi dòng có \(n\) kí tự: . có nghĩa làm một hình vuông trống, và A và B hiển thị các kí tự đã được đặt
• Bạn có thể giả định rằng mỗi hàng và cột có nhiều nhất một A và B

Constraints

• \(1 \leq n \leq 500\)

Output

• In một số nguyên: số cách chia lấy dư cho \(10^9 + 7\)

Example

5
.....
..AB.
.....
B....
...A.

16