Quy hoạch động trên biên dạng nứt (Broken Profile DP / Domino Tiling)

Mục tiêu kiến thức

• Hiểu phương pháp Quy hoạch động trên biên dạng nứt (Broken Profile DP / Plug DP): Thay vì chuyển trạng thái theo cả cột O(N · 4^M), ta duyệt lần lượt từng ô (i, j) theo thứ tự từ trái sang phải, từ trên xuống dưới.
• Biên dạng tại ô (i, j) gồm M bit lưu trạng thái phủ của M ô lân cận.
• Giảm độ phức tạp chuyển trạng thái xuống O(N · M · 2^M) với hằng số cực nhỏ.

Mô tả bài toán

Cho một bảng lưới chữ nhật kích thước N × M. Hãy tính số cách lát kín bảng này bằng các thanh domino kích thước 1 × 2 và 2 × 1 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

• 1 ≤ N ≤ 100, 1 ≤ M ≤ 10.
• Thời gian: 1000ms. Bộ nhớ: 256MB.