Problem:
 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 .

Solution (Python):





def combination(n,r):
	"""
    高速な組み合わせの計算．
	nCrは必ず整数になるため分母を全部約分で1にしてから残った分子の積を求める．
	[参考]https://kadzus.hatenadiary.org/entry/20081211/1229023326
    """

	if n-r < r: r = n-r
	if r == 0: return 1
	if r == 1: return int(n)

	numerator = [i+1 for i in range(n-r, n)]
	denominator = [i+1 for i in range(r)]

	for p in range(2,r+1):
		pivot = denominator[p-1]
		if pivot > 1:
			offset = (n-r)%p
			for k in range(p-1, r, p):
				numerator[k-offset] /= pivot
				denominator[k] /= pivot
	
	ans = 1
	for i in range(r):
		if numerator[i] > 1:
			ans *= numerator[i]
			if ans >= 1e9+7: ans %= 1e9+7
	
	return int(ans)

X,Y = map(int, input().split())

if (X+Y)%3 != 0:
	ans = 0
else:
	n = int((2*Y-X)/3)
	m = int(Y-2*n)
	if n<0 or m<0:
		ans = 0
	else:
		ans = combination(n+m, n)

print(ans)

Solution (Python):





def combination(n,r):
	"""
    高速な組み合わせの計算．
	nCrは必ず整数になるため分母を全部約分で1にしてから残った分子の積を求める．
	[参考]https://kadzus.hatenadiary.org/entry/20081211/1229023326
    """

	if n-r < r: r = n-r
	if r == 0: return 1
	if r == 1: return int(n)

	numerator = [i+1 for i in range(n-r, n)]
	denominator = [i+1 for i in range(r)]

	for p in range(2,r+1):
		pivot = denominator[p-1]
		if pivot > 1:
			offset = (n-r)%p
			for k in range(p-1, r, p):
				numerator[k-offset] /= pivot
				denominator[k] /= pivot
	
	ans = 1
	for i in range(r):
		if numerator[i] > 1:
			ans *= numerator[i]
			ans %= 1e9+7
	
	return int(ans)

X,Y = map(int, input().split())

if (X+Y)%3 != 0:
	ans = 0
else:
	n = int((2*Y-X)/3)
	m = int(Y-2*n)
	if n<0 or m<0:
		ans = 0
	else:
		ans = combination(n+m, n)

print(ans)

Solution (Python):
X,Y = map(int,input().split())
M = max(X,Y)
m = min(X,Y)
mod = 10 ** 9 + 7

con = (X + Y) // 3
dif = M - m
n = (con - dif) // 2

if (X + Y) % 3 != 0 or n < 0:
  print(0)
  
else:
  def comb(n, r):
    n += 1
    over = 1
    under = 1
    for i in range(1,r + 1):
      over = over * (n - i) % mod
      under = under * i % mod
    
    return over * pow(under,mod - 2,mod) % mod
  
  ans = comb(con,n)
  
  print(ans)

Solution (Python):
import sys

X, Y = [int(i) for i in input().split()]
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 
N = 10**6
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

a_3 = 2 * Y - X
b_3 = 2 * X - Y
if a_3 % 3 != 0 or b_3 % 3 != 0 or a_3 < 0 or b_3 < 0:
    print(0)
    sys.exit(0)
a = a_3//3
b = b_3//3
print(cmb(a+b,a,mod))

Solution (Python):
X, Y = map(int, input().split())

if (2*X-Y)%3==0 and (2*Y-X)%3==0:
    a = (2*X-Y)//3
    b = (2*Y-X)//3
    if a>=0 and b>=0:
        MOD = 10**9+7
        n = a+b+1
        fac = [1]*(n+1)
        rev = [1]*(n+1)
        
        for i in range(1,n+1):
            fac[i] = i*fac[i-1]%MOD
            rev[i] = pow(fac[i], MOD-2, MOD)
        comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD
        print(comb(a+b, a))
    else:
        print(0)
else:
    print(0)

Solution (Python):
x, y = map(int, input().split())
mod = 10 ** 9 + 7

cnt1 = cnt2 = 0
for i in range(x + 1):
    x_left = x - i
    y_left = y - 2 * i
    if x_left == y_left * 2:
        cnt1 = i
        cnt2 = y_left

if cnt1 == cnt2 == 0:
    ans = 0
else:
    ans = 1
    for i in range(1, cnt1 + 1):
        ans *= (cnt1 + cnt2 - i + 1)
        ans %= mod
        ans *= pow(i, mod - 2, mod)
        ans %= mod

print(ans)

Solution (Python):
x, y = map(int, input().split())
mod = 10 ** 9 + 7

cnt1 = cnt2 = 0
for i in range(x + 1):
    x_left = x - i
    y_left = y - 2 * i
    if x_left == y_left * 2:
        cnt1 = i
        cnt2 = y_left

if cnt1 == cnt2 == 0:
    ans = 0
else:
    ans = 1
    for i in range(1, cnt1 + 1):
        ans *= (cnt1 + cnt2 - i + 1)
        ans %= mod
        ans *= pow(i, mod - 2, mod)
        ans %= mod

print(ans)

Solution (Python):
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 2 * 10 ** 6  
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

X, Y = map(int, input().split())

n = (-X + 2 * Y) / 3
m = (-Y + 2 * X) / 3

if n % 1 != 0:
  print(0)
  quit()
elif m % 1 != 0:
  print(0)
  quit()

ans = cmb(int(n + m), int(n), p)
print(ans)

Solution (Python):

X, Y = map(int, input().split())
if (X + Y) % 3:
    exit(print(0))
m = (2*X - Y) // 3
n = X - 2*m
if n < 0 or m < 0:
    exit(print(0))


def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def power(a, b, c):
    try:
        return pow(a, b, c)
    except (ValueError, TypeError) as e:
        if b < 0:
            return pow(modinv(a, c), -b, c)
        else:
            print(e)

class Factorial:
    def __init__(self, n, mod):
        self.f = f =[0] * (n + 1)
        f[0] = b = 1
        for i in range(1, n + 1):f[i] = b = b * i % mod
        self.inv = inv = [0] * (n + 1)
        inv[n] = b = power(self.f[n], -1, mod)
        for i in range(n,0,-1):inv[i-1] = b = b * i % mod
        self.mod = mod
    def factorial(self, i):
        return self.f[i]
    def ifactorial(self, i):
        return self.inv[i]
    def comb(self, n, k):
        if n >= k:return self.f[n] * self.inv[n - k] * self.inv[k] % self.mod
        else:return 0

def nCr(n, r, mod = None, limit = None):
    if mod and limit:
        return Factorial(limit, mod).comb(n, r)
    elif mod:
        r = min(r, n - r)
        a = 1
        for i in range(r):
            a = a * (n - i) * power(i + 1, mod - 2, mod) % mod
        return a
    else:
        from math import factorial as f
        return f(n) // (f(n - r) * f(r))

MOD = 10**9+7
print(nCr(m + n, n, MOD, 2*10**6))

Solution (Python):
import math

def modpow(a,b,mod=10**9+7):
    res=1
    a%=mod
    leng=int(math.log2(b))
    for i in range(leng,-1,-1):
        res=(res*res)%mod
        if (b>>i)&1:
            res=(res*a)%mod
    return res

def fact(x):
    ans=1
    for i in range(2,x+1):
        ans = (ans*i)%(10**9+7)
    return ans

def comb(n,r):
    return fact(n)*modpow(fact(r),10**9+5)*modpow(fact(n-r),10**9+5)%(10**9+7)

x,y=map(int,input().split(' '))
if (x+y)%3!=0 or 2*x-y<0 or 2*y-x<0:
    print(0)
else:
    x,y=max(x,y),min(x,y)
    d=x-y
    n=((x-2*d)//3)
    m=n+d
    print(comb(n+m,n))

Solution (Python):
x,y=map(int,input().split())
mod=10**9+7

def comb(n,k):
    if n<k:
        return 0
    if n-k<k:
        k=n-k
    comb=1
    for x in range(n-k+1,n+1):
        comb=(comb*x)%mod
    d=1
    for x in range(1,k+1):
        d =(d*x)%mod
    comb*=pow(d,mod-2,mod)
    return comb%mod

ans=0
if (x+y)%3==0:
    n=int((x+y)/3)
    r=int((2*x-y)/3)
    if n-r>=0 and r>=0:
        ans=comb(n,r)%mod
print(ans)

Solution (Python):
x,y = map(int,input().split())
mod = 10**9 + 7

move = x+y
if move %3 !=0:
  print(0)
  exit()
move //= 3
  
x,y = x-move, y-move

if x < 0 or y < 0:
  print(0)
  exit()
  
ans = 1
for i in range(min(x,y)):
  ans *= (x+y-i)
  ans *= pow(i+1,mod-2,mod)
  ans %= mod
print(ans)

Solution (Python):
import math
import numpy as np

def cmb(n, r, mod):
  r = min(r, n-r)
  return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 
N = 10**6
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
  g1.append( ( g1[-1] * i ) % mod )
  inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
  g2.append( (g2[-1] * inverse[-1]) % mod )

x,y = map(int,input().split()) 

if (x+y) % 3 == 0:

  A = np.array([[1, 2],
                [2, 1]])

  b = np.array([x, y])

  N = np.linalg.solve(A, b)


  if N[0].is_integer() == True and N[1].is_integer() == True and N[0] >=0 and N[1] >=0:
        
      print(cmb(int(N[0]+N[1]),int(N[0]),mod))

  else:
      print(0)

else:
  print(0)

Solution (Python):
x,y=map(int,input().split())
mod=10**9+7

def comb(n,k):
    if n<k:
        return 0
    if n-k<k:
        k=n-k
    comb=1
    for x in range(n-k+1,n+1):
        comb=(comb*x)%mod
    d=1
    for x in range(1,k+1):
        d =(d*x)%mod
    comb*=pow(d,mod-2,mod)
    return comb%mod

ans=0
if (x+y)%3==0:
    n=int((x+y)/3)
    r=int((2*x-y)/3)
    if n-r>=0 and r>=0:
        ans=comb(n,r)%mod
print(ans)

Solution (Python):
MOD = 10**9 + 7

X, Y = map(int, input().split())

def getComb(n, k, MOD):
    if n < k:
        return 0
    if n-k < k:
        k = n-k
    comb = 1
    for x in range(n-k+1, n+1):
        comb = (comb * x) % MOD
    d = 1
    for x in range(1, k+1):
        d = (d * x) % MOD
    comb *= pow(d, MOD-2, MOD)
    return comb % MOD

ans = 0
if (X+Y)%3 == 0:
    N = (X+Y)//3
    k = (2*Y-X)//3
    if k >= 0:
        ans = getComb(N, k, MOD)

print(ans)

Solution (Python):
mod = 10**9 + 7
fact = []
ifact = []
def setFact(n, mod):
    global fact
    global ifact
    fact.append(1)
    for i in range(1, n+1):
        fact.append((fact[-1] * i) % mod)
    ifact = [0] * (n+1)
    ifact[-1] = pow(fact[-1] , mod-2, mod)
    for i in range(n, 0, -1):
        ifact[i-1] = ifact[i] * i % mod
def combination(n, k, mod):
    if k <0 or k>n:
        return 0
    return (fact[n]* ifact[k]* ifact[n-k]) %mod
X, Y = map(int, input().split())
if (X+Y)%3 != 0:
    print(0)
    exit()
N = int((X+Y)/3)
Nx = int((N + X - Y) /2)
Ny = int((N - X + Y) /2)
if Nx < 0 or Ny < 0:
    print(0)
    exit()
setFact(N, mod)
print(combination(N, Nx, mod))

Solution (Python):
MOD = 10 ** 9 + 7
def choose(n,r):
  num = 1
  den = 1
  for i in range(r):
    num *= n-i
    num %= MOD
  for i in range(r):
    den *= i+1
    den %= MOD
  return num * pow(den, MOD-2, MOD) % MOD
def solve(x,y):
  if (x+y)%3!=0:
    return 0
  k = (x+y)//3
  if x<k or y<k:
    return 0
  return choose(k, min(y-k, x-k))
print(solve(*map(int, input().split())))

Solution (Python):
x,y=map(int,input().split())
mod=pow(10,9)+7
if (2*x-y)%3!=0 or (2*y-x)%3!=0:
  print(0)
  exit(0)
a=(2*x-y)//3
b=(2*y-x)//3

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 
N = 10**6
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

print(cmb(a+b,a,mod))

Solution (Python):
x ,y = map(int, input().split())

if x >= y:
    if not (2 * y - x) % 3:  
        ch2 = int((2 * y - x) / 3)
        if ch2 < 0:
            print(0)
            exit()
        ch1 = ch2 + x - y
    else:
        print(0)
        exit()

elif x < y:
    if not (2 * x - y) % 3:  
        ch1 = int((2 * x - y) / 3)
        if ch1 < 0:
            print(0)
            exit()
        ch2 = ch1 + y - x 
    else:
        print(0)
        exit()

def cmb(s, t, r):
    x = 1
    y = 1
    for i in range(t):
        x = (x*(s-i))%r
        y = (y*(i+1))%r
 
    y_inverse = pow(y, r-2, r)
    return (x*y_inverse)%r

mod = 10 ** 9 + 7

print(cmb(ch1+ch2,ch1,mod))

Solution (Python):
mod = 10 ** 9 + 7

x, y = map(int, input().split())

if (x + y) % 3 != 0:
    print(0)
    exit()

if x > 2 * y or y > 2 * x:
    print(0)
    exit()

cnt = (x + y) // 3
x_cnt = x - cnt
y_cnt = y - cnt
min_cnt = min(x_cnt, y_cnt)

def nCr(n, r, mod):
    return g1[n] * g2[r] * g2[n - r] % mod

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range(2, cnt + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

print(nCr(cnt, min_cnt, mod))

Solution (Python):
x, y = map(int, input().split())
mod = 10 ** 9 + 7


def cmb(n, r, mod):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % mod


N = 10 ** 6
g1 = [1, 1]  
g2 = [1, 1]  
inverse = [0, 1]  

for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

if (x + y) % 3 != 0:
    print(0)
else:
    res = 0
    m, n = 0, 0
    while m * 2 <= x:
        n = x - m * 2
        if 2 * n + m == y:
            res += cmb(m + n, m, mod)
        m += 1
    print(res)

Solution (Python):

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)


from collections import Counter,deque,defaultdict





x,y=n1()

def comb(n,k):
    nCk = 1
    MOD = 10**9+7

    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= MOD

    for i in range(1,k+1):
        nCk *= pow(i,MOD-2,MOD)
        nCk %= MOD
    return nCk

if (x+y)%3!=0:
    print(0)
else:
    n=(x+y)//3
    if x-n>=0 and y-n>=0:
        ans=comb(n,x-n)
        print(ans)
    else:
        print(0)

Solution (Python):

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)


from collections import Counter,deque,defaultdict





x,y=n1()

def comb(n,k):
    nCk = 1
    MOD = 10**9+7

    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= MOD

    for i in range(1,k+1):
        nCk *= pow(i,MOD-2,MOD)
        nCk %= MOD
    return nCk

if (x+y)%3!=0:
    print(0)
else:
    n=(x+y)//3
    if x-n>=0 and y-n>=0:
        ans=comb(n,x-n)
        print(ans)
    else:
        print(0)

Solution (Python):
import sys

input = lambda: sys.stdin.readline().rstrip()


def solve():
    X, Y = map(int, input().split())
    sm = min(X, Y)
    lg = max(X, Y)
    mod = 10**9 + 7
    m = [0] * (sm + 1)
    n = [-1] * (sm + 1)
    m[0] = 1
    n[0] = pow(m[0], mod - 2, mod)

    for i in range(1, sm + 1):
        m[i] = m[i - 1] * i % mod

    ans = 0
    for i in range(sm + 1):
        if (sm - i) % 2 == 0:
            b = (sm - i) // 2
            if b + i * 2 == lg:
                if n[i] == -1:
                    n[i] = pow(m[i], mod - 2, mod)
                if n[b] == -1:
                    n[b] = pow(m[b], mod - 2, mod)
                ans = (ans + m[i + b] * n[i] * n[b]) % mod

    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
x,y=map(int,input().split())
n=x+y
if x/y>2 or y/x>2 or n%3!=0:
    print(0)
    exit()
n//=3
r=min(x-n,y-n)
m=10**9+7
a=b=1
for i in range(r):
    a=a*(n-i)%m
    b=b*(i+1)%m
print(a*pow(b,m-2,m)%m)

Solution (Python):
def fer(n, r, p):
    
    
    x, y = 1, 1
    for i in range(r):
        x *= (n - i)
        x %= p
        y *= (i + 1)
        y %= p
    
    
    return x * pow(y, p - 2, p) % p


def main():
    x, y = map(int, input().split())

    if x/y < 1/2 or x/y > 2 or (x + y) % 3 != 0:
        print(0)
        exit()

    n, m = (2*y-x)//3, (2*x-y)//3
    ans = fer(n+m, n, 10 ** 9 + 7)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
X,Y=map(int,input().split())
mod=10**9+7
MAX=X+Y+1

fac=[1,1]
inv_t=[0,1]
finv=[1,1]
for i in range(2,MAX):
    fac.append(fac[-1]*i%mod)
    inv_t += [inv_t[mod % i] * (mod - mod // i) % mod]
    finv.append(finv[i-1]*inv_t[i]%mod)

x=2*X-Y
y=2*Y-X

if x%3!=0 or y%3!=0 or x*y<0:
    print(0)
else:
    x=x//3
    y=y//3
    n=x+y
    r=min(x,y)
    print((fac[n]*finv[r]*finv[n-r])%mod)

Solution (Python):
def nCr(n_, r_, m_):
  c = min(r_ , n_ - r_)
  bunshi = 1
  bunbo = 1
  for i in range(1,c+1):
    bunshi = bunshi * (n_+1-i) % m_
    bunbo = bunbo * i % m_
  return bunshi * pow(bunbo, m_-2, m_) % m_


x,y = map(int,input().split())
s = max(x,y)
t = min(x,y)
u = 2*t-s
if u%3 != 0 or u < 0:
  print(0)
else:
  a = u//3
  b = a + s - t
  ans = nCr(a+b,b,10**9+7)
  print(ans)

Solution (Python):
import sys
x,y=map(int,input().split())

if (x+y)%3 != 0:
    print(0)
    sys.exit()

tmp=(x+y)//3
x=x-tmp
y=y-tmp
sosu=10**9+7
if x<0 or y<0:
    print(0)
    sys.exit()

def combination(x,y):
    n=x+y
    r=min(x,y)
    upper=1
    lower=1
    for i in range(r):
        upper=(upper*(n-i))%sosu
        lower=(lower*(i+1))%sosu
    return (upper * pow(lower,sosu-2,sosu))%sosu
print(combination(x,y))

Solution (Python):
import sys

X, Y = map(int, input().split())
mod = 10 ** 9 + 7

if (2 * X - Y) % 3 != 0 or (2 * Y - X) % 3 != 0:
    
    print(0)
    sys.exit()


m = (2 * X - Y) // 3
n = (2 * Y - X) // 3


if m < 0 or n < 0:
    print(0)
    sys.exit()

u = m + n
fact = [1] * (u+1)

for i in range(1, u+1):
    fact[i] = (fact[i-1] * i) % mod

fact_inv1 = pow(fact[n], mod-2, mod)
fact_inv2 = pow(fact[m], mod-2, mod)

res = (((fact[u] * fact_inv1) % mod) * fact_inv2) % mod

print(res)

Solution (Python):
import sys

X, Y = map(int, input().split())
mod = 10 ** 9 + 7


if (X + Y) % 3 != 0:
    
    print(0)
    sys.exit()


m = (2 * X - Y) // 3
n = (2 * Y - X) // 3

if m < 0 or n < 0:
    print(0)
    sys.exit()

u = m + n
fact = [1] * (u+1)

for i in range(1, u+1):
    fact[i] = (fact[i-1] * i) % mod

fact_inv1 = pow(fact[n], mod-2, mod)
fact_inv2 = pow(fact[m], mod-2, mod)

res = (((fact[u] * fact_inv1) % mod) * fact_inv2) % mod

print(res)

Solution (Python):
MOD = 10 ** 9 + 7

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    X, Y = ZZ()
    if (X + Y)%3 != 0:
        print(0)
        return

    N = (X + Y)//3
    if abs(X - Y) > N:
        print(0)
        return
        
    fact = [0] * (N + 1) 
    ifact = [0] * (N + 1)

    for i in range(N+1):
        if i == 0:
            fact[i] = 1
            continue
        fact[i] = i * fact[i-1]
        fact[i] %= MOD
    ifact[N] = pow(fact[N], MOD-2, MOD)
    for i in range(N)[::-1]:
        ifact[i] = ((i+1) * ifact[i+1])%MOD

    m = (2*X - Y)//3
    n = (-X + 2*Y)//3

    output = fact[m+n] * ifact[m] * ifact[n] % MOD
    print(output)

    return

if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9+7

def modcmb(n, r, mod):
    r = min(r, n-r)
    x = 1
    y = 1
    for i in range(1,r+1):
        x *= i
        x %= MOD
        y *= n-i+1
        y %= MOD
    
    return y * pow(x, mod-2, mod) % mod


def main():
    X,Y = map(int, readline().split())

    x, y = 2 * X - Y, -X + 2 * Y
    if x < 0 or y < 0:
        print(0)
        exit()
    
    if x % 3 != 0 or y % 3 != 0:
        print(0)
        exit()
    
    x, y = x // 3, y // 3
    

    ans = modcmb(x + y, x, MOD)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from functools import reduce

m, n = map(int, input().split())
mod = 10 ** 9 + 7


def ncr(p, k):
    if k == 0:
        return 1
    elif k < 0:
        return 0
    else:
        num = reduce(lambda x, y: x * y % mod, range(p, p - k, -1))
        den = reduce(lambda x, y: x * y % mod, range(1, k + 1))
        return num * pow(den, mod - 2, mod) % mod


if (m + n) % 3 != 0:
    print(0)
else:
    p = (m + n) // 3
    k = m - p
    print(ncr(p, k))

Solution (Python):
from sys import stdin, setrecursionlimit


def cmb(n, r, mod=10 ** 9 + 7):
    r = min(r, n - r)
    x = y = 1
    for i in range(r):
        x *= n - i
        x %= mod
        y *= i + 1
        y %= mod
    return x * pow(y, mod - 2, mod) % mod


def main():
    mod = 10 ** 9 + 7
    input = stdin.buffer.readline
    x, y = map(int, input().split())

    if (x + y) % 3 != 0 or 2 * x < y or 2 * y < x:
        print(0)
    else:

        x_min = (x + y) // 3

        print(cmb((x + y) // 3, x - x_min, mod))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Solution (Python):
from sys import stdin, setrecursionlimit


def initialize_cmb(m, mod=10 ** 9 + 7):
    fac = [1]
    finv = [1]
    inv = [0] * (m + 1)
    if m >= 1:
        fac.append(1)
        finv.append(1)
        inv[1] = 1
        pre_fac = 1
        pre_finv = 1
        for i in range(2, m + 1):
            pre_fac = pre_fac * i % mod
            fac.append(pre_fac)
            inv[i] = mod - inv[mod % i] * (mod // i) % mod
            pre_finv = pre_finv * inv[i] % mod
            finv.append(pre_finv)
    return fac, finv


def cmb(n, k, fac, finv, mod=10 ** 9 + 7):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


def main():
    mod = 10 ** 9 + 7
    input = stdin.buffer.readline
    x, y = map(int, input().split())

    if (x + y) % 3 != 0 or 2 * x < y or 2 * y < x:
        print(0)
    else:
        fac, finv = initialize_cmb((x + y) // 3, mod)

        x_min = (x + y) // 3

        print(cmb((x + y) // 3, x - x_min, fac, finv, mod))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Solution (Python):
import math


def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: 
        return 1
    if r%2 == 0:
        return power(n*n%mod,r//2,mod)%mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

x,y = map(int,input().split())


ans = 0
md = 10**9+7
if((x+y)%3 != 0 or (2*y-x)%3 != 0 or (2*x-y)%3 != 0 or 2*y-x < 0 or 2*x-y < 0):
    print(0)
else:
    a = (2*x - y)//3
    n = (x+y)//3
    ans = comb(n,a,md)
    print(ans)

Solution (Python):
MOD=10**9+7

def cmb(n, r):
    if n < r: return 0 
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
            result = result%MOD

    return result

x, y = map(int, input().split())
a = (2*y - x)/3
b = (2*x - y)/3



if a.is_integer() and b.is_integer() and a>=0 and b>=0:
    print(cmb(int(a+b), int(a)))
else:
    print(0)

Solution (Python):
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m




def combination(n, r, mod=10 ** 9 + 7):
    r = min(r, n - r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i + 1, mod) % mod
    return res

x,y = map(int, input().split())
b = (2*y - x) / 3
a = (2*x - y) / 3
if not b.is_integer() or not a.is_integer() or a < 0 or b < 0:
    print(0)
else:
    print(combination(int(a+b), int(a)))

Solution (Python):
import math
def inv(a,mod=10**9+7):
    return(pow(a,mod-2,mod))

x,y = map(int,input().split())
mod = 10**9+7
reuslt = 0
if (x+y) %3 == 0:

    n = (2*x-y)//3
    m = (2*y-x)//3
    r = min(n,m)
    result = 1
    if n < 0 or m < 0:
        print(0)
        exit()
    for i in range(r):
        result = result*(n+m-i)*inv(i+1,mod)%mod
    
else :
    result = 0

print(result)

Solution (Python):
x,y=map(int,input().split())
mod=10**9+7

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def mod_combinations_count(n, r, mod):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

if (x+y)%3!=0:
    print(0)
else:
    n=(x+y)//3
    m=(-x+2*y)//3
    if n<0 or m<0 or n<m:
        print(0)
        exit()
    else:
        print(mod_combinations_count(n,m,mod)%mod)

Solution (Python):
x,y=map(int,input().split())
mod=10**9+7

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def mod_combinations_count(n, r, mod):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

if (x+y)%3!=0:
    print(0)
else:
    n=(x+y)//3
    m=(-x+2*y)//3
    if n<0 or m<0 or n<m:
        print(0)
        exit()
    else:
        print(mod_combinations_count(n,m,mod)%mod)

Solution (Python):
X,Y = map(int, input().split())

if (X+Y)%3!=0:
    print(0)
    exit()

def mcomb(n, k):
    fac = [0] * (n + 1)
    fac[0] = 1
    for i in range(1, n + 1):
        fac[i] = fac[i - 1] * i % 1000000007


    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], 1000000005, 1000000007) * pow(fac[k], 1000000005, 1000000007) % 1000000007

N = (-1*X+2*Y)//3
M = (2*X-Y)//3
print(mcomb(N+M, N)%(10**9+7))

Solution (Python):

def modpow(a, n, mod):
    res = 1
    
    
    
    
    
    
    while (n > 0):
        
        
        if n & 1:
            res = res * a % mod
        
        
        a = a * a % mod
        
        
        
        
        
        
        n = n >> 1
    return res


def modcomb(n, r, mod):
    if r > n - r:
        r = n - r
    nPr, rPr = 1, 1
    for i in range(r):
        nPr = nPr * (n - i) % mod
        rPr = rPr * (i + 1) % mod
    
    
    
    
    
    
    
    
    return nPr * modpow(rPr, mod - 2, mod) % mod


def main():
    X, Y = map(int, input().split())
    n = (-X + 2 * Y) / 3
    m = (2 * X - Y) / 3
    
    
    if not(n.is_integer() and m.is_integer()):
        return 0
    if n >= 0 and m >= 0:
        
        return modcomb(int(n + m), int(n), mod=10 ** 9 + 7)
    else:
        return 0


print(main())

Solution (Python):
p = 1000000007

X, Y = map(int, input().split())

if (X + Y) % 3 != 0:
    print(0)
    exit()

a = (2 * Y - X) // 3
b = (2 * X - Y) // 3

if a < 0 or b < 0:
    print(0)
    exit()

n = a + b
fac = [0] * (n + 1)
fac[0] = 1
for i in range(n):
    fac[i + 1] = fac[i] * (i + 1) % p


def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], p - 2, p) * pow(fac[k], p - 2, p) % p


print(mcomb(n, a))

Solution (Python):
import math
import time

def rpt_fact(a,b):
    mod = 10 ** 9 + 7
    txt = bin(b)[2:]
    ls = [a]
    res = []
    for i in range(len(txt)):
        ls.append(ls[-1]**2 % mod)
    for i in range(1,len(txt)+1):
        if txt[-i] == "1":
            res.append(ls[i-1])
    ans = 1
    for i in res:
        ans *= i
        ans % mod
    return ans


[x,y] = [int(i) for i in input().split()]
st = time.time()
mod = 10 ** 9 + 7


if (x + y) % 3 != 0:
    print(0)
else:
    
    
    _atb = x - y
    atb = (x + y)//3
    a = (atb - _atb)//2
    b = (atb + _atb)//2
    
    if a < 0 or b < 0:
        print(0)
    elif a == 0 or b == 0:
        print(1)
    else:
        n = a + b
        r = min(a,b)
        son = n
        mom = r

        for i in range(1,r):
            son *= (n - i)
            mom *= i
            son %= mod
            mom %= mod
        mom = rpt_fact(mom,mod-2) % mod
        
        print(son*mom % mod)

Solution (Python):
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6  
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


X,Y = map(int,input().split())

x = X % 3
y = Y % 3

sa = X - Y
to = ( X + Y ) // 3
aa = ( sa + ( X + Y ) // 3 ) // 2

ans = 1

if x == 0 and y == 0:
  print(cmb(to, aa, p))

elif x == 1 and y == 2:
  print(cmb(to, aa, p))
        
elif x == 2 and y == 1:
  print(cmb(to, aa, p))
  
else:
  print(0)

Solution (Python):
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p


X, Y = map(int, input().split())
p = 10 ** 9 + 7
turn = (X + Y)//3
N = turn + 10  
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

if (X + Y) % 3 != 0:
    print(0)
    exit()
turn = (X + Y)//3
move1 = (Y - X + turn) //2
move2 = (X - Y + turn) //2

print(cmb(turn, move1, p))

Solution (Python):

def main():
    import sys, math
    X, Y = map(int, sys.stdin.readline().split())
    '''
    i +2*j ==X
    2*i +j ==Y
    '''
    if (2*Y-X)%3==0:
        i = (2*Y-X)//3
        j = Y-2*i
    else:
        i,j=0,0
    
    mod = 10**9+7
    def calc(n):
        ans = 1
        for i in range(n, 1, -1):
            ans *= i
            ans %= mod
        return ans
    
    ans = calc(i+j)
    
    
    
    
    gg1 = pow(calc(i), mod-2, mod)
    gg2 = pow(calc(j), mod-2, mod)
    
    if i<0 or j<0:
        print(0)
    elif i==0 and j==0:
        print(0)
    else:
        print(ans*gg1*gg2%mod)

if __name__=='__main__':
    main()