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 make_inv_tables(mod, n):
    # 階乗テーブル逆元の階乗テーブルの2つを作成する

    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 cmb(n, k, mod, fac, ifac):
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod

X, Y = map(int, input().split())
total = int((X + Y) / 3)
n = X - total
if (X + Y) % 3 != 0:
    print(0)
elif X - total < 0 or Y - total < 0:
    print(0)
else:
    MOD = 10 **  9 + 7
    fac, ifac = make_inv_tables(MOD, total)
    ans = cmb(total, n, MOD, fac, ifac)
    print(ans)

Submission status: Accepted

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

if x<y:
  x,y=y,x
  
def cmb(n,r,p):
  if r<0 or n<r:
    return 0
  r=min(r,n-r)
  return fact[n]*factinv[r]*factinv[n-r]%p

p=10**9+7
N=10**6
fact=[1,1]
factinv=[1,1]
inv=[0,1]

for i in range(2,N+1):
  fact.append((fact[-1]*i)%p)
  inv.append((-inv[p%i]*(p//i))%p)
  factinv.append((factinv[-1]*inv[-1])%p)
  

if 2*y>=x and (x+y)%3==0:
  print(cmb((x+y)//3,(2*y-x)//3,p))
else:
  print(0)

Submission status: Accepted

Solution code:
# solution
import io
import math

MOD = 10 ** 9 + 7

nim, mike = map(int, input().split())

m = 2 * nim - mike
n = 2 * mike - nim

if m % 3 or n % 3 or m < 0 or n < 0:
    print(0)
    quit()

m //= 3
n //= 3

factorial = [1] * (n + m + 1)
for i in range(n + m):
    factorial[i + 1] = factorial[i] * (i + 1) % MOD

print(factorial[m + n] * pow(factorial[m], MOD - 2, MOD) * pow(factorial[n], MOD - 2, MOD) % MOD)

Submission status: Accepted

Solution code:
def power(x, a):
    if a == 0:
        return 1
    elif a == 1:
        return x
    elif a % 2 == 0:
        return power(x, a//2) **2 % mod
    else:
        return power(x, a//2) **2 * x % mod


def modinv(x):
    return power(x, mod-2)

def binomial_coefficients(n, k):
    numera = 1  
    denomi = 1  

    for i in range(k):
        numera *= n-i
        numera %= mod
        denomi *= i+1
        denomi %= mod
    return numera * modinv(denomi) % mod

X,Y=map(int,input().split())
mod=10**9 + 7
if Y<=2*X and Y>=0.5*X and (X+Y)%3==0:
  print(binomial_coefficients((X+Y)//3,((X+Y)//3)*2-X))
else:
  print(0)

Submission status: Accepted

Solution code:
def C(n, r, m):
    num, den = 1, 1
    for i in range(1, r + 1):
        num = num * (n - i + 1) % m
        den = den * i % m
    return (num * pow(den, m - 2, m)) % m

x, y = map(int, input().split())
m = (2*x - y) // 3
n = (-x + 2*y) // 3
if (x + y) % 3 != 0 or m < 0 or n < 0:
    print(0)
else:
    print(C(n + m, n, 10**9 + 7))

Submission status: Accepted

Solution code:
X, Y = map(int, input().split(" "))
mod = 10 ** 9 + 7
if (2 * Y - X) % 3 == 0 and (2 * X - Y) % 3 == 0:
    n, m = (2 * Y - X) // 3, (2 * X - Y) // 3
    if n < 0 or m < 0:
        print(0)
    else:
        fact = [1, 1]
        inv = [1, 1]
        inv_fact = [1, 1]
        for i in range(2, n + m + 1):
            fact.append((fact[-1] * i) % mod)
            inv.append(mod - inv[mod % i] * (mod // i) % mod)
            inv_fact.append((inv_fact[-1] * inv[-1]) % mod)
        ans = fact[n + m] * inv_fact[n] * inv_fact[m]
        print(ans % mod)
else:
    print(0)

Submission status: Accepted

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

if (2*x-y)%3!=0 or (2*x-y)<0:
  print(0)
  exit()
if (2*y-x)%3!=0 or (2*y-x)<0:
  print(0)
  exit()
p=int((2*x-y)/3)
q=int((2*y-x)/3)
M=p+q+2
Mod=10**9+7

fac=[0]*M
finv=[0]*M
inv=[0]*M

def COMinit():
  fac[0]=fac[1]=1
  finv[0]=finv[1]=1
  inv[1]=1
  for i in range(2,M):
    fac[i]=(fac[i-1]*i%Mod)%Mod
    inv[i]=Mod-inv[Mod%i]*(Mod//i) %Mod
    finv[i]=(finv[i-1]*inv[i]%Mod)%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)%Mod

COMinit()
print(COM(p+q,p))

Submission status: Accepted

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

if (2*x-y)%3!=0 or (2*x-y)<0:
  print(0)
  exit()
if (2*y-x)%3!=0 or (2*y-x)<0:
  print(0)
  exit()
p=int((2*x-y)/3)
q=int((2*y-x)/3)
M=p+q+2
Mod=10**9+7

fac=[0]*M
finv=[0]*M
inv=[0]*M

def COMinit():
  fac[0]=fac[1]=1
  finv[0]=finv[1]=1
  inv[1]=1
  for i in range(2,M):
    fac[i]=(fac[i-1]*i%Mod)%Mod
    inv[i]=Mod-inv[Mod%i]*(Mod//i) %Mod
    finv[i]=(finv[i-1]*inv[i]%Mod)%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)%Mod

COMinit()
print(COM(p+q,p))

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

Submission status: Accepted

Solution code:
import math
import copy
x,y = map(int, input().split())
m = 1000000007

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


step = (x+y)//3

step_x = (step+abs(x-y))//2
step_y = (step-abs(x-y))//2

if (step_y<0):
    print(0)
    exit()
    
def com(n,r,m):
    #a = math.factorial(n)%m
    a = 1
    for i in range(1,n+1):
        a *= i
        a %= m
    A = pow(a,m-2,m)
    
    
    b= copy.deepcopy(A)   
    for i in range(n,r,-1):
        b = (b*i)%m
    
    c = copy.deepcopy(A)
    for i in range(n,n-r,-1):
        c = (c*i)%m
       
    return (a*b*c)%m
    
    
print(int(com(step_x+step_y,step_x,m)))

Submission status: Accepted

Solution code:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
p = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

def main():

    def combination(n, r, p):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return fact[n] * factinv[r] * factinv[n-r] % p

    N = 10 ** 6  # N は必要分だけ用意する
    fact = [1, 1]  # fact[n] = (n! mod p)
    factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
    inv = [0, 1]  # factinv 計算用
    
    for i in range(2, N + 1):
        fact.append((fact[-1] * i) % p)
        inv.append((-inv[p % i] * (p // i)) % p)
        factinv.append((factinv[-1] * inv[-1]) % p)

    x, y = nm()

    if (x + y) % 3 != 0:
        print(0)
        exit()
    
    n = (2*y - x) // 3 # (X, Y) -> (X+1, Y+2) 
    m = (2*x - y) // 3 # (X, Y) -> (X+2, Y+1) 

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

    print(combination(n+m, n, p))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
p = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

def main():

    def combination(n, r, p):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return fact[n] * factinv[r] * factinv[n-r] % p

    N = 10 ** 6  # N は必要分だけ用意する
    fact = [1, 1]  # fact[n] = (n! mod p)
    factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
    inv = [0, 1]  # factinv 計算用
    
    for i in range(2, N + 1):
        fact.append((fact[-1] * i) % p)
        inv.append((-inv[p % i] * (p // i)) % p)
        factinv.append((factinv[-1] * inv[-1]) % p)

    x, y = nm()

    if (x + y) % 3 != 0:
        print(0)
        exit()
    
    n = (2*y - x) // 3 # (X, Y) -> (X+1, Y+2) 
    m = (2*x - y) // 3 # (X, Y) -> (X+2, Y+1) 

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

    print(combination(n+m, n, p))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))


def fur(n,r):
    p,q = 1,1
    for i in range(r):
        p = p*(n-i)%mod
        q = q*(i+1)%mod
    return p * pow(q,mod-2,mod) % mod

x, y = nm()

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

n = (2*y - x) // 3 # (X, Y) -> (X+1, Y+2) 
m = (2*x - y) // 3 # (X, Y) -> (X+2, Y+1) 

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

print(fur(n+m, n))

Submission status: Accepted

Solution code:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

def main():

    def fur(n,r):
        p,q = 1,1
        for i in range(r):
            p = p*(n-i)%mod
            q = q*(i+1)%mod
        return p * pow(q,mod-2,mod) % mod

    x, y = nm()

    if (x + y) % 3 != 0:
        print(0)
        exit()
    
    n = (2*y - x) // 3 # (X, Y) -> (X+1, Y+2) 
    m = (2*x - y) // 3 # (X, Y) -> (X+2, Y+1) 

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

    print(fur(n+m, n))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)

    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())
# 後の、n, mの大小を一定にするため
if X > Y:
    X, Y = Y, X
dist = X + Y

if dist % 3 != 0:
    print(0)
else:
    # (+1,+2) の移動の回数を n、(+2,+1) の移動の回数を m とする)
    # total = n + m
    # 以下の式は、2n + m = X, n + 2m = Y の連立方程式を解いた結果
    total = int((X+Y) / 3)
    n = X - total

    # n < 0 もしくは m < 0 の場合、たどり着けない
    # Y > X なので、m > n
    # n < 0 → 2X - Y < 0
    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)

Submission status: Accepted

Solution code:
def comb(n,k,mod):
    x = y = 1
    for i in range(min(k,n-k)):
        x = x*(n-i)%mod
        y = y*(i+1)%mod
    return x * pow(y, mod-2, mod) % mod

x,y = map(int,input().split())
ans = 0
mod = 10**9+7
if (x+y)%3 == 0:
    a = (-x+2*y)//3
    b = (2*x-y)//3
    if a >= 0 and b >= 0: ans = comb(a+b,a,mod)
print(ans)

Submission status: Accepted

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

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


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

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

elif a<0 or b<0:
    ans = 0

else:
    ans = cmb(int(a + b), int(a), 10**9 + 7)

print(ans)

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
if (2*x-y)%3!=0 or (x-2*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()
mod=10**9+7
def comb(x,y):
    s=1
    t=1
    for i in range(1,y+1):
        s=s*(x-i+1)%mod
        t=t*(i)%mod
    return (s*pow(t,mod-2,mod))%mod
print(comb(a+b,min(a,b)))

Submission status: Accepted

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

class Combination(): # nCr mod MOD など
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(10**6)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.fac, self.facinv = self.prepare(n_max)
        #self.modinv = self.make_modinv_list(n_max) ##なくても問題ないので、必要な時のみ使う
        
    def prepare(self,n): # 前処理(コンストラクタで自動的に実行)
        # 1! ~ n! の計算
        factorials = [1]  # 0!の分
        for m in range(1, n+1):
            factorials.append(factorials[m-1]*m%self.mod)
        # n!^-1 ~ 1!^-1 の計算
        invs = [1] * (n+1)
        invs[n] = pow(factorials[n], self.mod-2, self.mod)
        for m in range(n, 1, -1):
            invs[m-1] = invs[m]*m%self.mod
        return factorials, invs # list
    
    def make_modinv_list(self, n): # 0からnまでのmod逆元のリストを返す O(n)
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            # 整数aのMを法とした時の逆元a^-1は、(0<=a<=M-1)
            # a == qM+rであるとき(qは商,rは余り)、
            # a^-1 == -qr^-1 % M で与えられる。
            modinv[i] = (self.mod - self.mod//i)*modinv[self.mod%i]  % self.mod
        return modinv

    def perm_mod(self,n,r): # nPr % self.mod
        if n < r:
            return 0
        if (n < 0 or r < 0):
            return 0
        return (self.fac[n] * self.facinv[n-r]) % self.mod

    def combi_mod(self,n,r): # nCr % self.mod
        if n < r:
            return 0
        if (n < 0 or r < 0):
            return 0
        return (((self.fac[n] * self.facinv[r]) % self.mod) * self.facinv[n-r]) % self.mod


if (X+Y)%3==0:
    d = (X+Y)//3
    if d<=X<=X+Y-d and d<=Y<=X+Y-d:
        C = Combination(d+1)
        print(C.combi_mod(d,abs(d-X)))
    else:
        print(0)
else:
    print(0)

Submission status: Accepted

Solution code:
X, Y = map(int, input().split())
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] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)
 
    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
if (X + Y) % 3 != 0:
    print(0)
    quit()
n = (2 * Y - X) // 3
m = (2 * X - Y) // 3
if n < 0 or m < 0:
    print(0)
    quit()
mod = 10 ** 9 + 7
fac, ifac = make_tables(mod, n + m)
print(cmb(n + m, n, mod, fac, ifac))

Submission status: Accepted

Solution code:
import math
import sys

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])
			result %= MOD

	return result

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

min_xy = min(x,y)
max_xy = max(x,y)

MOD = 10**9+7

if max_xy / min_xy == 2.0:
	print(1)
	sys.exit()
if max_xy / min_xy > 2.0:
	print(0)
	sys.exit()
if max_xy == min_xy and max_xy % 3 != 0:
	print(0)
	sys.exit()
if max_xy == min_xy and max_xy % 3 == 0:
	print(cmb(2 * max_xy//3, max_xy//3))
	sys.exit()

for i in range(min_xy//3+1):
	if (max_xy-3*i) / (min_xy-3*i) == 2.0:
		print(cmb(2*i + (min_xy-3*i),i)%MOD)
		sys.exit()

print(0)

Submission status: Accepted

Solution code:
X, Y = map(int, input().split())
if (X + Y) % 3 != 0:
    print(0)
    quit()
n = (2 * Y - X) // 3
m = (2 * X - Y) // 3
if n < 0 or m < 0:
    print(0)
    quit()
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
print(cmb(n + m, n, p))

Submission status: Accepted

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

def solve():
    at = 2*x - y
    bt = 2*y - x
    if at < 0 or bt < 0 or at % 3 != 0 or bt %3 != 0:
        return 0
    a = at // 3
    b = bt // 3
    num = den = 1
    for i in range(max(a, b)+1, (a+b)+1):
        num = num * i % M
    for i in range(2, min(a, b)+1):
        den = den * i % M
    inv_den = pow(den, M-2, M)
    return num * inv_den % M

print(solve())

Submission status: Accepted

Solution code:
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] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)

    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())
dist = X + Y
if dist % 3 != 0:
    print(0)
    quit()
n = int((2 * X - Y) / 3)
m = int((2 * Y - X) / 3)
if n < 0 or m < 0:
    print(0)
    quit()
mod = 10 ** 9 + 7
fac, ifac = make_tables(mod, n + m)
ans = cmb(n + m, m, mod, fac, ifac)
print(ans)

Submission status: Accepted

Solution code:
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] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)

    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)
    quit()
n = int((2 * X - Y) / 3)
m = int((2 * Y - X) / 3)
if n < 0 or m < 0:
    print(0)
    quit()
mod = 10 ** 9 + 7
fac, ifac = make_tables(mod, n + m)
ans = cmb(n + m, m, mod, fac, ifac)
print(ans)

Submission status: Accepted

Solution code:
mod = 10**9 + 7

fact_range = 10**6
facts = [1] * (fact_range + 1)
for i in range(0, fact_range):
    facts[i+1] = facts[i] * (i + 1) % mod

ifacts = [1] * (fact_range + 1)
ifacts[fact_range] = pow(facts[fact_range], mod - 2, mod)
for i in range(fact_range, 0, -1):
    ifacts[i-1] = ifacts[i] * i % mod

def comb(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return facts[n] * ifacts[n-k] % mod * ifacts[k] % mod

x, y = map(int, input().split())
if (x + y) % 3:
    print(0)
else:
    n = (x + y) // 3
    k = x - n
    print(comb(n, k))

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
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
  
if (x+y)/3 != int((x+y)/3):
    print(0)
elif (y<int((x+y)/3)) or (x<int((x+y)/3)):
    print(0)
else:
    print(comb(int((x+y)/3), int(y-((x+y)/3)),10**9+7))

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
m = 10**9+7
if not((x+y)%3== 0 and abs(x-y)<=(x+y)//3):
    print(0);exit()

def comb(n,k):
    #if 2 * k > n:
        #k = n - k
    a = 1
    for i in range(1,k+1):
        a *= (n - ( i - 1)) * pow(i,m-2,m)
        a = a%m
    return a

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

Submission status: Accepted

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

mod = 10**9 + 7 

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

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

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+1
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,a,mod))

Submission status: Accepted

Solution code:
X,Y=map(int,input().split())
if 2*Y<X or 2*X<Y or not((2*Y-X)%3==0) or not((2*X-Y)%3==0):
  print(0)
else:
  A=(2*Y-X)//3
  B=(2*X-Y)//3
  k=1
  for i in range(A+1,A+B+1):
    k=(k*i)%1000000007
  j=1
  for i in range(1,B+1):
    j=(j*i)%1000000007
  l=(pow(j,1000000005,1000000007)*k)%1000000007
  print(l)

Submission status: Accepted

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

mod=10**9+7

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

def enumfactorial(x):
    ret=1
    for i in range(1,x+1):
        ret*=i
        ret%=mod
    
    return ret

def denomfactorial(x):
    ret=1
    for i in range(1,x+1):
        ret*=modinv(i)
        ret%=mod
    
    return ret

if (2*Y-X)%3>0 or (2*X-Y)%3>0:
    print(0)
else:
    m=(2*Y-X)//3
    n=(2*X-Y)//3

    if m<0 or n<0:
        print(0)
    else:
        print((enumfactorial(m+n)*denomfactorial(m)*denomfactorial(n))%mod)

Submission status: Accepted

Solution code:
P = 10**9 + 7
N = 700000 #使う最大値以上にする、値に注意4*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
finv = [1] + [1] # 1/x!
fac = [1] + [1] # x!
for i in range(2,N+1):
  inv += [inv[P % i] * (P - int(P / i)) % P]
  fac += [(fac[i-1] * i) % P]
  finv += [(finv[i-1] * inv[i]) % P]

def comb(a, b):
    if a<b: return 0 # error
    return (fac[a] * ((finv[b] * finv[a-b]) % P)) %P
x, y = map(int, input().split())
if (2*y-x)%3!=0 or (2*x - y)%3!=0:
    print(0)
    exit(0)
A = (2*y-x)//3
B = (2*x-y)//3
if A<0 or B<0:
    print(0)
    exit(0)
print(comb(A+B, A))

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
def cal(number,mod):
    m=mod-2
    mod2=""
    while m!=0:
        if m%2==0:
            mod2="0"+mod2
        else:
            mod2="1"+mod2
        m=m//2
    two=[]
    for i in range(len(mod2)):
        if mod2[len(mod2)-1-i]=="1":
            two.append(i)
    ret=1
    for i in two:
        v=i
        retsub=number
        while v>0:
            retsub=retsub**2
            retsub=retsub%mod
            v-=1
        ret*=retsub
    ret=ret%mod
    return ret
ans=0
M=10**9+7
if (2*x-y)%3==0:
    n=(x+y)//3
    r=(2*x-y)//3
    if n<r or r<0:
        print(0)
        exit()
    l=[1]
    num=1
    for i in range(1,n+1):
        p=(num*i)%(M)
        l.append(p)
        num=p
    a=l[n]
    b=cal(l[n-r],M)
    c=cal(l[r],M)
    ans=(a*b*c)%M
print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools

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

#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

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

if(X<Y):
  X, Y = Y, X

XY = X-Y

if((X - 2*XY)%3 == 0 and (Y-XY)%3 == 0):
  XX = XY+(X- 2*XY)//3
  YY = (X-2*XY)//3
  #print(XX,YY)
  if(YY==0):
    print(1)
  else:
    ans = comb(XX+YY, XX, mod)
    print(ans%mod)
else:
  print(0)

Submission status: Accepted

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

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

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