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.

Output

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

Constraints

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

Example

Input:

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

Output:

16