Profile DP: Lát gạch bảng M x N bằng Domino và Tromino

Mô tả bài toán

Cho một lưới ô vuông kích thước M × N gồm M hàng và N cột.

Bạn có vô số viên gạch kích thước 2 × 1 (Domino), có thể xoay ngang hoặc dọc (1 × 2 hoặc 2 × 1).

Yêu cầu: Đếm số cách lát kín hoàn toàn lưới M × N bằng các viên gạch domino sao cho các viên gạch không chồng đè lên nhau và không có ô nào bị bỏ trống. Kết quả được lấy dư theo modulo 10⁹ + 7.

Dữ liệu vào

• Một dòng duy nhất chứa hai số nguyên M, N (1 ≤ M ≤ 8, 1 ≤ N ≤ 1000).

Dữ liệu ra

• In ra một số nguyên duy nhất là số cách lát theo modulo 10⁹ + 7.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• Thời gian chạy tối đa: 2000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng định dạng và miền giá trị được mô tả.