Problem:
 Score : 400 points    Problem Statement There is a knight - the chess piece - at the origin (0, 0) of a two-dimensional grid.  When the knight is at the square (i, j) , it can be moved to either (i+1,j+2) or (i+2, j+1) .  In how many ways can the knight reach the square (X, Y) ?  Find the number of ways modulo 10^9 + 7 .      Constraints  1 \leq X \leq 10^6  1 \leq Y \leq 10^6  All values in input are integers.         Input Input is given from Standard Input in the following format:  X  Y       Output Print the number of ways for the knight to reach (X, Y) from (0, 0) , modulo 10^9 + 7 .        Sample Input 1 3 3      Sample Output 1 2  There are two ways: (0,0) \to (1,2) \to (3,3) and (0,0) \to (2,1) \to (3,3) .       Sample Input 2 2 2      Sample Output 2 0  The knight cannot reach (2,2) .       Sample Input 3 999999 999999      Sample Output 3 151840682  Print the number of ways modulo 10^9 + 7 .

Solution (Python):



def count_combination(n: int, r: int, mod: int = 10 ** 9 + 7) -> int:
    '''Count the total number of combinations.
        nCr % mod.
        nHr % mod = (n + r - 1)Cr % mod.
    Args:
        n   : Elements. Int of number (greater than 1).
        r   : The number of r-th combinations. Int of number (greater than 0).
        mod : Modulo. The default is 10 ** 9 + 7.
    Returns:
        The total number of combinations.
    Landau notation: O(n)
    See:
    https://qiita.com/derodero24/items/91b6468e66923a87f39f
    '''

    if (r > n) or (n < 0) or (r < 0):
        return 0

    if r > (n - r):
        return count_combination(n, n - r, mod)

    if r == 0 or r == n:
        return 1

    if r == 1:
        return n

    multiple = 1
    division = 1

    for i in range(r):
        multiple *= n - i
        division *= i + 1
        multiple %= mod
        division %= mod

    return multiple * pow(division, mod - 2, mod) % mod


def main():
    large_x, large_y = map(int, input().split())
    x = -large_x + 2 * large_y
    y = 2 * large_x - large_y

    
    
    

    
    
    
    

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

    
    
    xy = (x + y) // 3
    y = y // 3
    print(count_combination(xy, y))

    
    


if __name__ == '__main__':
    main()

Solution (Python):



def count_combination(n: int, r: int, mod: int = 10 ** 9 + 7) -> int:
    '''Count the total number of combinations.
        nCr % mod.
        nHr % mod = (n + r - 1)Cr % mod.
    Args:
        n   : Elements. Int of number (greater than 1).
        r   : The number of r-th combinations. Int of number (greater than 0).
        mod : Modulo. The default is 10 ** 9 + 7.
    Returns:
        The total number of combinations.
    Landau notation: O(n)
    See:
    https://qiita.com/derodero24/items/91b6468e66923a87f39f
    '''

    if (r > n) or (n < 0) or (r < 0):
        return 0

    if r > (n - r):
        return count_combination(n, n - r, mod)

    if r == 0 or r == n:
        return 1

    if r == 1:
        return n

    multiple = 1
    division = 1

    for i in range(r):
        multiple *= n - i
        division *= i + 1
        multiple %= mod
        division %= mod

    return multiple * pow(division, mod - 2, mod) % mod


def main():
    large_x, large_y = map(int, input().split())
    x = -large_x + 2 * large_y
    y = 2 * large_x - large_y

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

    xy = (x + y) // 3
    y = y // 3
    print(count_combination(xy, y))


if __name__ == '__main__':
    main()

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

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

if max(x, y) > 2 * min(x, y) or (x+y) % 3 != 0:
    print(0)
else:
    n = (x + y) // 3
    r = 2 * n - x
    print(nCr(n, r))

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
from math import factorial






















def make_comb(m, d):
    def div(i, j):
        
        
        p = j - 2
        ans = 1
        while p != 0:
            if p % 2 == 1:
                ans = (ans * i) % d
            i = i**2 % d
            p >>= 1
        return ans

    fac = [0] * (m+1)
    ifac = [0] * (m+1)
    
    fac[0] = 1
    ifac[0] = 1
    for i in range(m):
        fac[i+1] = (fac[i] * (i+1)) % d
        ifac[i+1] = (ifac[i] * div(i+1, d)) % d
    def comb(n, k):
        if n == 0 and k == 0:
            return 1
        if n < k or n < 0:
            return 0
        return (fac[n] * ifac[k] * ifac[n-k]) % d
    return comb

def main():
    x, y = map(int, input().strip().split())
    if (x + y) % 3 != 0:
        print(0)
        return
    k = (x+y) // 3
    q = x - k
    if x - 2 * q < 0 or q < 0:
        print(0)
        return
    comb = make_comb(10**6, 10**9+7)
    print(comb(k, q))

if __name__ == '__main__':
    main()

Solution (Python):
def cmb(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    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)
else:
    
    
    
    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)
        ans = cmb(total, n, MOD, fac, ifac)
        print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

MOD = 10**9 + 7


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


def make_table(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


def main():
    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:
        fac, ifac = make_table(total)
        ans = cmb(total, n, fac, ifac)
        print(ans)


if __name__ == '__main__':
    main()

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

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

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

X = max(x,y)
Y = min(x,y)

all_move = (X+Y)//3
diff = (X-Y)
Y_move = (all_move - diff)//2


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

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

print(mod_cmb(all_move, Y_move,MOD))

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

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

if max(x,y) > 2 *min(x,y):
    print(0)
elif (x+y) % 3 == 0:
    k = (x+y)//3
    n = (2*x-y)//3
    print(nCr(k,n))
else:
    print(0)

Solution (Python):
X, Y = map(int, input().split())
MOD = int(pow(10, 9) + 7)
def isValid(x, y):
    if (X + Y) % 3 != 0:
        return False
    S = (X + Y) // 3
    return Y >= S and X >= S

if not isValid(X, Y):
    print(0)
    quit()

S = (X + Y) // 3
A = (2 * X - Y) // 3

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

def modInverse(x, power=MOD - 2):
    if power == 0: return 1
    cur = modInverse(x, power // 2); cur *= cur; cur %= MOD
    if power % 2 == 1:
        cur *= x
    cur %= MOD
    return cur


print((fact[S] * modInverse(fact[A]) * modInverse(fact[S-A])) % MOD)

Solution (Python):




import itertools
import numpy as np
from scipy.spatial import distance


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


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


if P[0]%2 == 0:
    X2 = int(P[0]/2); X1 = 0
else:
    X2 = int(P[0]/2); X1 = 1


Y_check = []
Y = []
for y in range(X2+1):
    if 2*(P[0]-2*y)+y == P[1]:
        Y.append(y)
    Y_check.append(2*(P[0]-2*y)+y)


x = np.array(["1", "2"])
for i in range(len(Y)):
    
    
    print(cmb(Y[i]+P[0]-2*Y[i], Y[i])%(10**9+7))

if not Y:
    print(0)

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

def nCr(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 (2*X-Y)%3 != 0 or (2*Y-X)%3 != 0 or Y > X*2 or X > Y*2:
  print(0)
else:
  m = (2*X-Y)//3
  n = (2*Y-X)//3
  print(nCr(m+n, n))

Solution (Python):
def nCk(n,k):
    if n<k or (n<0 or k<0):
        return 0
    
    num,denum=1,1
    for i in range(k):
        num=num*(n-i)%mod
        denum=denum*(i+1)%mod
    return num*pow(denum,mod-2,mod)%mod

x,y=map(int,input().split())
mod=10**9+7
n=(y-0.5*x)/1.5
if int(n)!=n:
    print(0)
else:
    m=(y+x)//3
    l=int(n)
    print(nCk(m,l))

Solution (Python):

import sys











mod = 10 ** 9 + 7

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

    numerator = list(range(n-r+1, n+1))
    denominator = list(range(1, r+1))

    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(x) for x in sys.stdin.readline().split()]
    
    n, m = (2 * y - x) / 3, (2 * x - y) / 3

    if n != abs(int(n)) or m != abs(int(m)):
        print(0)
        sys.exit()
    else:
        n, m = int(n), int(m)
        ans = comb(n+m, n) % mod
        print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
def make_tables(m):
    fac=[1,1]
    finv=[1,1]
    inv=[0,1]
    for i in range(2,m+1):
        fac.append((fac[-1]*i)%mod)
        inv.append((-inv[mod%i]*(mod//i))%mod)
        finv.append(finv[i-1]*inv[i]%mod)
    return fac,finv

def calc_nCk(n,k,fac,finv):
    if n<k or (n<0 or k<0):
        return 0

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

x,y=map(int,input().split())
mod=10**9+7
n=(y-0.5*x)/1.5
if int(n)!=n:
    print(0)
else:
    m=(y+x)//3
    l=int(n)
    fac,finv=make_tables(m)
    ans = calc_nCk(m,l,fac,finv)
    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 % (10 ** 9 + 7)
ab = input().split()
a, b = int(ab[0]), int(ab[1])
sum = a + b
if a>(2*b) or b>(2*a):
	print("0")
elif sum % 3 == 0:
    n = int(sum / 3)
    m = b - n
    print(cmb(n, m))
else:
	print("0")

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


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

    if (X + Y) % 3 or X > Y*2 or Y > X*2:
        return 0

    n = (X + Y) // 3
    r = Y - n
    return(combination(n, r))


print(main())

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

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

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

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

X, Y = [int(x) for x in input().strip().split()]
p = (X, 2 * X)
n1 = X
n2 = 0
f = True
while p != (X, Y):
    n1 -= 2
    n2 += 1
    p = (n1 + 2 * n2, 2 * n1 + n2)
    if p[1] <= 0:
        f = False
        break

if n1 < 0 or n2 < 0:
    print(0)
else:
    print(combination(n1 + n2, n1))

Solution (Python):

import sys
import math

MOD = 1000000007  

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 





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

    n = -1
    for m in range(X + 1):

        

        
        
        
        

        if (X - m) / 2 == (Y - (2 * m)):
            n = int((X - m) / 2)
            
            break

    

    if(n == -1):
        print(0)
    else:
        
        print(ncr((m + n), n, MOD))

    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):
x, y = map(int, input().split())
mod = 10**9+7
def inv(x):
        return pow(x, mod-2, mod)
def fact(x):
        f = 1 
        for i in range(1, x + 1): 
                f *= i
                f %= mod    
        return f
def comb(n, r): 
        return (fact(n) * inv(fact(n-r)) * inv(fact(r))) % mod 
if (x + y) % 3 != 0:
  print(0)
else:
  n = (x + y) // 3
  if n > x or n > y:
    print(0)
  else:
    nx = x - n
    print(comb(n, nx))

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

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

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

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

X, Y = [int(x) for x in input().strip().split()]
p = (X, 2 * X)
n1 = X
n2 = 0
f = True
while p != (X, Y):
    n1 -= 2
    n2 += 1
    p = (n1 + 2 * n2, 2 * n1 + n2)
    if p[1] <= 0:
        f = False
        break

if n1 < 0 or n2 < 0:
    print(0)
else:
    print(combination(n1 + n2, n1) % (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

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


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

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

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):
import sys
from math import factorial

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 

def check(x, y):
    if (x + y) % 3 == 0:
        return True
    else:
        return False
    


line = sys.stdin.readlines()[0]
X, Y = map(int,line.split(' '))

if not check(X, Y):
    print(0)
    exit(0)

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

if n < 0 or m < 0:
    print(0)
else:
    print(ncr(n+m, n, 10**9+7))

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())
if (x+y)%3!=0 or min(x,y)<(x+y)/3:
    print(0)
    exit()
n=(x+y)//3
r=(n-abs(x-y))//2
mod=10**9+7
a = cmb(n,r)
print(a%mod)

Solution (Python):

import sys











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

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 main():
    x, y = [int(x) for x in sys.stdin.readline().split()]
    
    n, m = (2 * y - x) / 3, (2 * x - y) / 3

    if n != abs(int(n)) or m != abs(int(m)):
        print(0)
        sys.exit()
    else:
        n, m = int(n), int(m)
        ans = comb(n+m, m, mod)
        print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
def getComb(n, k, MOD):
    if n < k:
        return 0
    if n-k < k:
        k = n-k
    comb = 1
    for x in range(n-k+1, n+1):
        comb = (comb * x) % MOD
    d = 1
    for x in range(1, k+1):
        d = (d * x) % MOD
    comb *= pow(d, MOD-2, MOD)
    return comb % MOD
    
X,Y = [int(i) for i in input().split()]
def check(x,y):
    if x/2 == y:
        return 0
    elif x/2 < y:
        return 1
    else:
        return 9
cnt = 0
possible = True
MOD = 10**9 + 7

while True:
    check_num =  check(X,Y)
    if check_num == 0:
        break
    elif check_num == 1:
        X += 1
        Y -= 1
        cnt += 1
    else:
        possible = False
        break
if possible == True:
    n = X // 2 
    r = cnt
    print(getComb(n,r,MOD))
else:
    print(0)

Solution (Python):
def fact(n, r):
    calc_a = 1
    calc_b = 1
    for i in range(1, r + 1):
        calc_a = (calc_a * (n + 1 - i)) % p
        calc_b = (calc_b * i) % p
    ans = (calc_a * pow(calc_b, p - 2, p)) % p
    return ans


p = (10 ** 9) + 7
x, y = map(int, input().split())
if ((2 * y - x) % 3 == 0) & ((2 * x - y) % 3 == 0) & (2 * y >= x) & (2 * x >= y):
    a = (2 * y - x) // 3
    b = (2 * x - y) // 3
    print(fact(a + b, min(a, b)))
else:
    print(0)

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 or Y / X > 2 or Y / X < 1 / 2:  
    print(0)
    exit()

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


def combination(n, r, mod=MOD):
    r = min(r, n - r)
    nf = rf = 1
    for i in range(r):
        nf = nf * (n - i) % mod
        rf = rf * (i + 1) % mod
    return nf * pow(rf, mod - 2, mod) % mod














a = combination(pascal_depth, pascal_k, MOD)
print(a)

Solution (Python):
def comb(n,k):
  s=1
  r=min(k,n-k)
  p=10**9+7
  for c in range(r):
    s=(s*(n-c)*pow(c+1,p-2,p))%p
  return s

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

if (x+y)%3:
  print(0)
else:
  m=y-(x+y)//3
  n=x-(x+y)//3
  if m < 0 or n < 0:
    print(0)
  else:
    print(comb(m+n,m))

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)
    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)
    return g1[n] * g2[r] * g2[n - r] % mod


a = cmb(pascal_depth, pascal_k, MOD)
print(a)

Solution (Python):
import sys
import math
from operator import mul
from functools import reduce
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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= (int(_) for _ in input().split()) 
if (x+y)%3!=0:
    print(0)
    sys.exit()
else:
    n=(x+y)/3
    n=int(n)
    if x<n or y<n:
         print(0)
         sys.exit()
    else:
        x=x-n
        y=y-n
        ans=int(cmb(x+y, x,mod))
        print(ans%1000000007)

Solution (Python):


def com(n,k):
    if k==0:
        return 1
    s=n
    p=10**9+7
    inv=[0,1]
    for c in range(2,k+1):
        inv.append((-(p//c)*inv[p%c])%p)
        s=(((s*(n+1-c))%p)*inv[c])%p
    return s


x,y=map(int,input().split())
if (x+y)%3!=0 or 2*y<x or 2*x<y:
    print(0)
else:
    r=min(2*y-x,2*x-y)//3
    print(com((x+y)//3,r))

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 % 3 == 1 and Y % 3 == 1:
    print(0)
    exit()
if X % 3 == 2 and Y % 3 == 2:
    print(0)
    exit()

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


mod = 10**9+7 
N = a + b + 3
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, b, mod))

Solution (Python):
def mp(a,n,mod):
    if n==1:
        return a%mod
    aq=(mp(a,n//2,mod))**2
    ar=a**(n%2)
    return (((aq)%mod)*ar)%mod


def s_comb(n,k):
    s=1
    r=min(k,n-k)
    p=10**9+7
    for c in range(r):
        s=(s*(n-c)*mp(c+1,p-2,p))%p
    return s

x,y=map(int,input().split())
if (x+y)%3!=0 or 2*y<x or 2*x<y:
    print(0)
else:
    r=int(min(2*y-x,2*x-y)/3)
    print(s_comb(int((x+y)/3),r))

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

    def combination(n, r, mod):
        r = min(r, n - r)
        numerator, denominator = 1, 1
        for i in range(1, r + 1):
            numerator = (numerator * (n + 1 - i)) % mod
            denominator = (denominator * i) % mod
        return numerator * pow(denominator, mod - 2, mod) % mod

    if not (X <= 2 * Y and Y <= 2 * X):
        return 0

    n, m = (-X + 2 * Y) / 3, (2 * X - Y) / 3
    if not (n.is_integer() and m.is_integer()):
        return 0

    n, m = int(n), int(m)
    return combination(n + m, n, 10**9 + 7)

print(d_knight())

Solution (Python):


def s_comb(n,k):
    s=1
    r=min(k,n-k)
    p=10**9+7
    for c in range(r):
        s=(s*(n-c)*pow(c+1,p-2,p))%p
    return s


x,y=map(int,input().split())
if (x+y)%3!=0 or 2*y<x or 2*x<y:
    print(0)
else:
    r=min(2*y-x,2*x-y)//3
    print(s_comb((x+y)//3,r))

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

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

def nCk(n, k, mod=10**9+7):
  
  ans = 1
  for i in range(1, k+1):
    ans = ans*(n-i+1)*pow(i, mod-2, mod)%mod
    
  return ans

ans = 0

if (2*x-y)%3==0 and (2*y-x)%3==0 and 2*y-x>=0 and 2*x-y>=0:
  k = (2*x-y)//3
  l = (2*y-x)//3
  
  ans = nCk(k+l, min(k, l))

print(ans)

Solution (Python):
x, y = map(int, input().split())
n = (2*y - x)//3 
m = (2*x - y)//3
mod = 10**9+7
def inv(x):
        return pow(x, mod-2, mod)
def fact(x):
        f = 1 
        for i in range(1, x + 1): 
                f *= i
                f %= mod    
        return f
def comb(n, r): 
        return (fact(n) * inv(fact(n-r)) * inv(fact(r))) % mod 
res = comb(n+m, m)
if (x + y) % 3 == 0 and n >= 0 and m >= 0:
        print(res)
else:
        print(0)

Solution (Python):
import subprocess
import os
import time


import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

input = sys.stdin.readline


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













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


def main():
    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:
        print(0)
        sys.exit()

    

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

    ans = cmb(n+m, n)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time

def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
ts=time.time()
sys.setrecursionlimit(10**6)

show_flg=False
show_flg=True

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo
        
ans=0

s,t=LI()
a=(2*t-s)//3
b=(2*s-t)//3


if (2*t-s)%3!=0 or (2*s-t)%3!=0:
    print(0)
    exit()

cm=Comb(a+b+1+1)
ans=cm.comb(a+b,min(a,b))
print(ans)

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

if X > Y:
    X, Y = Y, X
dist = X + Y
   
if dist % 3 != 0:
    print(0)
else:
    
    
    
    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)
        ans = cmb(total, n, MOD, fac, ifac)
        print(ans)

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

mod = 10**9 + 7
n = (2*y - x) // 3 
m = (2*x - y) // 3 
N = 10**6
g1 = [1,1]
g2 = [1,1]
inverse = [0,1]

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


if __name__ == '__main__':
    if (x+y) % 3 != 0:
        print(0)
        exit()
    if n < 0 or m < 0:
        print(0)
        exit()
    sum = n + m
    r = min(n,m)

    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(comb(sum,r,mod))

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


def z_pow(a, n):
    
    if n == 0:
        return 1
    if n == 1:
        return a % Z
    m = n // 2
    i = n - m * 2
    x = z_pow(a, m)
    return (x * x * z_pow(a, i)) % Z


def n_comb(n, i):
    if n - i < i:
        return n_comb(n, n - i)
    e = [1 for j in range(n + 1)]
    for j in range(n):
        e[j + 1] = (e[j] * (j + 1)) % Z
    return (e[n] * z_pow(e[i], Z - 2) * z_pow(e[n - i], Z - 2)) % Z


def calc(X, Y):
    if (X + Y) % 3 != 0:
        return 0
    n = (X + Y) // 3
    if X < n or Y < n:
        return 0
    return n_comb(n, X - n)


(X, Y) = tuple([int(s) for s in input().split()])
print(calc(X, Y))