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):
import sys
input = sys.stdin.readline

def modPow(a, x, p):
    res = 1
    while x > 0:
        if x % 2 != 0:
            res = res * a % p
        a = a * a % p
        x = x // 2
    return res

def modInverse(a, p):
    return modPow(a, p - 2, p)

def modBinomial(n, k, p):
    numerator = 1
    for i in range(k):
        numerator = (numerator * (n - i)) % p

    denominator = 1
    for i in range(1, k + 1):
        denominator = (denominator * i) % p

    return (numerator * modInverse(denominator, p)) % p


def main():
    X, Y = [int(x) for x in input().split()]

    MOD = 10 ** 9 + 7
    y = (X - 2 * Y) // (-3)
    x = (X - y) // 2

    if y < 0 or x < 0:
        print(0)
        exit()
    if X == x * 2 + y and Y == x + 2 * y:
        print(modBinomial(x + y, x, MOD))
    else:
        print(0)









if __name__ == '__main__':
    main()

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

mm = (2*Y - X) / 3
nn = (2*X - Y) / 3

ans = 0

if mm.is_integer() and nn.is_integer():
    mm = int(mm)
    nn = int(nn)
    if mm >=0 and nn>=0:
        ans =comb(mm+nn, nn, 10**9+7)
      
print(ans)

Solution (Python):
from sys import exit
import math
x,y = map(int, input().split())
seppen = x + y

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


if seppen%3 != 0:
    print(0)
    exit()
else:
    dan = int(seppen/3)
    kyori = y - dan

    mod = 10**9+7 
    N = dan
    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 kyori < 0 or kyori > dan:
        print(0)
    else:
        a = cmb(dan,kyori,mod)
        print(a)

Solution (Python):
x, y = map(int, input().split())
mod = 10 ** 9 + 7
h = (2 * x - y) / 3
v = x - 2 * h

if not v.is_integer() or v * h < 0:
    print(0)
    exit()


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


ans = comb(int(v + h), int(min(v, h)), mod)
print(ans % mod)

Solution (Python):
import sys
import math
input = sys.stdin.readline

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

mod = 10**9 + 7

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

x_ = max(x, y)
y = min(x, y)
x = x_

cnt_x = 0
while 2*x > y and x > 0 and y>0:
    x -= 2
    y -= 1
    cnt_x += 1

if x==-1:
    x += 2
    y += 1

if 2*x == y:
    cnt_y = x

    n = cnt_x + cnt_y 
    k = cnt_y
    print(comb(n, k, mod))

else:
    print(0)

Solution (Python):

x,y=map(int,input().split())
MOD=10**9+7
ans=0
if y>x:
    x,y=y,x

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

for a in range(1,x//2+1):
    b=x-2*a
    if 2*b+a==y:
        tmp=cmb(b+a,a,mod)%MOD
        ans+=tmp
        ans%=MOD

print(ans)

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())
if (x + y) % 3 != 0:
    print(0)
else:
    n = (x + y) // 3
    print(cmb(n, x - n, mod))

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 = map(int, input().split())
N = X + Y
C21 = 0
C12 = 0

if N % 3 != 0 or X > 2*Y or Y > 2*X:
  print(0)
else:
  while N != 0:
    if X >= Y:
      C21 += 1
      X -= 2
      Y -= 1
      N -= 3
    else:
      C12 += 1
      X -= 1
      Y -= 2
      N -= 3
  a = cmb(C21 + C12, C21)
  print(a % (10**9 + 7))

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())
if (x + y) % 3 == 0:
    n = (x + y) // 3
    k = x - n
    print(cmb(n, k, mod) % (10**9 + 7))
else:
    print(0)

Solution (Python):
import operator as op
from functools import reduce



def fact(n):
    x = n
    t = 1
    while(x>0):
        t *= x
        t %= (10**9+7)
        x -= 1
    return t



valid = True
n = sorted([int(i) for i in input().split()])
a = n[0]
b = n[1]
x = 0
y = 0

x += b-a
t = a
a -= b-a
b -= 2*(b-t)

if(a>=0 and b>=0 and a%3==0):
    x += a//3
    y += a//3
else:
    valid = False

if(valid):
    print ((fact(x+y)*pow(fact(x)*fact(y), 10**9+5, 10**9+7)) % (10**9+7))
else:
    print(0)

Solution (Python):







MOD = 10**9+7
MAX = (10**6)*2+5
fac = [0]*MAX
inv = [0]*MAX
finv = [0]*MAX
def COMinit():
    fac[0]=1
    fac[1]=1
    finv[0]=1
    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):
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD

x,y=list(map(int,input().split()))
if (2*y-x)%3!=0 or (2*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:
        COMinit()
        print(COM(n+m,n))

Solution (Python):
from numpy.linalg import solve
mod = 10**9+7
x,y=map(int,input().split(' '))
left = [[1,2],
        [2,1]]
right = [x,y]

A=solve(left,right)
ax,ay=float(A[0]),float(A[1])
if not 0.5 <= y/x <= 2:
    print(0)
    exit()
if not float.is_integer(ax) or not float.is_integer(ay):
    print(0)
    exit()
ax,ay=int(ax),int(ay)
fac=[0 for i in range(ax+ay+1)]
inv=[0 for i in range(ax+ay+1)]
finv=[0 for i in range(ax+ay+1)]
fac[0] = 1
fac[1] = 1
finv[0]=1
finv[1]=1
inv[1] = 1
for i in range(2,ax+ay+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
ans = fac[ax+ay]*(finv[ax]*finv[ay])
ans %= mod
print(int(ans))

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 = 666666
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:
    print(0)
else:    
    bg = max(X, Y)
    sm = min(X, Y)

    z = (bg + sm) // 3
    a = z - (z * 2 - bg)
    b = z - a
    
    print(cmb(a+b,a,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 
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 )

def is_integer(n):
    try:
        float(n)
    except ValueError:
        return False
    else:
        return float(n).is_integer()

X,Y = map(int,input().split())
a = (2*Y-X)/3
b = (2*X-Y)/3
if (X == 0 or Y == 0):
    print(0)
    exit()
if is_integer(a):
    a = (2*Y-X)//3
else:
    print(0)
    exit()
if is_integer(b):
    b = (2*X-Y)//3
else:
    print(0)
    exit()
n = a+b
mod = 10**9+7 
ans = cmb(n,a,mod)
print(ans)

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

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

if max(x,y) / min(x,y) > 2:
    print(0)
    exit()

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

fac = [1] * (n+1)
finv = [1] * (n+1)
inv = [1] * (n+1)
def com_init(n):
    for i in range(2, n+1):
        fac[i] = fac[i - 1] * i % M
        inv[i] = M- inv[M % i] * (M // i) % M
        finv[i] = finv[i - 1] * inv[i] % M
com_init(n)
def solve(n, k):
    return fac[n] * (finv[k] * finv[n - k] % M) % M

ans = solve(n, yn)
print(ans)

Solution (Python):
import math
MOD = 1000000000+7
X, Y = map(int, input().split())

if ((2*Y-X)%3 != 0) or ((2*X-Y)%3 != 0) or (2*Y-X) < 0 or (2*X-Y) < 0:
    print(0)
else:
    x = (2*Y-X) // 3
    y = (2*X-Y) // 3
    fac_list = [None for _ in range(x+y+2)]
    inv_fac_list = [None for _ in range(x+y+2)]

    fac_list[0] = 1
    for i in range(1, x+y+2):
        fac_list[i] = i * fac_list[i-1] % MOD

    inv_fac_list[x+y+1] = pow(fac_list[x+y+1],(MOD - 2), MOD)
    for i in range(x+y, -1, -1):
        inv_fac_list[i] = inv_fac_list[i+1] * (i+1) % MOD

    print((fac_list[x+y] * inv_fac_list[x] * inv_fac_list[y]) % MOD)

Solution (Python):
import math

N = 10 ** 9 + 7
X, Y = map(int, input().split())
B3 = 2 * X - Y
if B3 % 3:
    print(0)
    exit()
B = B3 // 3
A = X - 2 * B
if A < 0 or B < 0:
    print(0)
    exit()













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

print(cmb(A + B,A) % N)

Solution (Python):


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

x=(2*X-Y)/3
y=X-2*x
if x!=int(x) or y!=int(y):
    print(0)
    exit()
else:
    x=int(x)
    y=int(y)

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

if x<0 or y<0:
    print(0)
    exit()

n=x+y
r=min(x,y)

ans=cmb(n,r)
if x==0:
    if Y==2*y and X==Y//2:
        print(ans)
    else:print(0)
elif y==0:
    if X==2*x and Y==X//2:
        print(ans)
    else:print(0)
else:
    print(ans)

Solution (Python):

mod=10**9+7
MAX=10**6

g1=[1,1]
g2=[1,1]
for i in range(2,MAX+1):
    num_1=g1[-1]*i%mod
    g1.append(num_1)
    g2.append(pow(num_1,mod-2,mod))
    
def cmb(n,r,MOD):
    return g1[n]*g2[r]*g2[n-r]%MOD

x,y=map(int,input().split())
ans=0
for k in range(y//2+1):
    l=y-2*k
    if l>=0 and k+2*l==x:
        ans=(ans+cmb(k+l,k,mod))%mod
print(ans)

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

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

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

x,xm = divmod(X*2-Y, 3)
y,ym = divmod(-X+Y*2, 3)
if (xm == 0) & (ym==0)& (x>=0) & (y>=0):
    print(combination(x+y, x, mod))
else:
    print(0)

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


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

mod = 10**9+7
ans_list = []

x_list = []

for i in range(0, x//2+1):
    x_list.append([i, x-2*i])

for g,l in x_list:
    if (g+2*l)==y:
    	ans_list.append([g,l])

ans=0
A = Combination(10**6, mod)
for g,l in ans_list:
    ans += A(g+l,l)

print(ans)

Solution (Python):
import os

MAX = 10**6
MOD = 10**9 + 7

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, MAX + 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())
m = x + y
if m % 3 != 0:
    print(0)
    os.sys.exit()

n = int(m / 3)
k = x - n + 1

print(cmb(n, k-1))

Solution (Python):
import sys

sys.setrecursionlimit(10**6)

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

mod = int(10**9 + 7)

res = 0

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

N = 0
M = 0
if X <= Y:
    N += X
    M += Y
else:
    N += Y
    M += X

f = [1]
for i in range(N):
    f.append(f[i]*(i+1)%mod)

def comb(A,B,mod):
    if A >= B:
        temp = f[A] * pow(f[B],mod-2,mod) * pow(f[A-B],mod-2,mod) % mod
    else:
        temp = f[B] * pow(f[A],mod-2,mod) * pow(f[B-A],mod-2,mod) % mod
    return temp

def perm(A,B,mod):
    return f[A+B] * pow(f[A],mod-2,mod) * pow(f[B],mod-2,mod) % mod

for i in range(N):
    role1 = i + 1
    role2 = int((N - role1) / 2)
    roles = role1 + role2
    temp1 = role1 + role2 * 2
    temp2 = role1 * 2 + role2
    if (temp1 == N) & (temp2 == M):
        res += perm(role1,role2,mod)

    res %= mod




print(res)

Solution (Python):
import math
MOD = 1000000000+7
X, Y = map(int, input().split())

if ((2*Y-X)%3 != 0) or ((2*X-Y)%3 != 0) or (2*Y-X) < 0 or (2*X-Y) < 0:
    print(0)
elif 2 *Y == X or 2 * X == Y:
    print(1)
else:
    x = (2*Y-X) // 3
    y = (2*X-Y) // 3
    fac_list = [None for _ in range(x+y+2)]
    inv_fac_list = [None for _ in range(x+y+2)]

    fac_list[0] = 1
    for i in range(1, x+y+2):
        fac_list[i] = i * fac_list[i-1] % MOD

    inv_fac_list[x+y+1] = pow(fac_list[x+y+1],(MOD - 2), MOD)
    for i in range(x+y, 0, -1):
        inv_fac_list[i] = inv_fac_list[i+1] * (i+1) % MOD

    print((fac_list[x+y] * inv_fac_list[x] * inv_fac_list[y]) % 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 
N = 2*10**6//3 + 1
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 
x, y = map(int,input().split())

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 = 0
if (x + y)% 3 == 0:
    movtot = (x+y)//3
    movx = x - movtot

    ans = cmb(movtot,movx,mod)
    
print(ans)

Solution (Python):

x, y = map(int, input().split())
PRIME = 10 ** 9 + 7
if (x + y) % 3 == 0:
    n = (x + y) // 3
    if x >= n and y >= n:
        up = 2 * n - x
        factorial = 1
        for i in range(1, n + 1):
            factorial *= i
            factorial %= PRIME
        inv = pow(factorial, PRIME - 2, PRIME)
        invs = [1 for _ in range(n + 1)]
        invs[n] = inv
        for i in range(n, min(n - up, up), -1):
            inv *= i
            inv %= PRIME
            invs[i - 1] = inv
        print((factorial * invs[n - up] * invs[up]) % PRIME)
    else:
        print(0)
else:
    print(0)

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

tot = (X+Y) // 3

x = X - tot
y = tot - x

if x < 0:
	print(0)
	sys.exit()

if x == 0 or y == 0:
	print(1)
	sys.exit()

ans = 1
for i in range(y+1, tot+1):
	ans *= i
	ans %= mod

for i in range(1,x+1):
	ans *= pow(i, mod-2, mod)
	ans %= mod

print(ans%mod)

Solution (Python):
p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x%p
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
A = [1 for _ in range(10**6+1)]
for i in range(1,10**6+1):
    A[i] = (A[i-1]*i)%p
B = [1 for _ in range(10**6+1)]
B[10**6] = pow(A[10**6],p-2)
for i in range(10**6-1,1,-1):
    B[i] = (B[i+1]*(i+1))%p

X,Y = map(int,input().split())
if (X+Y)%3!=0:
    cnt = 0
else:
    k = (X+Y)//3
    if X>Y:
        X,Y = Y,X
    n = X-k
    if X<k:
        cnt = 0
    else:
        cnt = (((A[k]*B[n])%p)*B[k-n])%p
print(cnt)

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


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())
MOD = 1000000007

dP = dict()
vQ = []

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

N = (X+Y)//3
K = X - N
nCk = cmb(N,K,MOD)

print(nCk)

Solution (Python):


ans = 0 
mod = 10**9 + 7 

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

a = (2*y-x)/3
b = (2*x-y)/3
N = 10**6
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 

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.is_integer() and b.is_integer():
    a = int(a)
    b = int(b)
    ans = cmb(a+b,b,mod)
    print(ans)
else:
    print(0)

Solution (Python):
INF = 1000000000+7

x,y = map(int, input().split())
a = 2*x-y
b = -x + 2*y
if a%3!=0 or b%3!=0:
    print(0)
    exit()

n = a//3
m = b//3
nm = n+m

def cmb(n,r):
    if r > n:
        return 0
    if n - r < r:
         r = n - r
    if r > n:
        return 0
    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 n<0 or m<0:
    print(0)
    exit()
ans = cmb(nm,n)
print(ans%INF)

Solution (Python):

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


MOD = 10**9 + 7

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

pascal_depth = int((X + Y) / 3)  
x, y = int((X + Y) * 2 / 3), (X + Y) / 3
pascal_k = x - X  

if pascal_k > pascal_depth / 2:
    pascal_k = pascal_depth - pascal_k



































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 = pascal_depth
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 = cmb(pascal_depth, pascal_k, mod)
print(a)

Solution (Python):
import sys


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] 


x, y = [int(_) for _ in input().split()]
n = 1500000
p = 10**9+7
l = []
for i in range(0, n*3//2+1, 3):
    l.append(i)

if x/2 <= y <= 2*x:
    for i in l:
        if y == i - x:
            t = i//3
            N = t
            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(t,x-t,10**9+7))
            sys.exit()
print(0)

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np
from math import factorial
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 )
def print_ans(X, Y):
    """Test Case
    >>> print_ans(3, 3)
    2
    >>> print_ans(2, 2)
    0
    >>> print_ans(999999, 999999)
    151840682
    """
    A = np.array([[1, 2],[2, 1]])
    B = np.array([X, Y])
    X = np.linalg.solve(A, B)
    if X[0].is_integer() and X[1].is_integer() :
        
        
        
        
        
        print(cmb(int(X[0] + X[1]),int(X[0]),mod))
        
    else:
        print("0")


if __name__ == '__main__':
    X, Y = map(int, input().rstrip().split())
    print_ans(X, Y)

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

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

max_diff = min(X,Y)
if (X+Y) % 3 == 0:
  n = (X + Y) // 3
  k = max_diff - n
  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 )
  ans = cmb(n,k,mod)
else:
  ans = 0

print(ans)

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

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    
    return [w[0],w[1]]


def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

if (X+Y)%3 != 0:
    ans = 0
elif min(X,Y)*2 < max(X,Y):
    ans = 0
else:
    A = (min(X,Y)-abs(X-Y))//3+abs(X-Y)
    B = (min(X,Y)-abs(X-Y))//3
    ans = 1
    for i in range(A):
        ans = ans*(A+B-i)%P
    for i in range(1,A+1):
        ans = ans*mod_inv(i,P)%P
print(ans)

Solution (Python):
import math

def comb(n, k, MOD, N):
    fact = [1]*(N+1)
    rfact = [1]*(N+1)
    r = 1
    for i in range(1, N+1):
        fact[i] = r = r * i % MOD
    rfact[N] = r = pow(fact[N], MOD-2, MOD)
    for i in range(N, 0, -1):
        rfact[i-1] = r = r * i % MOD
    return fact[n] * rfact[k] * rfact[n-k] % MOD

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

diff = abs(x-y)
if (min(x, y) - diff) % 3 != 0 or (min(x, y) - diff) < 0:
    print(0)
else:
    count = (min(x, y) - diff) // 3
    print(comb(2*count+diff, count, mod, 10**6))

Solution (Python):
import numpy as np
import math
X,Y = map(int,input().split())


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

else:
  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
  
  c1 = c1//3
  c2 = Y-2*c1
  c3 = c1+c2
  mod = 10**9+7
  g1 = [1, 1]
  g2 = [1, 1]
  inverse = [0, 1]
  for i in range( 2,c3+1):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

  a = cmb(c3,c1,mod)

  print(a)

Solution (Python):
from math import factorial

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 (x + y) % 3 != 0:
    print(0)
else:
    n = (x + y) // 3
    a = 2 * (x + y) // 3
    b = (x + y) // 3
    
    if x > a or y > a:
        print(0)
    else:
        t = a-x
        
        p = 10 ** 9 + 7
        
        k = comb(n, n-t, p)
        
        print(k)

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

X,Y = map(int,input().split())
if(X>Y): x,y = Y,X
else: x,y = X,Y
  


ans = -1
for i in range(y+1):
  
  tmp_x,tmp_y = 2*i,1*i 
  res_x,res_y = x-tmp_x,y-tmp_y
  if(res_x > 0):
    if((res_y%res_x == 0)and(res_y//res_x == 2)):
     n1 = i
     n2 = res_x
     break
  elif(res_x == 0):
     if(res_y == 0):
       n1 = i
       n2 = i
     else: ans = 0
     break
  elif(res_x < 0):
    ans = 0
    break
    
if(ans != 0):
 mod = 10**9+7 
 N = n1+n2
 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 )
 r = min(n1,n2)
 ans = cmb(N, r, mod)

  
if((x+y)%3 != 0): ans = 0
ans = ans%(10**9 + 7)
print(ans)

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

MOD = 10 ** 9 + 7

xx = 2 * Y - X
if (xx >= 0 and xx % 3 == 0 and Y - 2 * xx // 3 >= 0):
    a = xx // 3
    b = Y - 2 * a

    f = 1
    factorials = [1]
    for m in range(1, a + b + 1):
        f *= m
        f %= MOD
        factorials.append(f)

    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (a + b + 1)
    invs[a + b] = inv
    for m in range(a + b, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv


    print (factorials[-1] * invs[a] * invs[b] % MOD)

    


else:
    print (0)

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

class ModComb:
    def __init__(self, MAX, mod=10 ** 9 + 7):
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, MAX):
            fac.append(fac[i - 1] * i % mod)
            inv.append(mod - inv[mod % i] * (mod // i) % mod)
            finv.append(finv[i - 1] * inv[i] % mod)
        self.fac, self.finv, self.mod = fac, finv, mod
 
    def nCk(self, n, k):
        if n < k or n < 0 or k < 0:
            return 0
        fac, finv, mod = self.fac, self.finv, self.mod
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod

if (x+y)%3!=0:
    print(0)
else:
    a = (2*x - y) // 3
    b = (2*y - x) // 3

    mod = 10 ** 9 + 7
    mc = ModComb(1000000, mod=mod) 

    print(mc.nCk(a + b, a) % mod)

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

MOD = 10**9 + 7

def power_func(a,b,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

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

factorial = [1]
for n in range(1, X+Y):
    factorial.append(factorial[n-1]*n%MOD)

ans = 0
prv_m, prv_n = None, None
done = set([])
for m in range(X):
  if (X-m)%2 == 1:continue
  n = (X-m)//2
  if 2*m+n != Y: continue
 
  ans += factorial[m+n]*power_func(factorial[m],MOD-2,MOD)*power_func(factorial[n],MOD-2,MOD)
  ans %= MOD
  done.add((m,n))

for m in range(Y):
  if (Y-m)%2 == 1:continue
  n = (Y-m)//2
  if 2*m+n != X or (n,m) in done: continue
  ans += factorial[m+n]*power_func(factorial[m],MOD-2,MOD)*power_func(factorial[n],MOD-2,MOD)
  ans %= MOD

print(ans%MOD)

Solution (Python):



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 


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

if not((x + y) % 3 == 0):
    print(0)
elif (x > 2*y) or (y > 2 * x):
    print(0)
else:
    k = (x + y) // 3
    i = x - k
    print(ncr(k, i, 10 ** 9 + 7))

Solution (Python):
from functools import reduce

prime = 1000000007


def modpow(a: int, n: int, mod: int = prime) -> int:
    res = 1
    while n > 0:
        if n & 1 != 0:
            res = res * a % mod
        a = a * a % mod
        n = n // 2
    return res


def modinv(a: int, mod: int = prime) -> int:
    return modpow(a, mod-2, mod)


def modfactrial(n: int, mod: int = prime) -> int:
    return reduce(lambda x, y: (x*y) % mod, range(1, n+1), 1)


def modcombination(n: int, r: int, mod: int = prime) -> int:
    
    n_fact = modfactrial(n, mod)
    r_fact = modfactrial(r, mod)
    nr_fact = modfactrial(n-r, mod)
    r_fact_inv = modinv(r_fact, mod)
    nr_fact_inv = modinv(nr_fact, mod)
    return n_fact * r_fact_inv * nr_fact_inv % mod


def abort():
    import sys
    print(0)
    sys.exit(0)


x, y = [int(x) for x in input().split()]
if (2*x-y) % 3 != 0:
    abort()
if (2*y-x) % 3 != 0:
    abort()
n = (2*y-x)//3
m = (2*x-y)//3

if n < 0 or m < 0:
    abort()
print(modcombination(n+m, n))