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.



Sample input:
3 3


Sample output:
2

Submission status: Accepted

Solution code:
import numpy as np
class InvCom:
    def __init__(self, space, mod):
        self.mod = mod
        self.fac = list(np.zeros(space).astype(np.int64))
        self.finv = list(np.zeros(space).astype(np.int64))
        self.inv = list(np.zeros(space).astype(np.int64))
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        for i in range(2, space):
            self.fac[i] = self.fac[i - 1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i - 1] * self.inv[i] % self.mod

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

x, y = map(int,input().split(' '))
if (x + y) % 3 != 0:
    print(0)
else:
    m = (2 * x -y) // 3
    n = (y - m) // 2
    if n < 0 or m < 0:
        print(0)
    else:
        fact = InvCom(n + m + 1,1000000007)
        print(fact(n + m,n))

Submission status: Accepted

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

def inv_mod(a, p=MOD):
    def inv_mod_sub(a, p):
        if a == 1:
            return 1, 0
        else:
            d, r = p//a, p%a
            x, y = inv_mod_sub(r, a)
            return y-d*x, x
    if p < 0: p = -p
    a %= p
    return inv_mod_sub(a,p)[0] % p

def comb_mod(n, k):
    if k < 0 or k > n:
        return 0
    else:
        return f_mod[n]*f_mod_inverse[k]*f_mod_inverse[n-k] % MOD

if (2*y-x) % 3 != 0 or (2*x-y) % 3 != 0:
  print(0)
else:
  k,l = (2*y-x)//3,(2*x-y)//3
  f_mod=[1]*(10**6)
  f_mod_inverse=[1]*(10**6)
  for i in range(1,10**6):
    f_mod[i]=f_mod[i-1]*i%MOD
    f_mod_inverse[i]=f_mod_inverse[i-1]*inv_mod(i)%MOD
  print(comb_mod(k+l,l))

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
 
X, Y = map(int, input().split())
 
def getComb(n, k, MOD):
    if n < k:
        return 0
    if n-k < k:
        k = n-k
    comb = 1
    for x in range(n-k+1, n+1):
        comb = (comb * x) % MOD
    d = 1
    for x in range(1, k+1):
        d = (d * x) % MOD
    comb *= pow(d, MOD-2, MOD)
    return comb % MOD
 
if (X+Y)%3:
    ans = 0
else:
    K = (X+Y)//3
    if X < K or Y < K:
        ans = 0
    else:
        ans = getComb(K, X-K, MOD)
 
print(ans)

Submission status: Accepted

Solution code:
# D - Knight

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

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

# https://qiita.com/derodero24/items/91b6468e66923a87f39f
# を一部修正
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)

Submission status: Accepted

Solution code:
# D - Knight

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

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

# https://qiita.com/derodero24/items/91b6468e66923a87f39f
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)

Submission status: Accepted

Solution code:
import itertools
X, Y=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
MOD = 10**9 + 7
if (X+Y)%3 != 0:
    print(0)
else:

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

    # print(f"n:{n}, m:{m}")

    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)

Submission status: Accepted

Solution code:
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):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        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):
        # 0からnまでのmod逆元のリストを返す O(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()

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
# 拡張ユークリッド互除法を用いて逆元を求める
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)
        # 結局 コンビネーションkCiに帰着
        MOD = 10**9 + 7
        # まず階乗のmodを求める
        fac = [1]*(k + 1)
        for j in range(2, k + 1):
            fac[j] = fac[j - 1]*j%MOD
        # 次に階乗の逆元を求める
        finv = [0]*(k + 1)
        #finv[k] = pow(fac[k], MOD - 2, MOD) # fac[k]の逆元, フェルマーの小定理
        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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# import numpy as np
#N=int(input().strip())
#x=[0]*N
#y=[0]*N
#
#for i in range(N):
#    x[i],y[i]=list(map(int,input().strip().split()))

import sys

def power_l(x,power): # for mod
    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): # x^(-1)=x^(p-2) mod
    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()

# compute m+nCm=(m+n)!/(m!n!)
# make factorial
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 階乗は英語でfactrial, ifacは階乗に対する逆元
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):  # (mod mod)の世界における割り算に従ってテーブルを作る
    # 階乗, 階乗に対する逆元のテーブルを作成する
    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)

Submission status: Accepted

Solution code:
# 拡張ユークリッドアルゴリズム
# (d, x, y): d=ax+by を満たすd, x, yを求める
# aとbが互いに素な整数であればgcd(a,b)=d=1, ax=1 (mod b)
# xは法bの元でaの乗法逆元a^-1になる
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)

Submission status: Accepted

Solution code:
#!/usr/bin/pypy
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
#ans = (f(j) / f(X-j) / f(Y-j)) % mod

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)

Submission status: Accepted

Solution code:
#coding: utf-8
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

    # Combination Part1
    ## 最初に十分に大きいfactorical, invFactoricalのテーブルを作って、様々なcomに対応
    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
    # Combination part2
    ## combinationのnの枠が決まっていたり、数回くらいしか計算しないなら、一気にテーブルと計算を行う
    
    # n,kが小さい時(2000程度),動的計画法で、nCkのテーブルを作る(mod pが素数でなくていい)   

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

# X = n + 2 * m
# Y = 2 * n + m

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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
def factorials(n,m):
    # 0~n!のリスト
    f = [1,1]
    for i in range(2,n+1):
        f.append(f[-1]*i%m)

    # 0~n!の逆元のリスト
    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)

Submission status: Accepted

Solution code:
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  # factorial of n mod p = 1 * 2 * ... * n mod p
    inv = [0, 1] # inv[i] : inverse of i mod p
    invfct_k = 1 # factorial of inverse of k mod p = 1^(-1) * 2^(-1) * ... * k^(-1) mod p
    invfct_n_k = 1  # factorial of inverse of (n-k) mod p

    # Calculate inverse, factorial, factorial of inverse of i
    # all at the same time
    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)

Submission status: Accepted

Solution code:
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()
#print("modefied X,Y  "+str(X)+" "+str(Y))
mod=10**9+7 
def nCr(n, r, mod):#mod=10**9+7 
    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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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: # yCc
        print(comb(y, count, 10**9+7))
        exit()
    if y*2 < x: # ない
        print(0)
        exit()
    
    count += 1
    x += 1
    y -= 1

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 1000000007  # type: int


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))  # type: int
    Y = int(next(tokens))  # type: int
    solve(X, Y)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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]
# print(x,y,n)
# print(factX,factY,factN)

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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 #(+2,+1)の移動回数
    print(comb_mod(int(N), int(mov_x), mod))

Submission status: Accepted

Solution code:
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)