You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Sân nhà Tâm được lát bằng $m\times n$ viên gạch hình vuông ($m,n>1$), thành dạng lưới ô vuông $m$ dòng, $n$ cột như Hình 1. Tọa độ của viên gạch ở dòng $i$, cột $j$ là $(i,j)$.

Tâm kêu chú chó nhà mình đi từ $(1,1)$ tới $(m,n)$ với yêu cầu:

• Từ một viên gạch, chú chó chỉ có thể bước đi sang viên gạch có cùng cạnh (Hình 2 biểu diễn ví dụ về bước đi hợp lệ).
• Đường đi phải là ngắn nhất (trên ít viên gạch nhất) có thể.

Tâm đã từng huấn luyện chú chó phản ứng theo một cách cụ thể với ánh sáng; vì vậy, Tâm đã dễ dàng điều khiển chú chó đi theo đúng yêu cầu của mình.

Yêu cầu

Hãy cho biết có bao nhiêu đường đi khác nhau của chú chó theo đúng yêu cầu của Tâm. Hai đường đi được coi là khác nhau nếu có ít nhất một viên gạch nằm trên đường đi này nhưng không nằm trên đường đi kia.

Dữ liệu

Vào từ đầu vào chuẩn 2 số nguyên $m$ và $n$.

Kết quả

Ghi ra đầu ra chuẩn 1 số nguyên là số dư trong phép chia số nguyên có số bị chia là số đường đi khác nhau của chú chó theo đúng yêu cầu của Tâm và số chia là ${10}^9+7$.

Ví dụ

7 5

210

2 3

3

Giới hạn

Subtask 1 (50% số điểm): $m,n\le 10$.

Subtask 2 (50% số điểm): $m,n\le 2 \times {10}^3$.