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

Một vòi phun ngô ngọ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 \leq i\) và \(j \leq J\).

Một vòi phun cỏ linh lăng 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 \leq I\) và \(J \leq j\).

Một ô được một hoặc nhiều vòi phun ngô ngọt tưới có thể trồng ngô ngọt; một ô được một hoặc nhiều vòi phun cỏ linh lăng tưới có thể trồng cỏ linh lăng. Tuy nhiên, 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 được gì.

Hãy giúp FJ xác định số cách 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 màu mỡ (tức là được đúng một loại vòi phun tưới). Hãy tính số cách theo modulo \(10^9+7\).

Một số ô đã có những con bò lông xù chiếm chỗ; điều này không ngăn các ô đó trở nên màu mỡ, nhưng không thể lắp vòi phun tại những ô này.

Dữ liệu vào

Tệp sprinklers2.in:

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

Với mỗi \(1 \leq i \leq N\), dòng thứ \(i+1\) chứa một xâu độ dài \(N\) mô tả hàng thứ \(i\) của lưới. Mỗi ký tự trong xâu là W (biểu thị một ô có bò lông xù chiếm chỗ) hoặc . (biểu thị ô trống).

Dữ liệu ra

Tệp sprinklers2.out:

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

Phân nhóm

• Các test 3–4 thỏa mãn \(N \leq 10\) và có nhiều nhất mười ô trống.
• Các test 5–9 thỏa mãn \(N \leq 200\).
• Các test 10–16 không có ràng buộc bổ sung.

Ví dụ

2
..
..

28

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., .., ..

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

2304

Nguồn

USACO 2020 US Open Contest, Platinum — Sprinklers 2: Return of the Alfalfa

Tác giả bài: Benjamin Qi.