Một bảng chữ nhật có n hàng và m cột. Bạn có vô hạn quân domino, mỗi quân phủ đúng hai ô chung cạnh. Một quân có thể đặt theo chiều dọc hoặc chiều ngang.
Hãy đếm số cách phủ kín mọi ô của bảng sao cho các quân không chồng lên nhau và không vượt ra ngoài bảng. Hai cách được xem là khác nhau khi có ít nhất một ô được ghép với ô khác nhau.
Input
Một dòng chứa hai số nguyên n và m.
Output
In số cách phủ kín bảng, lấy phần dư theo 1000000007.
Constraints
1≤n≤10.
1≤m≤1000.
Scoring
Subtask 1 (50% số điểm): n≤5 và m≤8.
Subtask 2 (50% số điểm): Không có giới hạn bổ sung.
Example
Test 1
Input
2 3
Output
3
Giải thích: Có một cách dùng ba domino dọc. Hai cách còn lại dùng hai domino ngang phủ hai cột liên tiếp và một domino dọc ở cột còn lại.
Lời giải tóm tắt
Ý tưởng: Quét bảng theo cột. Một domino ngang có thể bắt đầu ở cột hiện tại và chiếm thêm một ô cùng hàng ở cột kế tiếp. Vì vậy, sau khi xử lý một tiền tố cột, chỉ cần nhớ mask các ô ở cột mới đã bị domino từ bên trái chiếm.
Ý tưởng: Với mỗi mask, dùng DFS lấp ô chưa xử lý đầu tiên trong cột: đặt domino ngang để bật bit ở nextMask, hoặc đặt domino dọc nếu ô ngay dưới còn trống. Danh sách chuyển của mọi mask được tiền xử lý một lần.
Đúng đắn: Ở ô trống đầu tiên của cột, domino phủ ô đó chỉ có thể nằm ngang hoặc dọc. Hai lựa chọn loại trừ nhau và bao phủ mọi khả năng, nên DFS sinh mỗi cách lấp cột đúng một lần. nextMask ghi chính xác phần duy nhất vượt qua biên cột. Quy nạp theo số cột cho thấy DP đếm đúng mọi cách lát tiền tố; sau cột cuối chỉ mask 0 hợp lệ.
Độ phức tạp: Có 2^h mask với h=min(n,m)≤10. Độ phức tạp là O(w·2^h·F_h) với w=max(n,m) và F_h là số chuyển của một mask; bộ nhớ O(2^h) ngoài bảng chuyển.