Problem link : Moscow, 1968
Difficulty : Medium
Setter : Harshit Garg
Explanation :
In one move the value of x coordinate + y coordinate increases by 3. So if X+Y is not a multiple of 3, the answer is 0. If it’s a multiple of three, let n be the number of move (+1,+2), and m be the number of move (+2,+1), then by considering each coordinate we obtain simultaneous equations n + 2m = X, 2n + m = Y , so we can find n, m. If n < 0 or m < 0, the answer is 0. Otherwise, you have to chose m moves, in which the knight will move (+1, +2), from a total of n + m moves, so the answer will be n+mCn.
Code :
X, Y = list(map(int, input().split()))
mod = 10 ** 9 + 7
if((2 * Y - X) % 3 == 0 and (2 * X - Y) % 3 == 0 and (2 * Y - X) >= 0 and (2 * X - Y) >= 0):
x = (2 * Y - X) // 3
y = (2 * X - Y) // 3
if(x == 0 or y == 0):
print(1)
else:
fac = 1
for i in range(1, x + y + 1):
fac = (fac * i) % mod
if(i == x):
mod_x = fac
if(i == y):
mod_y = fac
mod_xy = fac
def mod_n(a, n):
if(n == 1):
return a % mod
elif(n % 2 == 0):
return (mod_n(a, n // 2) ** 2) % mod
else:
return (a * mod_n(a, n // 2) ** 2) % mod
mod_x = mod_n(mod_x, mod - 2)
mod_y = mod_n(mod_y, mod - 2)
print((mod_xy * mod_x * mod_y) % mod)
else:
print(0)