実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
二次元グリッドの原点 (0,0) にチェスのナイトの駒があります。
ナイトの駒はマス (i,j) にあるとき (i+1,j+2) か (i+2, j+1) のどちらかのマスにのみ動かすことができます。
ナイトの駒をマス (X,Y) まで移動させる方法は何通りありますか?
10^9+7 で割った余りを求めてください。
制約
- 1 \leq X \leq 10^6
- 1 \leq Y \leq 10^6
- 入力中のすべての値は整数である。
入力
入力は以下の形式で標準入力から与えられる。
X Y
出力
ナイトの駒を (0,0) から (X,Y) まで移動させる方法の数を、10^9+7 で割った余りを出力せよ。
入力例 1
3 3
出力例 1
2
(0,0) \to (1,2) \to (3,3) と (0,0) \to (2,1) \to (3,3) の 2 通りが考えられます。
入力例 2
2 2
出力例 2
0
(2,2) にナイトの駒を移動させることはできません。
入力例 3
999999 999999
出力例 3
151840682
方法の数を 10^9+7 で割った余りを出力してください。
Score : 400 points
Problem Statement
There is a knight - the chess piece - at the origin (0, 0) of a two-dimensional grid.
When the knight is at the square (i, j), it can be moved to either (i+1,j+2) or (i+2, j+1).
In how many ways can the knight reach the square (X, Y)?
Find the number of ways modulo 10^9 + 7.
Constraints
- 1 \leq X \leq 10^6
- 1 \leq Y \leq 10^6
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
X Y
Output
Print the number of ways for the knight to reach (X, Y) from (0, 0), modulo 10^9 + 7.
Sample Input 1
3 3
Sample Output 1
2
There are two ways: (0,0) \to (1,2) \to (3,3) and (0,0) \to (2,1) \to (3,3).
Sample Input 2
2 2
Sample Output 2
0
The knight cannot reach (2,2).
Sample Input 3
999999 999999
Sample Output 3
151840682
Print the number of ways modulo 10^9 + 7.