Lát Gạch Domino Trên Lưới
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho một bảng lưới hình chữ nhật kích thước $N \times M$ ($N$ hàng, $M$ cột). Hãy đếm số cách lát kín toàn bộ bảng bằng các quân domino kích thước $1 \times 2$ hoặc $2 \times 1$ sao cho không có hai quân nào chồng lên nhau và không có ô nào bị thừa. In ra kết quả modulo $10^9 + 7$.
Dữ liệu vào
Một dòng duy nhất chứa hai số nguyên $N$ và $M$.
Dữ liệu ra
In ra số cách lát gạch hợp lệ modulo $10^9 + 7$.
Ví dụ
| Input | Output |
|---|---|
2 3 |
3 |
3 3 |
0 |
4 3 |
11 |
Giới hạn
- $1 \le N \le 10$
- $1 \le M \le 1000$
Community Discussion