Lát gạch sàn thông minh

Buổi 67-68 — Mock IOI Dynamic Programming
Points
100
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions

Đề bài

Cho một sàn nhà hình chữ nhật kích thước $N \times M$ gồm $N$ hàng và $M$ cột. Mỗi ô trên sàn có thể là ô trống (.) hoặc ô bị hỏng (#).

Ta cần lát kín tất cả các ô trống bằng các viên gạch domino kích thước $1 \times 2$ hoặc $2 \times 1$ sao cho các viên gạch không chồng lên nhau, không chờm ra ngoài bảng và không đặt lên ô #. Hãy đếm số cách lát hợp lệ, lấy phần dư cho $10^9 + 7$.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên $N$ và $M$ ($1 \le N \le 10$, $1 \le M \le 100$).
  • $N$ dòng tiếp theo, mỗi dòng là một xâu độ dài $M$ chỉ gồm các ký tự . và #.

Kết quả

  • In ra một số nguyên duy nhất là số cách lát hợp lệ modulo $10^9 + 7$.

Subtasks

  • Subtask 1 (25% số điểm): $N \le 4$, $M \le 10$.
  • Subtask 2 (25% số điểm): Không có ô #.
  • Subtask 3 (50% số điểm): Không có ràng buộc bổ sung.

Ví dụ

Input Output
3 3
...
.#.
...
2
Draft saved