JOI-kun quản lý một khu cắm trại được chia thành lưới chữ nhật gồm \(H\) hàng và \(W\) cột. Các hàng chạy theo hướng đông-tây, các cột chạy theo hướng bắc-nam. Ô ở hàng thứ \(i\) tính từ phía bắc và cột thứ \(j\) tính từ phía tây được gọi là ô \((i,j)\).

JOI-kun muốn dựng một số lều. Mỗi lều chiếm đúng một ô, và không có hai lều chiếm cùng một ô. Mỗi lều có đúng một cửa ra vào, hướng về một trong bốn phía bắc, nam, đông hoặc tây. Hướng cửa phải thỏa mãn:

• Nếu cả hai ô \((i_1,j)\) và \((i_2,j)\), với \(1 \le i_1 < i_2 \le H\) và \(1 \le j \le W\), đều có lều, thì cửa lều ở \((i_1,j)\) phải hướng nam, còn cửa lều ở \((i_2,j)\) phải hướng bắc.
• Nếu cả hai ô \((i,j_1)\) và \((i,j_2)\), với \(1 \le i \le H\) và \(1 \le j_1 < j_2 \le W\), đều có lều, thì cửa lều ở \((i,j_1)\) phải hướng đông, còn cửa lều ở \((i,j_2)\) phải hướng tây.

Hãy đếm số cách dựng ít nhất một lều thỏa mãn các điều kiện trên, lấy dư cho \(1\,000\,000\,007\). Hai cách khác nhau nếu có một ô mà trạng thái khác nhau: có hay không có lều, hoặc hướng cửa lều khác nhau.

Dữ liệu vào

Một dòng chứa hai số nguyên \(H,W\).

Dữ liệu ra

In số cách dựng ít nhất một lều thỏa mãn điều kiện, lấy dư cho \(1\,000\,000\,007\).

Ràng buộc

• \(1 \le H \le 3\,000\).
• \(1 \le W \le 3\,000\).

Phân nhóm

1. \(48\) điểm: \(1 \le H \le 300\) và \(1 \le W \le 300\)
2. \(52\) điểm: Không có ràng buộc bổ sung.

Ví dụ

1 2

9

4 3

3252

100 100

561068619

Nguồn

JOI 2018 Spring Training Camp, ngày 1 - Tents (tiếng Anh). Bản tiếng Nhật.