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):
X,Y = [int(zz) for zz in input().split()]

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

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

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

if a != int(a):
    print(0)
    exit()

a = int(a)
b = int(b)
N = a+b

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 )

ans = cmb(N,a,mod)%(10**9+7)
print(int(ans))

Solution (Python):
X,Y = [int(zz) for zz in input().split()]

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

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

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

if a != int(a):
    print(0)
    exit()

a = int(a)
b = int(b)
N = a+b

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 )

ans = cmb(N,a,mod)%(10**9+7)
print(int(ans))

Solution (Python):
def sq(a, b, mod):  
    if b == 0:
        return 1
    elif b % 2 == 0:
        return sq(a, b // 2, mod)**2 % mod
    else:
        return sq(a, b - 1, mod) * a % mod


def nCk(n, k, mod=10 ** 9 + 7):
    x = max(k, n - k)
    y = min(k, n - k)
    kkai = 1
    for i in range(2, y + 1):
        kkai = (kkai * i) % mod
    nkkai = 1
    for i in range(x + 1, n + 1):
        nkkai = (nkkai * i) % mod
    answer = sq(kkai, mod - 2, mod) * nkkai % mod
    return answer


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

Solution (Python):
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 )


x, y = map(int, input().split())
ans = 0
if ((x+y)%3 == 0):
    X = (2*x - y)//3
    Y = (2*y - x)//3
    ans = cmb(X+Y,X,mod)
print(ans)

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

if (x + y) % 3 != 0:
    print(0)
else:
    time = (x + y) // 3
    if time > x or time > y:
        print(0)
    else:
        move_time = sorted([x - time, y - time])
        
        if move_time[0] == 0:
            print(1)
        else:
            ans = 1
            for i in range(2, time+1):
                ans *= i
                ans %= mod
            
            const = 1
            for i in range(1, move_time[1]+1):
                const *= i
                const %= mod
                
                if i == move_time[0]:
                    inv0 = pow(const, mod-2, mod)
                
            inv1 = pow(const, mod-2, mod)
        
            print((ans * inv0 * inv1) % mod)

Solution (Python):
from functools import reduce

MOD = 1000000007

def comb(n, r):
    if n < 0 or r < 0 or r > n:
        return 0
    r = min(r, n - r)
    if r == 0: return 1

    numer = [n - r + i + 1 for i in range(r)]
    denom = [i + 1 for i in range(r)]

    for i in range(1, r):
        divisor = denom[i]
        if divisor > 1:
            offset = (n - r) % (i + 1)
            for j in range(i, r, i+1):
                numer[j - offset] //= divisor
                denom[j] //= divisor

    res = 1
    for i in range(r):
        if numer[i] > 1:
            res *= numer[i]
    return res

    

def main():
    x, y = map(int, input().split())
    ans = 0
    if (x+y)%3==0 and x <= 2*y <= 4*x:
        n = (x + y) // 3
        r = y - n
        ans = comb(n, r) % MOD
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from functools import reduce

MOD = 1000000007

def comb(n, r):
    if n < 0 or r < 0 or r > n:
        return 0
    r = min(r, n - r)
    if r == 0: return 1

    numer = [n - r + i + 1 for i in range(r)]
    denom = [i + 1 for i in range(r)]

    for i in range(1, r):
        divisor = denom[i]
        if divisor > 1:
            offset = (n - r) % (i + 1)
            for j in range(i, r, i+1):
                numer[j - offset] //= divisor
                denom[j] //= divisor

    res = 1
    for i in range(r):
        if numer[i] > 1:
            res *= numer[i]
    return res

    

def main():
    x, y = map(int, input().split())
    ans = 0
    if (x+y)%3==0 and x <= 2*y <= 4*x:
        n = (x + y) // 3
        r = y - n
        ans = comb(n, r) % MOD
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from functools import reduce

MOD = 1000000007

def comb(n, r):
    if n < 0 or r < 0 or r > n:
        return 0
    r = min(r, n - r)
    if r == 0: return 1

    numer = [n - r + i + 1 for i in range(r)]
    denom = [i + 1 for i in range(r)]

    for i in range(1, r):
        divisor = denom[i]
        if divisor > 1:
            offset = (n - r) % (i + 1)
            for j in range(i, r, i+1):
                numer[j - offset] //= divisor
                denom[j] //= divisor

    
    
    
    
    

    return reduce(lambda x, y: x*y if y > 1 else x, numer)
    

def main():
    x, y = map(int, input().split())
    ans = 0
    if (x+y)%3==0 and x <= 2*y <= 4*x:
        n = (x + y) // 3
        r = y - n
        ans = comb(n, r) % MOD
    print(ans)

if __name__ == "__main__":
    import sys
    if sys.platform =='ios':
        sys.stdin=open('in.txt')
    sys.setrecursionlimit(10**6)
    main()

Solution (Python):
from functools import reduce

MOD = 1000000007

def comb(n, r):
    if n < 0 or r < 0 or r > n:
        return 0
    r = min(r, n - r)
    if r == 0: return 1

    numer = [n - r + i + 1 for i in range(r)]
    denom = [i + 1 for i in range(r)]

    for i in range(1, r):
        divisor = denom[i]
        if divisor > 1:
            offset = (n - r) % (i + 1)
            for j in range(i, r, i+1):
                numer[j - offset] //= divisor
                denom[j] //= divisor

    
    
    
    
    

    return reduce(lambda x, y: x*y if y > 1 else x, numer)
    

def main():
    x, y = map(int, input().split())
    ans = 0
    if (x+y)%3==0 and x <= 2*y <= 4*x:
        n = (x + y) // 3
        r = y - n
        ans = comb(n, r) % MOD
    print(ans)

if __name__ == "__main__":
    import sys
    if sys.platform =='ios':
        sys.stdin=open('in.txt')
    sys.setrecursionlimit(10**6)
    main()

Solution (Python):
from sys import exit


def mpow(x, n):
    result = 1
    while n != 0:
        if n & 1 == 1:
            result *= x
            result %= 1000000007
        x *= x
        x %= 1000000007
        n >>= 1
    return result


def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0

    fac = [0] * (n + 1)
    fac[0] = 1
    for i in range(n):
        fac[i + 1] = fac[i] * (i + 1) % p
    return fac[n] * mpow(fac[n - k], p - 2) * mpow(fac[k], p - 2) % p


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()

print(mcomb(a + b, min(a, b)))

Solution (Python):
from sys import exit


def mpow(x, n):
    result = 1
    while n != 0:
        if n & 1 == 1:
            result *= x
            result %= 1000000007
        x *= x
        x %= 1000000007
        n >>= 1
    return result


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
k = min(a, b)

if n == 0 and k == 0:
    print(1)
    exit()

if n < k or k < 0:
    print(0)
    exit()

fac = [0] * (n + 1)
fac[0] = 1
for i in range(n):
    fac[i + 1] = fac[i] * (i + 1) % p
print(fac[n] * mpow(fac[n - k], p - 2) * mpow(fac[k], p - 2) % p)

Solution (Python):

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

mod = 10**9 + 7
f = [1]
for i in range(10**6):
    f.append(f[-1] * (i+1) % mod)
    
def nCr(n, r):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

def main():
    if (x + y) % 3 != 0 or (x + y) // 3 < abs(x - y):
        print(0)
        return
    
    n = (x + y) // 3
    r = n // 2 - abs(x-y) // 2
    print(nCr(n, r))
    return
    
main()

Solution (Python):
import math
import os
import sys

input = sys.stdin.readline

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

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


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


def main():
    X, Y = list(map(int, input().split()))
    N = (2 * Y - X) / 3
    M = (2 * X - Y) / 3

    if not (N.is_integer() and M.is_integer()):
        print(0)
        return

    N = int(N)
    M = int(M)

    for i in range(2, M + 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(N+M, M, MOD))


if __name__ == '__main__':
    main()

Solution (Python):
x,y = map(int,input().split())
n = 0
mod = 10**9+7
ans = 0
if not (x+y)%3:
  n = (x+y)//3
  x-=n
  y-=n
  if x>=0 and y>=0:
    ans = 1
    for i in range(x):
      ans = ans*(n-i)*pow(i+1,mod-2,mod)%mod
print(ans)

Solution (Python):
x,y = map(int,input().split())
n = 0
mod = 10**9+7
ans = 0
if not (x+y)%3:
  n = (x+y)//3
  x-=n
  y-=n
  if not x<0 or y<0:
    ans = 1
    for i in range(x):
      ans = ans*(n-i)*pow(i+1,mod-2,mod)%mod
print(ans)

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

def cmb(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    """
    階乗テーブル、逆元の階乗テーブルを作成する
    """
    fac = [1, 1] 
    ifac = [1, 1] 
    inverse = [0, 1] 

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac
    
x,y=map(int,input().split())

fac,ifac=make_tables(MOD,10**6)

if (2*x-y)%3==0 and (2*y-x)%3==0:
	a=(2*y-x)//3
	b=(2*x-y)//3
	if a>=0 and b>=0:
		print(cmb((x+y)//3,a,MOD,fac,ifac))
	else:
		print(0)
else:
	print(0)

Solution (Python):




x, y = map(int, input().split())
if (x + y) % 3 != 0 or (min(x, y) / max(x, y)) > 2.0:
    print(0)
    exit()












n = (x + y) // 3
p = (n - abs(x - y)) // 2







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(n, p, mod))

Solution (Python):
from operator import mul
from math import factorial
from functools import reduce

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

X, Y = map(int, input().split())
MOD = (10 ** 9) + 7
if ((2 * X) - Y) % 3 != 0:
    print(0)
    exit()
q = ((2 * X) - Y) // 3
p = X - (2 * q)
if q < 0 or p < 0:
    print(0)
    exit()
r = max(p, q)
s = min(p, q)

over = 1
for i in range(2,r+s+1):
    over = (over * i) % MOD
under = 0
e = 1
f = 1
for i in range(2,s+1):
    e = (e * i) % MOD
for i in range(2,r+1):
    f = (f * i) % MOD
under = e * f

result = (over * modpow(under, MOD-2, MOD) % MOD)
print(result)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def C(n,r):
    return fact[n]*pow(fact[n-r],mod-2,mod)*pow(fact[r],mod-2,mod) % mod

x,y = LI()

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

if (x+y) % 3 != 0:
    print(0)
else:
    if 2*y-x < 0 or (2*y-x) % 3 != 0:
        print(0)
    elif 2*x-y < 0 or (2*x-y) % 3 != 0:
        print(0)
    else:
        print(C((x+y)//3,(2*x-y)//3))

Solution (Python):
X,Y = map(int,input().split())
M = X+Y
mod = 10**9 + 7
kaijou = [1]
for i in range(1,10**6+1):
    kaijou.append((kaijou[-1]*i)%mod)


def C(n,k):
    return (kaijou[n]*pow(kaijou[k],mod-2,mod)*pow(kaijou[n-k],mod-2,mod))%mod

    

if M%3!=0:
    print(0)
elif X<M//3 or Y<M//3:
    print(0)
else:
    print(C(M//3, X-M//3))

Solution (Python):
import math
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 
k = 10 ** 6
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1]

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


a, b = map(int,input().split())
x = a + b

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

p = 0
q = 0
for i in range(x):
    if a <= 0 or b <= 0:
        if a == b == 0:
            break
        else:
            print(0)
            exit()
    else:
        if a >= b:
            a -= 2
            b -= 1
            p += 1
        else:
            a -= 1
            b -= 2
            q += 1

print(cmb(p+q, p, mod))

Solution (Python):
x, y = map(int, input().split())
mod = 1000000007
m = (x+y)//3
a = (m + x-y)//2
if (x+y)%3 != 0 or a<0 or a>m:
  print(0)
else:
  ans = 1
  for i in range(1, a+1):
    ans *= (m-a+i)*pow(i, mod-2, mod)
    ans %= mod
  print(ans)

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

def f(n):
  if n == 0: return 1
  res = 1
  for i in range(1,n+1):
    res = (res * i) % M
  return res % M

def pow(x, n):
  res = 1
  while n:
    if (n & 1) == 1:
      res = res * x % M
    x = x * x % M
    n = n >> 1
  return res

def c(n,r):
  if r == 0 or r == n:
    res = 1
  elif r == 1 :
    res = n
  else:
    res = f(n) * pow(f(r), M-2) * pow(f(n-r), M-2)
  return res % M

if (X+Y) % 3 != 0:
  ans = 0
else:
  a = 0
  b = (X+Y)//3
  if X < Y: X, Y = Y, X
  a = X - Y
  a += (2*Y-X)//3
  if 2*Y - X < 0:
    ans = 0
  else:
    ans = c(b, a) % M
print (ans)

Solution (Python):
import sys
input = sys.stdin.readline
X, Y = map(int, input().split())
mod = 10 ** 9 + 7
for t in range(X + Y + 1):
  if t == X + Y:
    print(0)
    exit(0)
  if X + Y - 2 * t == t:
    X -= t
    Y -= t
    break
if X < 0 or (Y < 0):
  print(0)
  exit(0)
class Factorial:
  def __init__(self, n, mod):
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod
f = Factorial(X + Y, mod)

print(f.combi(X + Y, X))

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

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

a3 = 2 * y - x
b3 = 2 * x - y
if not (a3 % 3 == 0 and b3 % 3 == 0):
  print(0)
  exit()

a = a3 // 3
b = b3 // 3

n = a + b




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


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))

Solution (Python):
MOD = 10**9+7
fact = [1, 1]
for i in range(2, 10**6+1):
    fact.append((fact[i-1] * i) % MOD)


def comb(n, k):
    return (fact[n] * pow(fact[k], MOD-2, MOD) * pow(fact[n-k], MOD-2, MOD)) % MOD


X, Y = [int(x) for x in input().split(" ")]

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

if n < 0 or n != int(n):
    print(0)
elif m < 0 or m != int(m):
    print(0)
else:
    n = int(n)
    m = int(m)
    ans = comb(n+m, n)
    print(ans)

Solution (Python):

import scipy.misc

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

MOD_BY = 7 + 10**9


















A = (2*X - Y) / 3
B = (2*Y - X) / 3






def prepare(n, MOD):
 
    
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f
     
    
    inv = pow(f, MOD - 2, MOD)
    
    return fn, inv


if A >= 0 and B >= 0 and A.is_integer() is True and  B.is_integer() is True: 
    A = int(A)
    B = int(B)
    
    
    
    
    
    
    
    fn_A_plus_B = prepare(A+B,MOD_BY)[0]
    inv_A = prepare(A,MOD_BY)[1]
    inv_B = prepare(B,MOD_BY)[1]
    
    print(fn_A_plus_B * inv_A * inv_B % MOD_BY)
    
else:
    print(0)

Solution (Python):
MOD = 10 ** 9 + 7
MAX = 10 ** 6 + 1
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

def CoMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

def COM(n, k):
   if n < k:
       return 0
   if n < 0 or k < 0:
       return 0

   return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

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

if (X + Y) % 3:
    print(0)
    exit()
n = (X + Y) // 3
X -= n
Y -= n
if X < 0 or Y < 0:
    print(0)
    exit()
CoMinit()
ans = COM(X + Y, X)
print(ans)

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

def pow_mod(value, exp):
    r = 1
    while exp:
        if exp % 2:
            r *= value
            r %= MOD
        value *= value
        value %= MOD
        exp //= 2
    return r
 
 
fact = [1] * 1000001
for i in range(1, 1000000 + 1):
    fact[i] = fact[i - 1] * i % MOD

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

if (x + y) % 3 or x > y * 2 or y > x * 2:
    print("0")
    exit()

a, b = map(int, numpy.linalg.solve([[2, 1], [1, 2]], [x, y]))

ans = fact[a + b] % MOD

ans *= pow_mod(fact[a], MOD - 2)
ans %= MOD

ans *= pow_mod(fact[b], MOD - 2)
ans %= MOD
print(ans)

Solution (Python):
xy=list(map(int,input().split()))
if sum(xy)%3!=0 or 2*xy[0]<xy[1] or 2*xy[1]<xy[0]:
    print(0)
else:
    n=sum(xy)//3
    r=2*n-xy[0]
    
    p=10**9+7
    g=[1,1] 
    inv=[1,1] 
    ig=[1,1] 
    for i in range(2,n+1):
        gi=g[-1]*i%p
        g.append(gi)
        invi=-inv[p%i]*(p//i)%p
        inv.append(invi)
        igi=ig[-1]*inv[-1]%p
        ig.append(igi)
    ans=g[n]*ig[r]*ig[n-r]%p
    print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv
comb = Combination(10**6)
x,y = inpl()
if (x+y)%3 or max(x,y) > min(x,y)*2:
    print(0)
    quit()
n = (x+y)//3
c = comb(n,x-n)
print(c)

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

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

x = (2*Y-X)//3
y = (2*X-Y)//3

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

def pow_mod(x,n):
    if n==0:
        return 1
    
    K = 1
    while n>1:
        if n%2 != 0:
            K *= x
            K %= mod
        x *= x
        x %= mod
        n //= 2

    return K*x

def n_C_k(n,k,mod):
    factorial_n = factorial_mod(n,mod)
    factorial_k = factorial_mod(k,mod)
    factorial_nk = factorial_mod(n-k,mod)
    conbi=factorial_n*pow_mod(factorial_nk,mod-2)*pow_mod(factorial_k,mod-2)
    return conbi%mod

print(n_C_k(x+y,x,mod))

Solution (Python):
def cmb(n, k, mod, fac, ifac):
    
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod

def make_tables(mod, n):
    
    fac = [1, 1] 
    ifac = [1, 1] 
    inverse = [0, 1] 

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac

X, Y = map(int, input().split())
if X > Y:
    X, Y = Y, X
dist = X + Y
if dist % 3 != 0:
    print(0)
    exit()

total = int((X+Y) / 3)
n = X - total
if Y > 2*X:
    print(0)
else:
    MOD = 10**9 + 7
    fac, ifac = make_tables(MOD, total)
    answer = cmb(total, n, MOD, fac, ifac)
    print(answer)

"""
p = (p/a)×a + (p %a)
この両辺の mod p をとると、
(p/a)×a + (p%a) ≡ 0
⇔(p/a) + (p%a)×a−1 ≡ 0　(両辺に a−1 をかける)

⇔(p%a) × a−1 ≡ −(p/a)
⇔a−1 ≡ −(((p%a)^−1) × (p/a))
"""

Solution (Python):
X, Y = map(int,input().split())
n = int((2*Y-X)/3)
m = int((2*X-Y)/3)
if (X+Y)%3!=0:
  print(0)
  exit()
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)
print(cmb(n+m, n, p))

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


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


X, Y = map(int, input().split())
if (X + Y) % 3 == 0 and 2 * Y - X >= 0 and 2 * X - Y >= 0:
    p = (2 * Y - X) // 3
    q = (2 * X - Y) // 3
    n = p + q
    r = min(p, q)
    modFacts, invs = prepare(n)
    ans = (modFacts[n] * invs[n - r] * invs[r]) % MOD
else:
    ans = 0

print(ans)

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


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


dest = list(map(int, input().split()))

p = (2, 1)
q = (1, 2)
num_p = 0
num_q = 0

while dest[0] and dest[1]:
    if dest[0] >= dest[1]:
        dest[0] -= p[0]
        dest[1] -= p[1]
        num_p += 1
    else:
        dest[0] -= q[0]
        dest[1] -= q[1]
        num_q += 1

modFacts, invs = prepare(num_p + num_q)

if dest == [0, 0]:
    n = num_p + num_q
    r = min(num_p, num_q)
    ans = (modFacts[n] * invs[n - r] * invs[r]) % MOD
else:
    ans = 0

print(ans)

Solution (Python):

P = 10**9 + 7
N = 700000 
inv = [0] + [1] 
finv = [1] + [1] 
fac = [1] + [1] 
for i in range(2,N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
  fac += [(fac[i-1] * i) % P]
  finv += [(finv[i-1] * inv[i]) % P]

def comb(a, b):
    if a<b:
        return -1 
    return (fac[a] * ((finv[b] * finv[a-b]) % P)) %P

x, y = map(int, input().split())
if (2*y-x)%3!=0 or (2*x - y)%3!=0:
    print(0)
    exit(0)
A = (2*y-x)//3
B = (2*x-y)//3
if A<0 or B<0:
    print(0)
    exit(0)
print(comb(A+B, A))

Solution (Python):
import sys

x,y=map(int,input().split())
T=x+y
MOD=10**9+7

def nCmMOD(A,B,Mod):
    num,den=1,1
    for i in range(B):
        num*=(A-i)
        den*=(i+1)
        num%=Mod
        den%=Mod
    return (num*pow(den,Mod-2,Mod))%Mod

if T%3!=0 or y/x<1/2 or y/x>2:
    print(0)
    sys.exit()
else:
    n=(2*y-x)//3
    m=(2*x-y)//3
    l=min(n,m)
    print(nCmMOD(n+m,l,MOD))

Solution (Python):
from math import factorial
pos = map(int, input().split())
p = 10**9 + 7
x, y = sorted(pos)

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

n = (-x + 2 * y) // 3
m = (-y + 2 * x) // 3





def ncr(n, r, p):
    
    
    num = den = 1
    for i in range(r):
        num = (num * (n - i)) % p
        den = (den * (i + 1)) % p
    return (num * pow(den,
                      p - 2, p)) % p


ans = ncr(n+m, n, p)
print(ans)

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

fac = [0]*MAX   
inv = [0]*MAX    
finv = [0]*MAX   

def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2,MAX):
        fac[i] = (fac[i-1] * i) % MOD
        inv[i] = MOD-(inv[MOD%i] * (MOD//i))%MOD
        finv[i] = (finv[i-1]*inv[i]) %MOD
        
    
def COM(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return (fac[n] * (finv[k]*finv[n-k]))%MOD



COMinit()

x,y = map(int,input().split())
ans = 0
if 2*y-x < 0 or 2*x-y < 0:
  pass
elif (2*y-x)%3 != 0 or (2*x-y)%3 != 0: 
  pass
else:
  s = (2*y-x)//3
  t = (2*x-y)//3
  ans = COM(s+t,s)
  
print(ans)

Solution (Python):
X,Y = map(int,input().split())
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a = 1
  b = 1
  c = 1
  for i in range(1,n+1):
    a = (a*i)%p
  for i in range(1,k+1):
    b = (b*i)%p
  for i in range(1,n-k+1):
    c = (c*i)%p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return (d**2) %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
if (X+Y)%3 != 0 or X > 2*Y or Y > 2*X:
    print(0)
else:
    ab = (X+Y)//3
    a = X - ab
    b = ab - a
    mod = 10**9+7
    ans = comb(ab,min(a,b),mod)
    print(ans)

Solution (Python):
X,Y = map(int,input().split())
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a = 1
  b = 1
  c = 1
  for i in range(1,n+1):
    a = (a*i)%p
  for i in range(1,k+1):
    b = (b*i)%p
  for i in range(1,n-k+1):
    c = (c*i)%p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
if (X+Y)%3 != 0 or X > 2*Y or Y > 2*X:
    print(0)
else:
    ab = (X+Y)//3
    a = X - ab
    b = ab - a
    mod = 10**9+7
    ans = comb(ab,min(a,b),mod)
    print(ans)

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

if (X+Y)%3 != 0 or X > 2*Y or Y > 2*X:
    print(0)
else:
    ab = (X+Y)//3
    a = X - ab
    b = ab - a
    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

    mod = 10**9+7 
    N = 10**6+1
    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 )

    ans = cmb(ab,b,mod)
    print(ans)

Solution (Python):

def comb(n, r, mod=10 ** 9 + 7):
    n1 = n + 1
    r = min(n, n - r)
    numer = denom = 1
    for i in range(1, r + 1):
        numer = numer * (n1 - i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod - 2, mod) % mod

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

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

n = (2*y-x) // 3
m = (2*x-y) // 3

if n*m < 0:
    print(0)
    exit()

print(comb(n+m, m))

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

def cmb(n, r):
    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])
 
    return result


if (2*Y - X) < 0:
    print(0)
elif (2*X - Y) < 0:
    print(0)
else:
    if (X - 2*Y) % 3 != 0 or (2*X - Y) % 3 != 0:
        print(0)
    else:
        a = (2 * Y - X) // 3
        b = (2 * X - Y) // 3
        ans = cmb(a+b, a)
        ans = ans % M
        print(ans)

Solution (Python):

def cmb(n, r):
    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])

    return result






def main():

    X,Y = [int(i) for i in input().split(" ")]

    
    if (2*X-Y) < 0 or (2*Y-X) < 0 or (2*X-Y)%3 > 0 or (2*Y-X)%3 > 0:
        print(0)
        return 0

    
    else:
        r = (2*X-Y)//3
        l = (2*Y-X)//3
        n = r+l
        
        a = cmb(n,r)
        print(a%(int(1e9+7)))
        return 0


main()

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

if (X+Y)%3>0:
  print(0)
  exit()
  
a=(2*X-Y)//3
b=(2*Y-X)//3

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

ab=a+b
ue=[1]*(ab+1)
for i in range(1, ab+1):
  ue[i]=ue[i-1]*i%p
  
out=ue[-1]*pow(ue[a], p-2, p)%p
out=out*pow(ue[b], p-2, p)%p

print(out)