Mã đi một chiều

Xem PDF

Nộp bài


Điểm: 20 (thành phần)
Thời gian: 1.0s
Bộ nhớ: 512M

Tác giả:
Dạng bài

Cho một lưới ô vuông hai chiều cùng một quân mã ở ô có tọa độ \((0, 0)\). Tại mỗi nước, quân mã có thể di chuyển từ ô \((i, j)\) đến ô \((i+1,j+2)\) hoặc \((i+2,j+1)\).

Yêu cầu: Cho hai số nguyên dương \(m\) và \(n\), hãy tính số cách đi khác nhau để quân mã có thể di chuyển đến ô \((m, n)\). Vì kết quả có thể rất lớn nên bạn chỉ cần in ra số dư của nó khi chia cho \(10^9+7\).

Input:

  • Gồm một dòng duy nhất chứa hai số nguyên dương \(m\) và \(n\). Các số có giá trị không vượt quá \(10^6\).

Output:

  • In ra số lượng cách đi \(\text{mod}\) \((10^9+7)\).

Ví dụ

Sample input 01
3 3
Sample output 01
2
Giải thích

Hai cách đi khả thi là \((0,0)\rightarrow (1,2)\rightarrow (3,3)\) và \((0,0)\rightarrow (2,1)\rightarrow (3,3)\).

Sample input 02
4 4
Sample output 02
0
Sample input 03
99 81
Sample output 03
669452545