[KHTN - PreTS10 - 2025] Bài 4: TITLE3
Xem dạng PDF
Gửi bài giải
Điểm:
20,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch, TEXT
Cho một bảng hình chữ nhật gồm ~N~ hàng và ~M~ cột được tạo bởi ~N \times M~ ô vuông đơn vị. Có ~K~ ô trong bảng đã được đánh dấu. Hãy đếm số cách lát kín những ô không bị đánh dấu bằng những viên gạch hình chữ nhật kích cỡ ~1 \times 2~ hoặc ~2 \times 1~ sao cho mỗi viên gạch phải nằm hoàn toàn trong bảng và không có 2 viên gạch nào chồng lên nhau. Không được đặt viên gạch lên ô bị đánh dấu.
INPUT
- Dòng đầu tiên ghi 3 số nguyên dương ~N, M, K~ (~1 \le N \le 10, 1 \le M \le 1000, 0 \le K \le N \times M~)
- Trong ~K~ dòng sau, dòng thứ ~i~ gồm 2 số nguyên dương ~X_i, Y_i~ (~1 \le X_i \le N; 1 \le Y_i \le M~) là tọa độ của ô vuông thứ ~i~ bị đánh dấu.
OUTPUT
Một số nguyên duy nhất là kết quả của bài toán. Vì kết quả có thể rất lớn, hãy in ra kết quả modulo ~10^9+7~
SUBTASKS
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| ~1~ | ~25~ | ~N \le 2~ |
| ~2~ | ~25~ | ~N = 3, K = 0.~ |
| ~3~ | ~50~ | Không có ràng buộc gì thêm. |
SAMPLE INPUT
2 4 2
1 4
2 2
SAMPLE OUTPUT
1
Giải thích: Ta lát như hình dưới đây (những ô màu đen là bị đánh dấu, 2 ô có cùng số thuộc cùng 1 viên gạch).
Bình luận
tung tung tung sahur