Farmer John có một cánh đồng nhỏ hình lưới $N$ nhân $N$ ($1 \le N \le 2000$), trong đó ô thứ $j$ từ trái sang của hàng thứ $i$ từ trên xuống được ký hiệu là $(i,j)$ với mọi $1 \le i,j \le N$. Ông muốn trồng ngô ngọt và cỏ linh lăng trên cánh đồng của mình. Để làm vậy, ông cần lắp đặt một số vòi phun đặc biệt.

Một vòi phun cho ngô ngọt đặt tại ô $(I,J)$ sẽ tưới tất cả các ô ở phía dưới bên trái: tức là các ô $(i,j)$ thỏa mãn $I \le i$ và $j \le J$.

Một vòi phun cho cỏ linh lăng đặt tại ô $(I,J)$ sẽ tưới tất cả các ô ở phía trên bên phải: tức là các ô $(i,j)$ thỏa mãn $i \le I$ và $J \le j$.

Một ô được tưới bởi một hoặc nhiều vòi phun cho ngô ngọt có thể trồng ngô ngọt; một ô được tưới bởi một hoặc nhiều vòi phun cho cỏ linh lăng có thể trồng cỏ linh lăng. Nhưng một ô được cả hai loại vòi phun tưới (hoặc không được loại nào tưới) thì không thể trồng gì.

Hãy giúp FJ xác định số cách (lấy modulo $10^9 + 7$) lắp đặt vòi phun trên cánh đồng, mỗi ô nhiều nhất một vòi, sao cho mọi ô đều có thể trồng cây (tức là được đúng một loại vòi phun tưới).

Một số ô đã có những con bò lông xù đứng trên đó; điều này không ngăn các ô ấy có thể trồng cây, nhưng không thể lắp vòi phun tại các ô đó.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $N.$

Với mỗi $1\le i\le N,$ dòng thứ $i+1$ chứa một chuỗi độ dài $N$ mô tả hàng thứ $i$ của lưới. Mỗi ký tự của chuỗi là 'W' (chỉ một ô có bò lông xù) hoặc '.' (ô không có bò).

Dữ liệu ra

In ra phần dư khi chia số cách lắp đặt vòi phun cho $10^9+7.$

Ví dụ

Dữ liệu vào 1

2
..
..

Dữ liệu ra 1

28

Ghi chú

Dưới đây là tất cả mười bốn khả năng khi có thể trồng ngô ngọt tại $(1,1)$.

CC  .C  CA  CC  .C  CA  CA  C.  CA  C.  CC  .C  CC  .C  
CC, CC, CC, .C, .C, .C, CA, CA, .A, .A, C., C., .., ..

Dữ liệu vào 2

4
..W.
..WW
WW..
...W

Dữ liệu ra 2

2304

Ghi chú

Ví dụ này thỏa mãn các giới hạn của nhiệm vụ con đầu tiên được mô tả dưới đây.

Nhiệm vụ con

• Các bộ kiểm thử 3–4 thỏa mãn $N\le 10$ và có nhiều nhất mười ô không có bò.
• Các bộ kiểm thử 5–9 thỏa mãn $N\le 200$.
• Các bộ kiểm thử 10–16 không có giới hạn bổ sung.

Tác giả bài toán: Benjamin Qi