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 = map(int, input().split())


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



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

mod = 10**9+7 
N = int(a+b)
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

if a%1 != 0 or b%1 != 0:
    print(0)
else:
    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(int(a+b), int(min(a,b)), mod)
    print(ans)

Solution (Python):


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


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


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

if a%1 != 0 or b%1 != 0:
    print(0)
else:
    ans = cmb(int(a+b), int(min(a,b)), mod)
    print(ans)

Solution (Python):
import itertools
X, Y=map(int, input().split())  
MOD = 10**9 + 7
if (X+Y)%3 != 0:
    print(0)
else:

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

    

    if n<0 or m<0:
        print(0)
    else:
        ret = 1
        for i in range(m):
            ret = ret * ((X+Y)//3 - i) % MOD * pow(i + 1, MOD-2, MOD) % MOD
        print(ret)

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

def main():
    x,y = map(int,input().split())
    comb = Combination(10**6)

    if (x+y)%3==0:
        n_max = x//2
        ans = 0
        for i in range(n_max+1):
            if y == 2*x-3*i:
                ans = (ans+comb(x-i,i))%(10**9+7)
        print(ans)
    else:
        print(int(0))
if __name__=='__main__':
    main()

Solution (Python):
import sys
import numpy as np
input = sys.stdin.readline



class Solver(object):
    def __init__(self):
        pass

    def solve(self, x: int, y: int):
        if (x + y) % 3 != 0:
            return 0
        A = np.matrix([[1, 2],
                       [2, 1]])
        Y = np.matrix([[x],
                       [y]])
        m, n = np.linalg.solve(A, Y)
        if m < 0:
            return 0
        if n < 0:
            return 0
        return self.cmb(int(m)+int(n), int(n)) % (10**9 + 7)

    def cmb(self, 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()]

    solver = Solver()
    print(solver.solve(X, Y))


if __name__ == "__main__":
    main()

Solution (Python):
def f(x, y):
    if (x + y) % 3 != 0: return 0
    n = (x + y) // 3
    k = (2 * x - y) // 3
    if k < 0 or k > n: return 0
    ret = 1
    for i in range(k):
        ret = ret * (n - i) % MOD * pow(i + 1, MOD-2, MOD) % MOD
    return ret

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

Solution (Python):

def modinv(a, m):
    b = m; x0 = 1; x1 = 0
    while b:
        q = a//b
        a, b = b, a%b
        x0, x1 = x1, x0 - q*x1
    return x0%m 


x, y = map(int, input().split())
if (x + y)%3 != 0:
    print(0)
else:
    k = (x + y)//3
    if k <= x <= 2*k:
        i = min(x - k, 2*k - x)
        
        MOD = 10**9 + 7
        
        fac = [1]*(k + 1)
        for j in range(2, k + 1):
            fac[j] = fac[j - 1]*j%MOD
        
        finv = [0]*(k + 1)
        
        finv[k] = modinv(fac[k], MOD)
        for j in range(k, i, - 1):
            finv[j - 1] = finv[j]*j%MOD

        print(fac[k] * (finv[i] * finv[k - i] % MOD) % MOD)
    else:
        print(0)

Solution (Python):
x, y = map(int, input().split())
if (x + y)%3 != 0:
    print(0)
else:
    k = (x + y)//3
    if k <= x <= 2*k:
        MOD = 10**9 + 7
        fac = [0]*(k + 1)
        finv = [0]*(k + 1)
        inv = [0]*(k + 1)
        fac[0] = 1; fac[1] = 1; finv[0] =1; finv[1] = 1; inv[1] = 1
        for i in range(2, k + 1):
            fac[i] = fac[i - 1] * i % MOD
            inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
            finv[i] = finv[i - 1] * inv[i] % MOD
        
        i = x - k
        print(fac[k] * (finv[i] * finv[k - i] % MOD) % MOD)
    else:
        print(0)

Solution (Python):








import sys

def power_l(x,power): 
    if power==0:
        return 1
    elif power<0:
        print('error')
        sys.exit(1)
    res = 1
    sq = x%mod
    while(power>0):
        if power&1 > 0:
            res*=sq
            res=res%mod
        sq = sq**2 %mod
        power = power >> 1
    return res%mod

def inv(x): 
    ans = power_l(x,mod-2)
    return ans

mod = 10**9+7

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

if (X+Y)%3 !=0:
    print(0)
    sys.exit()
m = int((2*X-Y)//3)
n = int(X-2*m)

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



f=[1,1]
for i in range(m+n-1):
    f.append((f[i+1]*(i+2))%mod)

denom = (f[m]*f[n])%mod

ans=(f[m+n] * inv(denom)) %mod
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

class modfact(object):
    def __init__(self,n):
        fact=[1]*(n+1)
        invfact=[1]*(n+1)
        for i in range(1,n+1):
            fact[i]=i*fact[i-1]%MOD
        invfact[n]=pow(fact[n],MOD-2,MOD)
        for i in range(n-1,-1,-1):
            invfact[i]=invfact[i+1]*(i+1)%MOD
        self.__fact=fact
        self.__invfact=invfact

    def fact(self,n):
        return self.__fact[n]

    def invfact(self,n):
        return self.__invfact[n]

    def comb(self,n,k):
        if(k<0 or n-k<0): return 0
        return (self.fact(n)*self.invfact(k)*self.invfact(n-k))%MOD

def resolve():
    x,y=map(int,input().split())
    if((x+y)%3):
        print(0)
        return
    z=(x+y)//3
    mf=modfact(z)
    print(mf.comb(z,x-z))
resolve()

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())
MOD = 1000000007
if (X+Y) % 3 != 0:
    print(0)
else:
    m = (2*X-Y)//3
    n = X - 2*m
    if n < 0 or m < 0:
        print(0)
        exit()
    fac, ifac = make_tables(MOD, (X+Y)//3)
    ans = cmb(n+m, n, MOD, fac, ifac)
    print(ans)

Solution (Python):




def exEuclid(a, b):
    if (b==0):
        return (a, 1, 0)
    else:
        (dd, xx, yy) = exEuclid(b, a % b)
        return (dd, yy, xx - (a//b)*yy)

def mycomb(n, k, p):
    k = min(n-k,k)
    fact=1
    finv=1
    for i in range(k):
        fact=fact*(n-i) % p
        finv=finv*(i+1) % p
    (d, x, y) = exEuclid(finv, p)
    return fact*x % p

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

if ((x+y)%3 != 0):
    print(0)
    exit()
else:
    n1 = (-x+2*y)//3
    n2 = (2*x -y)//3
    if( (n1<0) or (n2<0) ):
        print(0)
        exit()
    npath = mycomb(n1+n2, n2, 10**9+7)
    print(npath)

Solution (Python):



P = (10**9)+7

fac=[]
inv=[]
finv=[]





def exEuclid(a, b):
    if (b==0):
        return (a, 1, 0)
    else:
        (dd, xx, yy) = exEuclid(b, a % b)
        return (dd, yy, xx - (a//b)*yy)

def COMinit(MAX):
    global fac, inv, finv
    fac=[1 for _ in range(MAX)]
    inv=[1 for _ in range(MAX)]
    finv=[1 for _ in range(MAX)]
    
    
    for i in range(2,MAX):
        
        fac[i] = fac[i-1]*i % P
        (d, x, y) = exEuclid(i, P)
        inv[i] = x
        finv[i] = finv[i-1]*inv[i] % P

def COM(n, k):
    if(n<k):
        return 0
    elif ( (n<0)or(k<0)):
        return 0
    else:
        return fac[n]*(finv[n-k]*finv[k] % P) % P




x, y = list(map(int,input().split()))
MAX = (x+y)//3 +1  
COMinit(MAX)

if ((x+y)%3 != 0):
    print(0)
    exit()
else:
    n1 = (-x+2*y)//3
    n2 = (2*x -y)//3
    if (n1<0):
        print(0)
        exit()
    elif(n2<0):
        print(0)
        exit()
    else:
        npath = COM(n1+n2, n1)
        print(npath)

Solution (Python):

from math import factorial as f
from sys import exit

X, Y=map(int, raw_input().split())
j = (X+Y)/3

if (X+Y)%3 != 0 or X-j < 0 or Y-j <0:
    print str(0)
    exit(0)


mod = pow(10,9)+7


nu = reduce(lambda x,y: (x*y)%mod, xrange(max(X-j, Y-j)+1, j+1), 1)
denu = reduce(lambda x,y: (x*y)%mod, xrange(1, min(X-j, Y-j)+1), 1)


ans = (nu * pow(denu, mod-2, mod)) % mod

print str(ans)

Solution (Python):

import math
import heapq

MOD = 10**9+7

def combination(n, r):
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n+1-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)
else:
    a = (2*X-Y)//3
    b = (2*Y-X)//3
    if a<0 or b<0:
        print(0)
    else:
        print(combination(a+b, a))

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

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

lxy = [x,y]
lxy.sort()
lxy.reverse()
x,y = lxy
delta = abs(x - y)
asum = x + y
anum = asum // 3
delta2 = (delta + anum) // 2
if asum%3 != 0 or anum < delta2:
    print(0)
else:
    X,Y = [abs(delta2), abs(anum-delta2) ]
    ans = cmb(X+Y, Y)%(10**9+7)
    print(ans)

Solution (Python):
def kaijou(n, r, mo):
    c = 1
    for i in range(r+1, n+1):
        c *= i
        c %= mo
    return c

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def invmod(a, m):
    g, x, y = xgcd(a, m)
    return x % m

def kaijou_inv(ans, n, mo):
    for i in range(1,n+1):
        ans *= invmod(i, mo)
        ans %= mo
    return ans


x, y = map(int, input().split())
mo = 10**9 + 7
if (x+y) % 3 != 0:
    print(0)
else:
    a = (2*x-y) // 3
    b = (2*y-x) // 3
    if a<0 or b<0:
        print(0)
    else:
        te = kaijou(a+b, max(a, b), mo)
        tem = kaijou_inv(te, min(a,b), mo)
        print(tem)

Solution (Python):
import sys
import numpy as np
import math


class remainder():
    def __init__(self, mod=(10**9 + 7)):
        self.mod = mod
    
    def add(self, a, b):
        
        return (a + b) % self.mod
    
    def sub(self, a, b):

        return (a + self.mod - b) % self.mod
    
    def mul(self, a, b):

        return ((a % self.mod) * (b % self.mod)) % self.mod

    def pow(self, a, b):
        bp = []
        
        bp.append(a)

        n = len(bin(b)) - 2
        for x in range(n):
            bp.append(bp[x]**2 % self.mod)

        res = 1
        for x in range(n):
            if b >> x & 1:
                res = (res * bp[x]) % self.mod
        
        return res

    def div(self, a, b):
        
        return self.mul(a, self.pow(b, self.mod - 2))

    def power(self, a, b):

        return self.pow(a % self.mod, b % (self.mod - 1)) % self.mod

    
    
    def comInit(self, MAX=1000000):
        self.fac = [0] * MAX
        self.invFac = [0] * MAX
        self.inv = [0] * MAX
        
        self.fac[0] = self.fac[1] = 1
        self.invFac[0] = self.invFac[1] = 1
        self.inv[1] = 1

        for x in range(2, MAX):
            self.fac[x] = self.fac[x - 1] * x % self.mod
            self.inv[x] = self.mod - self.inv[self.mod % x] * (self.mod // x) % self.mod
            self.invFac[x] = self.invFac[x - 1] * self.inv[x] % self.mod
    
    def com(self, n, k):
        if (n < k):
            return 0

        if  (n < 0 or k < 0):
            return 0

        return self.fac[n] * (self.invFac[k] * self.invFac[n - k] % self.mod) % self.mod
    
    
    
    

    def dpComInit(self, MAX=2000):
        dpCom = [[0] * (MAX + 1) for _ in range(MAX + 1)]
        dpCom[0][0] = 1

        for i in range(1, MAX + 1):
            dpCom[i][0] = 1
            for j in range(1, MAX + 1):
                dpCom[i][j] = (dpCom[i - 1][j - 1] + dpCom[i - 1][j]) % self.mod

        return dpCom

re = remainder()
re.comInit()

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

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




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

x = np.linalg.solve(A, B)

if np.where(x>=0, True, False).all():
    ans = re.com(int(x[0] + x[1]), int(x[0]))
    print(ans)

else:
    print(0)

Solution (Python):
def extgcd(a,b):
    a0,b0=a,b
    x0,y0=1,0
    x1,y1=0,1

    while b0!=0:
        q = a0 // b0
        r = a0 % b0

        a0,b0=b0,r
        x0,x1=x1,x0-q*x1
        y0,y1=y1,y0-q*y1

    return a0,x0,y0

def mo(x,m):
    return (m+x%m)%m

def inv(a,m):
    g,x,y=extgcd(a,m)
    ans=mo(x,m)
    return ans

def combi_mod(n,k,m):
    mi=min(k,n-k)
    invlist = [1]
    for i in range(1, mi + 1):
        temp = inv(i, m)
        invlist.append(temp)
    ans=1

    for i in range(1,mi+1):
        ans=(ans*(n+1-i)*invlist[i])%m
    ans = ans % m
    return ans

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

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

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

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

ans=combi_mod(a+b,a,mod)
print(ans)

Solution (Python):
import math

def comb(n, k, m):
  f = [1] * (n+1)
  for i in range(1, n+1):
    f[i] = f[i-1] * i % m
  return f[n] * pow_mod(f[k]*f[n-k]%m, m-2, m) % m

def pow_mod(a, b, m):
  if b == 0:
    return 1
  elif b%2 == 0:
    d = pow_mod(a, b//2, m) % m
    return d * d % m 
  else:
    d = pow_mod(a, (b-1)//2, m)
    return  d * d * a % m

tmp = list(map(int, input().split()))
x = tmp[0]
y = tmp[1]

ans = 0
mod = 10**9 + 7

if (x + y) % 3 != 0:
  ans = 0
else:
  n = (x + y) // 3
  if min(x, y) < n:
    ans = 0
  elif min(x,y) == n:
    ans = 1
  else:
    r = min(x, y) - n
    ans = comb(n, r, mod)

print(ans)

Solution (Python):
def factorials(n,m):
    
    f = [1,1]
    for i in range(2,n+1):
        f.append(f[-1]*i%m)

    
    g = [1]
    for i in range(n):
        g.append(pow(f[i+1],m-2,m))

    return f,g

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

m = 10**9+7

if (2*y-x)%3!=0:
    print(0)
    exit()

b = (2*y-x)//3
a = y-2*b

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

f,g = factorials(a+b,m)

nCr = f[a+b]*g[b]*g[a]

print(nCr%m)

Solution (Python):
def binomial_p(n, k, p):
    '''
    Input: integers n, k such that n >= k >= 0, prime number p
    Output: n choose k mod p
    '''

    k = min(k, n-k)
    fct_n = 1  
    inv = [0, 1] 
    invfct_k = 1 
    invfct_n_k = 1  

    
    
    for i in range(2, n - k + 1):
        fct_n = (fct_n * i) % p
        inv.append(( inv[p % i] * (p - p//i) ) % p )
        invfct_n_k = invfct_n_k * inv[-1] % p
        if i == k:
            invfct_k = invfct_n_k

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

    return ((fct_n * invfct_k % p) * invfct_n_k) % p



x, y = [int(a) for a in input().split()]

n, rn = divmod(2 * x - y, 3)
m, rm = divmod(2 * y - x, 3)
p = 10**9 + 7

if rn != 0 or rm != 0 or n < 0 or m < 0:
    ans = 0
else:
    a = (2 * x - y) // 3
    b = (2 * y - x) // 3
    ans = binomial_p(a + b, b, p)

print(ans)

Solution (Python):
X,Y =[int(i) for i in input().split()]
mod = 10**9+7
if (X+Y)%3!=0:
    print("0")
    exit()
newX = X-(X+Y)//3
newY = Y-(X+Y)//3
X=newX
Y=newY
if X<0 or Y<0:
    print("0")
    exit()

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

Solution (Python):
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 cmb(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
def main():
    x,y=sorted(map(int,input().split()))
    if (x+y)%3!=0:
        print(0)
        return
    if y>2*x:
        print(0)
        return
    m=(x+y)//3
    a,b=x-m,y-m
    print(cmb(a+b, a,10**9+7))
    
main()

Solution (Python):
X,Y=map(int,input().split())
mod=10**9+7
def nCr(n,r,mod):
    r=min(r,n-r)
    number=denom=1
    for i in range(1,r+1):
        number=number*(n+1-i)%mod
        denom=denom*i%mod
    return number*pow(denom,mod-2,mod)%mod

if (X+Y)%3 !=0:
    print(0)
    exit()
n=((2*X)-Y)//3
m=((X+Y)//3)-n

if n<0 or m<0:
    print(0)
    exit()
print(nCr(n+m,min(n,m),mod))

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

if not(-(-x//2) <= y and y <= x*2):
    print(0)
    exit()

flag = True

count = 0
while flag:
    if y*2 == x: 
        print(comb(y, count, 10**9+7))
        exit()
    if y*2 < x: 
        print(0)
        exit()
    
    count += 1
    x += 1
    y -= 1

Solution (Python):
from sys import stdin
import math
import bisect
import heapq
import numpy as np
from math import factorial
mod = 1000000007
x,y = [int(x) for x in stdin.readline().rstrip().split()]

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

a = (2*x-y)//3
b = (2*y-x)//3

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

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

print(combination(a+b,a))

Solution (Python):

import sys
INF = float("inf")

MOD = 1000000007  


class Combination(object):
    """
    組み合わせを求める。
    cmbで使いうる最大のNまでを前処理で準備。
    """

    def __init__(self, N, mod=10**9+7):
        fac, finv, inv = [0]*(N+1), [0]*(N+1), [0]*(N+1)
        fac[:2] = 1, 1
        finv[:2] = 1, 1
        inv[1] = 1
        for i in range(2, N+1):
            fac[i] = fac[i-1]*i % mod
            inv[i] = -inv[mod % i]*(mod//i) % mod
            finv[i] = finv[i-1]*inv[i] % mod
        self.N = N
        self.MOD = mod
        self.fac = fac
        self.finv = finv
        self.inv = inv

    def __call__(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return self.fac[n] * (self.finv[k]*self.finv[n-k] % self.MOD) % self.MOD


def solve(X: int, Y: int):

    if X > Y:
        X, Y = Y, X
    sub = Y-X

    if (X - (Y-X)) % 3 != 0:
        print(0)
        return

    A = (X - (Y-X))//3 + sub
    B = (X - (Y-X))//3

    cmb = Combination(A+B)
    print(cmb(A+B, A))

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  
    Y = int(next(tokens))  
    solve(X, Y)


if __name__ == '__main__':
    main()

Solution (Python):
inpl = lambda: list(map(int,input().split()))
def inv_mod(a, p):
    return pow(a, p-2, p)

def comb_mod(n,k,p):
    ans = 1
    k = min(k,n-k)
    if k < 0:
        return 0
    for i in range(k):
        ans = ans * (n-i) * inv_mod(k-i,p) % p
    return ans

MOD = 10**9+7
X, Y = inpl()
if (X+Y) % 3:
    print(0)
    exit()
N = (X+Y)//3
X -= N
Y -= N
Z = X + Y
print(comb_mod(Z,X,MOD))

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






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

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

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

MAX = 10**6
MOD = 10**9 + 7
 
fac = [0] * (MAX + 1)
faci = [0] * (MAX + 1)
inv = [0] * (MAX + 1)
 
fac[0] = fac[1] = 1
faci[0] = faci[1] = 1
inv[1] = 1
 
for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
    faci[i] = faci[i - 1] * inv[i] % MOD
 
def comb(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0 
    return fac[n] * (faci[k] * faci[n - k] % MOD) % MOD
   
print(comb(n + m, n))

Solution (Python):
def combination(n,r,mod=10**9+7):
    r=min(r,n-r)
    up,down=1,1
    for i in range(r):
        up=up*(n-i)%mod
        down=down*(i+1)%mod
    return up*pow(down,mod-2,mod)%mod


x,y=map(int,input().split())
n,m=(2*y-x)//3,(2*x-y)//3
if (x+y)%3!=0 or n<0 or m<0:print(0);exit()
print(combination(n+m,m))

Solution (Python):
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

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

MOD = 10**9+7
x, y = map(int, input().split())
if (x+y)%3 != 0 or 3*x < x+y or 3*y < x+y:
    print(0)
    exit()
n = (x+y)//3
x -= n
y -= n
fact = [1, 1]
for i in range(2,n+1):
    fact.append(fact[i-1] * i % MOD)
factX = fact[x]
factY = fact[y]
factN = fact[n]



c = factN * modinv(factX, MOD) * modinv(factY, MOD)
c %= MOD
print(c)

Solution (Python):

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

mod = 10 **9 + 7

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

from operator import mul
from functools import reduce

def combination(n, r, mod=10**9+7):
    n1, r = n+1, min(r, 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

if (x + y) %3 != 0:
    print(0)
elif n < 0 or m < 0:
    print(0)
else:
    print(combination(n+m,n,mod))

Solution (Python):


X,Y = map(int, input().split())
p=int(1e9+7)
if (X+Y)%3 or X>Y*2 or Y>X*2:
    print(0)
else:
    N=int((X+Y)/3)
    k=X-N
    if k==0 or k==N:
        print(1)
    else:
        fac=[1]*(N+1)
        inv=[1]*(N+1)
        finv=[1]*(N+1)
            
        num=max(k,N-k)
        for j in range(num-1):
            i=j+2
            fac[i]=fac[i-1]*i % p
            r=int(p%i)
            q=p//i
            inv[i]=p- inv[r]*q %p
            finv[i]=finv[i-1]*inv[i] % p
        for j in range(N-num):
            i=num+1+j
            fac[i]=fac[i-1]*i % p
        print(int(fac[N]*(finv[k]*finv[N-k] % p) % p))

Solution (Python):
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
def cinit(N):
    for i in range( 2, N + 1 ):
        g1[i] = ( ( g1[i-1] * i ) % mod )
        inverse[i] = ( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2[i] = ( (g2[i-1] * inverse[i]) % mod )
X,Y = map(int, input().split())
if (X+Y)%3==0and(X<Y*2 or Y<X*2):
    N = (X+Y)//3
    g1,g2,inverse = [0]*(N+1),[0]*(N+1),[0]*(N+1)
    g1[0],g1[1],g2[0],g2[1],inverse[0],inverse[1] = 1,1,1,1,0,1
    cinit(N)
    p = (min(X,Y)*2 - max(X,Y))//3
    print(cmb((X+Y)//3,p,mod))
else:
    print(0)

Solution (Python):


mod = int(1e9+7)

def comb_mod(n, r, mod):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    else:
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, n + 1):
            fac.append(fac[-1] * i % mod)
            inv.append(-inv[mod % i] * (mod // i) % mod)
            finv.append((finv[-1] * inv[-1]) % mod)
        return int(fac[n] * finv[r] * finv[n - r] % mod)

X,Y = (int(x) for x in input().split())
count = 0
if (X+Y)%3!=0 or 2*X<Y or 2*Y<X:
    print("0")
    exit()
else:
    N=(X+Y)/3 
    mov_x=(2*X-Y)/3 
    print(comb_mod(int(N), int(mov_x), mod))

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 
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

def cinit(N):
    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==0and(X<Y*2 or Y<X*2):
    cinit((X+Y)//3)
    p = (min(X,Y)*2 - max(X,Y))//3
    print(cmb((X+Y)//3,p,mod))
else:
    print(0)

Solution (Python):
import sys


def alg_combination_mod(n, r, mod):
    r = min(n - r, r)
    if r == 0:
        return 1
    else:
        denominator = 1
        for i in range(n, n - r, -1):
            denominator = (denominator * i) % mod
        molecule = 1
        for i in range(1, r + 1):
            molecule = (molecule * i) % mod
        return denominator * pow(molecule, mod - 2, mod) % mod


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    x, y = list(map(int, input().rstrip('\n').split()))
    if (x + y) % 3 != 0 or x <= 0 or y <= 0:
        print(0)
    else:
        t = (x + y) // 3
        for i in range(t + 1):
            xn = i * 2 + (t - i)
            yn = i + (t - i) * 2
            if xn == x and yn == y:
                print(alg_combination_mod(i + t - i, i, mod))
                exit()
        print(0)


if __name__ == '__main__':
    solve()

Solution (Python):
x,y=map(int,input().split())
MOD=10**9+7
def comb(n, k):
    ret = 1
    for i in range(1, k + 1):
        ret = ret * (n - i + 1) % MOD        
        ret = ret * pow(i, MOD - 2, MOD) % MOD
        
    return ret
a=(2*y-x)/3
b=(2*x-y)/3
c=(x+y)/3
if (x+y)%3!=0 :
    print(0)
elif a<0 or b<0:
    print(0)
else:
    print(int(comb(int(c),int(a))))

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

def combinations_count(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 A(i, j):
    if 0.5*i <= j and j <= 2*i and (i+j)%3==0:
        n, m = (2*j-i)//3, (2*i-j)//3
        return combinations_count(n+m,m)%((10**9)+7)
    else:
        return 0

print(A(x, y))

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

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

n=((x+y)//3) + 1
k=y-(n-2)

fac=[0 for _ in range(n)]   
finv=[0 for _ in range(n)]  
inv=[0 for _ in range(n)]   

fac[0]=1
fac[1]=1
finv[0]=1
finv[1]=1
inv[1]=1

for i in range(2,n):
    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 ncr(n,k):
    if(n < k):
        return 0
    elif(n < 0 or k < 0):
        return 0
    else:
        return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


print(ncr(n-1,k-1))

Solution (Python):
import numpy as np


MOD = 10**9 + 7

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

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

else:
    if (Y < X/2) or (Y > 2*X):
        print(0)
    
    else:
      
        h = (2 * X - Y) // 3
        v = (2 * Y - X) // 3

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

        def low_inverse(a):
            ret, _ = extgcd(a, MOD)
            return ret

        def low_combination(m, n):
            
            ret = 1
            numerator = m + n
            for i in range(min(m, n)):
                inv_i = low_inverse(i + 1)
                ret = ret * (numerator - i) * inv_i % MOD
            return ret

        print(low_combination(h, v))

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

def comb(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:
    n = - (X - 2 * Y) / 3
    m = (2 * X - Y) / 3
    if not (n % 1 == 0 and m % 1 == 0):
        print(0)
    else:
        if n < 0 or m < 0:
            print(0)
        else:
            print(comb(int(n+m), int(n), mod))

Solution (Python):

def combi(n, r, mod):
    r = min(r, n-r)
    numer = denom = 1

    for i in range(r):
        numer = numer * (n-i) % mod
        denom = denom * (i+1) % mod
    return numer * pow(denom, mod-2, mod) % mod 

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

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

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

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

ans = combi(int(n+m), int(n), mod)
print(ans)