Lát Gạch Domino Trên Lưới

Buổi 33 — Bitmask DP & SOS DP Buổi 36 — DP on DAG & Profile DP Buổi 40 — Contest Chặng 5
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved