Cho lưới chữ nhật kích thước n×m. Hãy đếm số cách lát kín lưới bằng các viên gạch domino 1×2 (mỗi viên phủ hai ô kề nhau, đặt ngang hoặc dọc), mỗi ô được phủ đúng một lần.
In kết quả theo modulo 109+7. Sử dụng quy hoạch động theo profile gãy (broken profile DP).
Ví dụ: Lưới 2×2 có 2 cách (hai domino dọc hoặc hai domino ngang).
Một dòng chứa hai số nguyên n và m.
1≤n,m≤14.
In số cách lát modulo 109+7.
Ví dụ:
Đầu vào:
2 2
Đầu ra:
2
Giải thích:
Đang tải editor...