Vòi Phun Nước 2

Farmer John có một trang trại dạng lưới $N\times N$ ($1\le N\le 2000$). Mỗi ô $(i,j)$ (hàng $i$, cột $j$, đánh số từ $1$) hoặc là trống (.) hoặc bị một con bò chiếm (W) — các ô có bò không thể đặt vòi phun.

Farmer John muốn tưới toàn bộ lưới bằng hai loại vòi phun:

• Vòi ngô ngọt đặt tại $(I,J)$ tưới tất cả ô $(i,j)$ với $i\ge I$ và $j\le J$ (vùng dưới-trái).
• Vòi cỏ linh lăng đặt tại $(I,J)$ tưới tất cả ô $(i,j)$ với $i\le I$ và $j\ge J$ (vùng trên-phải).

Yêu cầu: Mỗi ô $(i,j)$ phải được tưới bởi đúng một loại vòi (hoặc chỉ ngô ngọt, hoặc chỉ cỏ linh lăng). Đếm số cách lắp đặt vòi phun hợp lệ, lấy modulo ${10}^9+7$.

Lưu ý: Một ô trống có thể không có vòi nào, có một vòi ngô ngọt, hoặc có một vòi cỏ linh lăng — miễn là điều kiện phủ sóng được thỏa mãn.

Dữ liệu vào

• Dòng đầu: số nguyên $N$.
• $N$ dòng tiếp theo, mỗi dòng gồm $N$ ký tự . hoặc W.

Dữ liệu ra

Một số nguyên duy nhất — số cấu hình hợp lệ modulo ${10}^9+7$.

Ràng buộc

• $1\le N\le 2000$

Ví dụ

Ghi chú

Trong ví dụ 1, lưới $2\times 2$ gồm 4 ô trống. Mỗi cách phân chia hợp lệ ứng với một đường đi từ góc trên-trái xuống biên dưới hoặc biên phải của lưới, phân tách vùng tưới bởi vòi ngô ngọt (dưới-trái) và vùng tưới bởi vòi cỏ linh lăng (trên-phải).