Vòi Phun Nước 2

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Farmer John có một trang trại dạng lưới $N \times N$ ( $1 \leq N \leq 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 \geq I$ và $j \leq 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 \leq I$ và $j \geq 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 \leq N \leq 2000$

Ví dụ

Input	Output	Giải thích
2 .. ..	28	Lưới $2 \times 2$ toàn ô trống, có $28$ cách phủ hợp lệ.
4 ..W. ..WW WW.. ...W	2304	Lưới $4 \times 4$ với một số ô bị bò chiếm.

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

Bình luận

Không có bình luận tại thời điểm này.