Một sân vườn có kích thước \(m \times n\) đơn vị diện tích, được chia đều thành các ô vuông đơn vị có kích thước \(1 \times 1\). Một nhóm công nhân thi công lát gạch sân vườn bằng các viên gạch có hình tam giác vuông cân với độ dài cạnh góc vuông bằng \(1\). Công nhân có thể chọn viên gạch có màu trắng hoặc màu đen để lát vừa đủ kín toàn bộ diện tích mặt sân. Cụ thể, mỗi viên gạch được chọn khi lát có cạnh góc vuông trùng với cạnh của ô vuông đơn vị trên sân. Để sân vườn này trông đẹp mắt hơn, mọi người quyết định đưa ra cách lát gạch như sau:

• Không cắt các viên gạch.
• Không xếp các viên gạch chồng lên nhau.
• Hai viên gạch xếp chung cạnh không được cùng màu.

Minh họa:

Yêu cầu

• Với sân vườn kích thước \(m \times n\), hãy lập trình tìm số lượng cách lát gạch theo yêu cầu trên.

Dữ liệu vào:

• Một dòng duy nhất ghi hai số nguyên dương \(m, n\) \((m, n \le 10^9)\), mỗi số cách nhau một dấu cách.

Ràng buộc dữ liệu vào:

• 50% số điểm tương ứng với các test có \(m = 1\) hoặc \(n = 1\) và \(max(m, n) \le 15\).
• 50% số điểm còn lại không ràng buộc gì thêm.

Kết quả:

• Một số là phần dư của kết quả tìm được khi chia cho \(10^9 + 7\).

Input 1

1 2

Output 1

8