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:
def main():
    x,y=map(int,input().split())
    if (x+y)%3!=0:
        print(0)
        return 0
    n=(x+y)//3
    h=x-n
    w=y-n
    if h<0 or w<0:
        print(0)
        return 0
    def fact(n,mod=10**9+7):
        ans=1
        for i in range(1,n+1):ans=(ans*i)%mod
        return ans
    def inv_n(n,mod=10**9+7):return pow(n,mod-2,mod)
    def nPr(n,r,mod=10**9+7):return inv_n(fact(n-r,mod),mod)*fact(n,mod)%mod
    def nCr(n,r,mod=10**9+7):return inv_n(fact(n-r,mod)*fact(r,mod)%mod,mod)*fact(n,mod)%mod
    print(nCr(h+w,w))

main()

Submission status: Accepted

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

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 )


a = (2*x-y)//3
b = (2*y-x)//3
n = a+b
r = a
res = cmb(n,r,mod)
print(res)

Submission status: Accepted

Solution code:
import sys, math
mod = 10**9+7
X, Y = map(int, input().split())
if X>Y:
    X, Y = Y, X
if (X+Y)%3 !=0:
    print(0)
    sys.exit()
n = (X+Y)//3
d = (Y-X)
if n<d or (n-d)%2 != 0:
    print(0)
    sys.exit()
a = (n-d)//2
def make_fact(n):#0~nの階乗を求める
    fact = [1]*(n+1)
    for i in range(1, n+1):
        fact[i] = fact[i-1]*i%mod
    return fact
fact = make_fact(n)  
def make_fact_inv(n):#0~nの階乗のmodに関する逆元を求める
    fact_inv = [1]*(n+1)
    fact_inv[n] = pow(fact[n], mod-2, mod)#フェルマーの小定理
    for i in range(n, 0, -1):
        fact_inv[i-1] = fact_inv[i]*i%mod
    return fact_inv
fact_inv = make_fact_inv(n)

def comb(n, k):#nCk
    return fact[n]*fact_inv[k]*fact_inv[n-k]%mod

print(comb(n, a))

Submission status: Accepted

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

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

X, Y = map(int, input().split())
if (2 * X - Y) % 3 != 0 or (X - 2 * Y) % 3 != 0:
    print(0)
    quit()

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

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

Submission status: Accepted

Solution code:
class Combinatorics:
    def __init__(self, N, mod):
        '''
        Preprocess for calculating binomial coefficients nCr (0 <= r <= n, 0 <= n <= N)
        over the finite field Z/(mod)Z.
        Input:
            N (int): maximum n
            mod (int): a prime number. The order of the field Z/(mod)Z over which nCr is calculated.
        '''
        self.mod = mod
        self.fact = {i: None for i in range(N+1)}         # n!
        self.inverse = {i: None for i in range(1, N+1)}   # inverse of n in the field Z/(MOD)Z
        self.fact_inverse = {i: None for i in range(N+1)} # inverse of n! in the field Z/(MOD)Z
        
        # preprocess
        self.fact[0] = self.fact[1] = 1
        self.fact_inverse[0] = self.fact_inverse[1] = 1
        self.inverse[1] = 1
        for i in range(2, N+1):
            self.fact[i] = i * self.fact[i-1] % self.mod
            q, r = divmod(self.mod, i)
            self.inverse[i] = (- (q % self.mod) * self.inverse[r]) % self.mod
            self.fact_inverse[i] = self.inverse[i] * self.fact_inverse[i-1] % self.mod
    
    def perm(self, n, r):
        '''
        Calculate nPr = n! / (n-r)! % mod
        '''
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return (self.fact[n] * self.fact_inverse[n-r]) % self.mod
    
    def binom(self, n, r):
        '''
        Calculate nCr = n! /(r! (n-r)!) % mod
        '''
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return self.fact[n] * (self.fact_inverse[r] * self.fact_inverse[n-r] % self.mod) % self.mod
        
    def hom(self, n, r):
        '''
        Calculate nHr = {n+r-1}Cr % mod.
        Assign r objects to one of n classes.
        Arrangement of r circles and n-1 partitions:
            o o o | o o | | | o | | | o o | | o
        '''
        if n == 0 and r > 0:
            return 0
        if n >= 0 and r == 0:
            return 1
        return self.binom(n + r - 1, r)

MOD = 10**9 + 7
X, Y = map(int, input().split())
if (X + Y) % 3 != 0: print(0)
else:
    x, y = ((2*X - Y) // 3, (-X + 2*Y) // 3)
    com = Combinatorics(x + y, MOD)
    print(com.binom(x+y, x))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def inv(x):
    return pow(x, mod - 2, mod)

def comb(n, b):
    if b > n - b:
        b = n - b
    r = 1
    for k in range(n, n-b, -1):
        r = r * k % mod
    d = 1
    for k in range(1, b+1):
        d = d * k % mod
    return r * inv(d) % mod

def main():
    x,y = LI()
    x,y = max(x,y), min(x,y)
    if (x+y) % 3 > 0 or x > y*2:
        return 0

    c = (x+y) // 3
    xc = (x-y) + (c - (x-y)) // 2

    return comb(c,xc)


print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
MOD = 10 ** 9 + 7
def choose(n, r):
    num = 1
    den = 1
    for i in range(r):
        num *= n - i
        num %= MOD
    for i in range(r):
        den *= i + 1
        den %= MOD
    return num * pow(den, MOD - 2, MOD) % MOD
def solve(x, y):
    if (x + y) % 3 != 0:
        return 0
    k = (x + y) // 3
    if x < k or y < k:
        return 0
    return choose(k, min(y - k, x - k))
print(solve(*map(int, input().split())))

Submission status: Accepted

Solution code:
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]
MOD=10**9+7
MAX=10**6+2
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)
def COM(n, k):
  if n < k: 
    return 0
  if n < 0 or k < 0:
    return 0
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
X,Y=[int(s) for s in input().split()]
if (X+Y)%3!=0:
  print(0)
else:
  A=(X+Y)//3
  X-=A
  Y-=A
  if X<0 or Y<0:
    print(0)
  else:
    print(COM(X+Y,X))

Submission status: Accepted

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

def modfact(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
    return fact,invfact

def resolve():
    x,y=map(int,input().split())
    if((x+y)%3):
        print(0)
        return

    z=(x+y)//3
    if(x-z<0 or y-z<0):
        print(0)
        return
    
    fact,invfact=modfact(z)
    print(fact[z]*invfact[x-z]%MOD*invfact[y-z]%MOD)
resolve()

Submission status: Accepted

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

mod = 10**9 + 7

def comb(n,k):
    k=min(k,n-k)
    a=1
    b=1
    for i in range(k):
        a*=n-i
        b*=i+1
        a%=mod
        b%=mod
    return (a * pow(b,mod-2,mod))%mod


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

Submission status: Accepted

Solution code:
con = 10 ** 9 + 7
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

class Combination(object):
	def __init__(self, N, con):
		self.fac = [0] * (N + 1)
		self.inv = [0] * (N + 1)
		self.finv = [0] * (N + 1)
		self.fac[0], self.fac[1] = 1, 1
		self.inv[1] = 1
		self.finv[0], self.finv[1] = 1, 1

		# 前計算
		for i in range(2, N + 1):
			self.fac[i] = self.fac[i - 1] * i % con
			self.inv[i] = self.inv[con % i] * (con - (con // i)) % con
			self.finv[i] = self.finv[i - 1] * self.inv[i] % con

	def com(self, k, N):
		return (self.fac[N] * self.finv[k] * self.finv[N - k]) % con

#処理内容
def main():
	X, Y = getlist()
	N = (X + Y) // 3
	if (X + Y) % 3 != 0:
		print(0)
	elif X < N or Y < N:
		print(0)
	else:
		C = Combination(N, con)
		ans = C.com(X - N, N)
		print(ans)

	

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
if (x+y)%3:
    print(0)
    exit()
c = (x+y)//3
x -= c; y -= c
if x<0 or y<0:
    print(0)
    exit()

n = x+y
mod = 10**9+7
fun = [1]*(n+1)
for i in range(1,n+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n+1)
rev[n] = pow(fun[n],mod-2,mod)
for i in range(n-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod

def nCr(n,r):
    if r > n:
        return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod
    
print(nCr(x+y,x))

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:
MOD = int(1e9+7)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


def fact(x):
    prev = 1
    ret = 1
    for i in range(1, x+1):
        ret = (i * prev) % MOD
        prev = ret
    return ret


def main():
    X, Y = map(int, input().split())
    N = (X+Y)//3
    if (X+Y) % 3 != 0 or X < N or Y < N:
        print(0)
        return
    ans = div(div(fact(N), fact(X-N)), fact(N*2-X))
    print(ans)


if __name__ == "__main__":
    main()

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

import sys
x,y=map(int,input().split())
if (x+y)%3!=0:
  print(0)
  sys.exit()
z=(x+y)//3
mod=10**9+7

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

print(cmb(z,y-z,mod))

Submission status: Accepted

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


if (-X + 2*Y) % 3 or (2*X - Y) % 3 or (-X + 2*Y) < 0 or (2*X - Y) < 0:
    print(0)
else:
    a = (-X + 2*Y) // 3
    b = (2*X - Y) // 3
    P = 10**9 + 7
    fa = [1]
    for i in range(1, a + b + 100):
        fa.append(fa[-1] * i % P)    
    print(fa[a+b] * pow(fa[a]*fa[b], P-2, P) % P)

Submission status: Accepted

Solution code:
# Ýć x^n
def pow(x,n):
    global p
    res=1
    prod=x
    while n>0:
        if n%2==1:
            res=(res*prod)%p
        prod=(prod*prod)%p
        n//=2
    return res

# t x^(-1)
def inv(x):
    global p
    res=1
    prod=x
    e=p-2
    while e>0:
        if e%2==1:
            res=(res*prod)%p
        prod=(prod*prod)%p
        e//=2
    return res

# Kć x!
def fact(x):
    if x<1:
        return 1
    global p
    res=1
    for i in range(2, x+1):
        res=(res*i)%p
    return res
    
# gš nCr
def combi(n,r):
    if r<0 or r>n:
        return 0
    else:
        a=fact(n)
        b=inv(fact(r))
        c=inv(fact(n-r))
        return(((a*b)%p)*c)%p

p=10**9+7
X,Y=map(int,input().split())
if (X+Y)%3!=0 or 2*X<Y or 2*Y<X:
    ans=0
else:
    a=(2*X-Y)//3
    b=(-X+2*Y)//3
    ans=combi(a+b,a)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

def combination_mod(n, k, mod):
    """ power_funcを用いて(nCk) mod p を求める """ 
    """ nCk = n!/((n-k)!k!)を使用 """

    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = fact[n] 
    b = fact[k]
    c = fact[n - k]
    return (a * pow(b, mod - 2, mod) * pow(c, mod - 2, mod)) % mod
    


#solve
def solve():
    x, y = LI()
    x, y = (2 * y - x) / 3, (2 * x - y) / 3
    if x.is_integer() and y.is_integer():
        print(combination_mod(int(x + y), int(x), mod))
    else:
        print(0)
    return


#main
if __name__ == '__main__':
    fact = [1] * (10 ** 6+1)
    for i in range(1, 10 ** 6):
        fact[i + 1] *= (fact[i] * (i+1)) % mod
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

k=(X+Y)//3
X-=k
Y-=k

if X<0 or Y<0:
    print(0)
    sys.exit()

FACT=[1]
for i in range(1,2*10**6+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**6,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0

print(Combi(X+Y,X))

Submission status: Accepted

Solution code:

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

l = 10**6+3

M = [1]  # i!のmod
m = 1
for i in range(1, l):
    m = (m * i) % mod
    M.append(m)

def inv(x, y):  # xのmod yでの逆元を返す関数
    yy = y - 2
    ans = 1
    while yy > 0:
        if yy % 2 == 1:
            ans = (ans * x) % y
        x = (x**2) % y
        yy //= 2
    return ans

# print(inv(8,13))

MI = [0] * (l-1) +[inv(M[l-1], mod)]  # i!の逆元
for i in range(l-2, -1, -1):
    MI[i] = MI[i+1] * (i+1) % mod

def C(x, y):  # コンビネーション
    ans = M[x]
    ans = (ans * MI[y]) % mod
    return (ans * MI[x-y]) % mod
ans=0
for i in range(x//2+1):
    j = x-i*2
    if j >= 0 and i+2*j == y:
        # print(i,j)
        ans = (ans + C(i+j, i))%mod
print(ans)

Submission status: Accepted

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

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

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

if 2 * x - y < 0:
    print(0)
    exit()

if 2 * y - x < 0:
    print(0)
    exit()

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

mod = 10**9 + 7
ans = 1
f1 = 1
f2 = 1

for i in range(1, a + b + 1):
    ans = ans * i % mod

for i in range(1, a + 1):
    f1 = f1 * i % mod

for i in range(1, b + 1):
    f2 = f2 * i % mod

ans = ans * pow(f1, mod-2, mod) % mod
ans = ans * pow(f2, mod-2, mod) % mod

print(ans)

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

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

if a==int(a) and b==int(b) and a>=0 and b>=0:
    #print(a+b,b)
    kosu=cmb(int(a+b), int(b))
    print(kosu%(10**9+7))
else:    
    print(0)

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
mod=10**9+7
if (x+y)%3!=0:print(0);exit()
if x*2<y or y*2<x:print(0);exit()
t=(x+y)//3
f=[1]
for i in range(1,10**6+7):f.append(f[-1]*i%mod)
def comb(a,b,m):return f[a]*pow(f[b],m-2,m)*pow(f[a-b],m-2,m)%m
print(comb(t,x-t,mod))

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

X,Y = II()

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

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

#0!~(n-1)!をmodしつつ求める
def fact_all(n,M=mod):
    f = [1]*n
    ans = 1
    for i in range(1,n):
        ans = ans*i
        ans = ans%M
        f[i] = ans
    return f


#a!をmodしつつ求める
def fact(a,M=mod):
    ans = 1
    for i in range(2,a+1):
        ans = ans*i
        ans = ans%M
    return ans


#互いに素なa,bについて、a*x+b*y=1の一つの解[x,y]を出力
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]]


#aの逆元(mod M)を求める（aとMは互いに素）
def mod_inv(a,M=mod):
    x = extgcd(a,M)[0]
    return (M+x%M)%M


#nCkをmodしつつ返す
def nCk(n,k,M=mod,fact_list=[],inv_list=[]):
    if fact_list and inv_list:
        return (fact_list[n]*inv_list[k]*inv_list[n-k])%M
    else:
        x = fact(n,M)
        y1 = mod_inv(fact(k,M),M)
        y2 = mod_inv(fact(n-k,M),M)
        return (x*y1*y2)%M
    
print(nCk(x+y,x,mod))

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
mod = 10**9 + 7
if (x+y)%3 != 0:
    print(0)
    exit()
if (2*y-x)%3 !=0 or (2*x-y)%3 != 0 or 2*y-x <0 or 2*x-y<0:
    print(0)
    exit()

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

def inverse(a,p):
    return pow(a,p-2,p)

def combination_modp(n, r, p): # nCr modpを求める
    r = min(n-r, r)
    result = 1
    for i in range(n, n-r, -1):
        result *= i
        result %=p
    for i in range(1, r+1):
        result *= inverse(i,p)
        result %= p
    return result

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
input = sys.stdin.readline
MOD = 10**9 + 7

def single_mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    if r > n - r:
        r = n - r
    ret = 1
    for i in range(r):
        ret *= n - i
        ret *= pow(i+1, MOD-2, MOD)
        ret %= MOD
    return ret

x, y = [int(item) for item in input().split()]
if (x + y) % 3 != 0:
    print(0)
    exit()
step = (x + y) // 3
x -= step; y -= step
if x < 0 or y < 0:
    print(0)
    exit()

print(single_mod_nCr(x+y, x))

Submission status: Accepted

Solution code:
class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

    def f(self, p, q):
        return self.fact[p + q] * self.factInv[p] * self.factInv[q] % MOD


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

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

time = (X + Y) // 3
ans = 0
comb = Combination(time + 10)

for y in range(time + 1):
    x = time - y

    if X == x * 2 + y and Y == y * 2 + x:
        ans += comb.f(x, y)
        ans %= MOD

print(ans % MOD)

Submission status: Accepted

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


# comb init
nmax = 10**6 + 1  # change here
fac = [0] * (nmax + 1)
finv = [0] * (nmax + 1)
inv = [0] * (nmax + 1)
fac[0] = 1
fac[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
for i in range(2, nmax):
    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 comb(n, r):
    if n < r:
        return 0
    else:
        return (fac[n] * ((finv[r] * finv[n - r]) % mod)) % mod


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

if x < y:
    x, y = y, x
if x > 2 * y:
    print(0)
    exit()

n = (x+y) // 3
r = y - n
print(comb(n, r))

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
MOD = 10**9+7
if (x+y)%3!=0:print(0);exit()
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
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
cnt=(x+y)//3
dif=abs(x-y)
ele=(cnt-dif)//2
print(comb_mod(cnt,ele))

Submission status: Accepted

Solution code:
x, y = [int(i) for i in input().split()]
if (x + y) % 3 != 0:
    print(0)
    exit()
z = (x + y) // 3
x -= z
y -= z

p = 10**9+7


def kai(x, p):
    a = 1
    for i in range(1, x + 1):
        a *= i
        a %= p
    return a


def comb(a, b, p):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= kai(a, p)
    c *= pow(kai(b, p), p - 2, p)
    c *= pow(kai(a - b, p), p - 2, p)
    return c % p


print(comb(x+y, x, p))

Submission status: Accepted

Solution code:
def comb(n,m,p=10**9+7):
    if n < m : return 0
    if n < 0 or m < 0:return 0
    m = min(m, n-m)
    top = bot = 1
    for i in range(m):
        top = top*(n-i) % p
        bot = bot*(i+1) % p
    bot = pow(bot, p-2, p)
    return top*bot % p

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

j = 2*x-y
if j%3:
    print(0)
    exit()
j //= 3
i = x - 2*j
if i<0 or j<0:
    print(0)
    exit()

ans = comb(i+j,i)
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    x,y = LI()
    n = x+y
    if n%3 != 0:
        print(0)
        return
    n //= 3
    ans = 1
    for i in range(max(x,y)-n):
        ans *= n-i
        ans %= mod
        ans *= pow(i+1,mod-2,mod)
        ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

def enumfif(n, mod):
    f = [0] * (n+1)
    invf = [0] * (n+1)
    f[0] = 1
    for i in range(1, n+1):
        f[i] = f[i-1] * i % mod
    a = f[n]
    b = mod
    p, q = 1, 0
    while b > 0:
        c = a//b
        d = a
        a = b
        b = d % b
        d = p
        p = q
        q = d - c * q
    invf[n] = p + mod if p < 0 else p
    for i in range(n-1,-1,-1):
        invf[i] = invf[i+1] * (i+1) % mod
    return [f, invf]

x, y = na()
mod = 1000000007
if (x+y) % 3 != 0:
    print(0)
else:
    # 2a+b = x
    # a+2b = y
    a = (2*x-y)//3
    b = (2*y-x)//3
    if a < 0 or b < 0:
        print(0)
    else:
        fif = enumfif(1500005, mod)
        print(fif[0][a+b] * fif[1][a] * fif[1][b] % mod)

Submission status: Accepted

Solution code:

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

mod = 10**9+7

class Combination:
    def __init__(self,N):
        self.fac = [1]*(N+1)
        for i in range(1,N+1):
            self.fac[i] = (self.fac[i-1]*i)%mod
        self.invmod = [1]*(N+1)
        self.invmod[N] = pow(self.fac[N],mod-2,mod)
        for i in range(N,0,-1):
            self.invmod[i-1] = (self.invmod[i]*i)%mod

    def calc(self,n,k):#nCk
        return self.fac[n]*self.invmod[k]%mod *self.invmod[n-k] %mod

X,Y = inpl()
X,Y = min(X,Y), max(X,Y)

A = X
B = Y - X

A -= B

if A < 0 or A%3 != 0:
    print(0)
else:
    C = Combination(10**6+10)
    a = A//3
    b = A//3 + B
    print(C.calc(a+b,a))

Submission status: Accepted

Solution code:

import sys
def input():
	return sys.stdin.readline().strip()


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

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

times = (X + Y) // 3

times2 = X - times


def fact(n, mod=1000000007):
	ans = 1
	for i in range(n):
		ans *= i + 1
		if mod != 0 and ans >= mod:
			ans = ans % mod
	return ans


def mod_rev(x, mod):

	return pow(x, mod - 2, mod)



def comb(a, b, mod=1000000007):
	"""
	関数mod_rev, fact, powが必要
	"""
	if a < b or b < 0:
		return 0
	if a == b or b == 0:
		return 1
	a_fact = fact(a, mod)
	b_fact = fact(b, mod)
	a_b_fact = fact(a - b, mod)
	if mod != 0:
		return (a_fact * mod_rev(b_fact, mod) * mod_rev(a_b_fact, mod))%mod
	else:
		return a_fact//(b_fact*a_b_fact)

mod = 10**9 + 7

print(comb(times, times2, mod))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
SIZE=1000000; MOD=10**9+7 #998244353 #ここを変更する

SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0

def chofuku(ball,box): # nHk mod MOD の計算
    return choose(box+ball-1,box)


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

#n = int(input())
#a = [int(i) for i in readline().split()]
x,y = [int(i) for i in readline().split()]


xx = x-2*y
yy = (-2)*x+y

ng = 0

if xx%3 != 0: ng = 1
if yy%3 != 0: ng = 1

xx //= 3 
yy //= 3
xx *= -1
yy *= -1

#print(ng,xx,yy)

if ng: print(0)
else: print(choose(xx+yy,xx)%MOD)

Submission status: Runtime Error

Solution code:
p = 1000000007
def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], p - 2, p) * pow(fac[k], p - 2, p) % p

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

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

if a.is_integer()==False or b.is_integer()==False:
    print(0)
else:
    n = a + b
    fac = [0] * (n + 1)
    fac[0] = 1
    for i in range(n):
        fac[i + 1] = fac[i] * (i + 1) % p
        print(mcomb(n, a))
#他者の解答を参考にした

Submission status: Runtime Error

Solution code:
import math
import numpy as np

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

a=(-X+2*Y)/3
b=(2*X-Y)/3
if a.is_integer()==False or b.is_integer()==False or a<0 or b<0:
    print(0)
else:
    print(cmb(int(N[0]+N[1]),int(N[0]),mod))

#他者の解答を参考にした

Submission status: Runtime Error

Solution code:
import math
import numpy as np

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

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

  b = np.array([x, y])

  N = np.linalg.solve(A, b)


X, Y = map(int,input().split())
a=(-X+2*Y)/3
b=(2*X-Y)/3
if a.is_integer()==False or b.is_integer()==False or a<0 or b<0:
    print(0)
else:
    print(cmb(int(N[0]+N[1]),int(N[0]),mod))

#他者の解答を参考にした

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(pow(10,9)+7)
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

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