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:
X, Y = list(map(int, input().strip().split()))

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

if X>0 and Y>0 and (2*X - Y)%3 == 0 and (2*Y - X)% 3==0 and 2*Y >= X and Y <= 2*X: 
    m = int((2*X - Y)/ 3)
    n = int((2*Y - X)/ 3)
    
    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル
    for i in range( 2, m+n + 1 ):
        g1.append( ( g1[-1] * i ) % mod )
        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )
    ret = cmb(m+n, m, mod)
else:
    ret = 0
print(ret)

Submission status: Accepted

Solution code:
#coding:utf-8
import bisect
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True



def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    x, y = LMIIS()

    if (x+y)%3!=0:
      print(0)
      exit()
    n = (x+y)//3
    if 0 > x-n or 0 > y-n:
      print(0)
      exit()

    m = min(x-n,y-n)
    mod = 10**9 + 7

    a = 1
    b = 1
    for i in range(n - m + 1, n+1):
        a = a * i % mod
    for i in range(1, m + 1):
        b = b * i % mod
    print(a * pow(b, mod - 2, mod) % mod)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#coding:utf-8
import bisect
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True


def com(a, b, p):
    if a < b or a < 0 or b < 0:
        return 0
    fac = [1]*(a+1)
    inv = [1]*(a+1)
    finv = [1]*(a+1)

    for i in range(2, a+1):
        fac[i] = fac[i-1] * i % p
        inv[i] = p - (inv[p%i] * (p//i) )% p
        finv[i] = finv[i-1] * inv[i] % p

    return fac[a] * (finv[b] * finv[a - b] % p) % p


def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    x, y = LMIIS()

    if (x+y)%3!=0:
      print(0)
      exit()
    n = (x+y)//3
    if 0 > x-n or 0 > y-n:
      print(0)
      exit()

    m = min(x-n,y-n)
    mod = 10**9 + 7

    print(com(n, m, mod))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#coding:utf-8
import bisect
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True



def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    x, y = LMIIS()

    if (x+y)%3!=0:
      print(0)
      exit()
    n = (x+y)//3
    if 0 > x-n or 0 > y-n:
      print(0)
      exit()

    m = min(x-n,y-n)
    mod = 10**9 + 7

    a = 1
    b = 1
    c = 1
    for i in range(1, n+1):
        a = a * i % mod
    for i in range(1, n - m + 1):
        b = b * i % mod
    for i in range(1, m + 1):
        c = c * i % mod
    print(a * pow(b * c, mod - 2, mod) % mod)




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

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

mod = 10**9+7 #出力の制限
g1 = [1]*(x+y) # 元テーブル
g2 = [1]*(x+y) #逆元テーブル
inverse = [1]*(x+y)
inverse[0] = 1

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

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 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
x,y = map(int,input().split())
mod = 10**9+7
if (x+y) % 3 != 0:
  print(0)
elif abs(y-x) > min(x,y)*2:
  print(0)
else:
  print(cmb((y+x) // 3,(2*y-x) // 3,mod))

Submission status: Accepted

Solution code:
import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

MOD = 10**9 + 7


def cumprod(arr, MOD):
    L = len(arr)
    Lsq = int(L**.5 + 1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n - 1]
        arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n - 1, -1]
        arr[n] %= MOD
    return arr.ravel()[:L]


def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64)
    x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64)
    x[0] = pow(int(fact[-1]), MOD - 2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv


U = 10**6
fact, fact_inv = make_fact(U, MOD)

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

answer = fact[a + b] * fact_inv[a] % MOD * fact_inv[b] % MOD
print(answer)

Submission status: Accepted

Solution code:
# Thanks <3 https://qiita.com/derodero24/items/91b6468e66923a87f39f#%E7%95%AA%E5%A4%96%E7%B7%A8
def cmb(n, r, mod):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % mod


mod = 10 ** 9 + 7  # 出力の制限
N = 10 ** 6
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

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


x, y = map(int, input().split())
if (x + y) % 3 != 0:
    print(0)
    exit()

# n = (i + 1, j + 2) / m = (i + 2, j + 1)
n = int((2 * y - x) / 3)
m = int((2 * x - y) / 3)
print(cmb(n + m, m, mod))

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
X, Y = [int(_) for _ in input().split()]

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


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

kaijo = [0] * (X + Y + 10)
gyaku = [0] * (X + Y + 10)

kaijo[0] = 1
kaijo[1] = 1
MOD = 10 ** 9 + 7
for i in range(2, len(kaijo)):
    kaijo[i] = (i * kaijo[i - 1]) % MOD
gyaku[0] = 1
gyaku[1] = 1
for i in range(2, len(gyaku)):
    gyaku[i] = pow(kaijo[i], MOD - 2, MOD)


def nCm(n, m):
    return (kaijo[n] * gyaku[n - m] * gyaku[m]) % MOD


print(nCm(x + y, x))

Submission status: Accepted

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect
import functools

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in sys.stdin.readline().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v

def comb(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 bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

# --------------------------------------------

dp = None


def main():
    x, y = li_input()

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

    n = 0
    m1, m2 = 0, 0
    while x != 0 and y != 0:
        n += 1
        if x >= y:
            x -= 2
            y -= 1
            m1 += 1
        else:
            x -= 1
            y -= 2
            m2 += 1

    if not (x == 0 and y == 0):
        print(0)
        return(0)

    print(comb(n, m1) % (10 ** 9 + 7))


main()

Submission status: Accepted

Solution code:
x, y = [int(i) for i in input().split()]

mod = 10 ** 9 + 7
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

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


# 以下のcom関数を用いて組み合わせを計算
def com(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 (2*x-y) % 3 == 0 and (2*y-x) % 3 == 0:
    a = (2*x-y) // 3
    b = (2*y-x) // 3
    #a+bC(min(a,b))
    ans = 0
    n = a + b
    r = min(a, b)
    print(com(n, r, mod))

else:
    print(0)

Submission status: Accepted

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

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]

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

Submission status: Accepted

Solution code:
import math
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()) 
mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

if (X+Y)%3!=0:
  print(0)
else:
  N=(X+Y)//3
  if X>=N and Y>=N:
    a=X-N
    b=Y-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 )

    C = cmb(a+b,a,mod)
    print(C)
  else:
    print(0)

Submission status: Accepted

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

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    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

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

if y > 2 * x or y < x / 2:
    print(0)
    sys.exit()

cnt = (x + y) // 3
# p = cnt // 2
p = (2 * x - y) // 3
#print(cnt, p)

# Calclate cntCp
comb = Combination(1000000)
ans = comb(cnt, p)

print(ans)

Submission status: Accepted

Solution code:
from math import factorial as f
p = int(1e9+7)
X, Y = map(int, input().split())
n = (2 * X - Y) // 3
m = (2 * Y - X) // 3
if(n < 0 or m < 0 or (X + Y) % 3 > 0):
  print(0)
else:
  fac = [0] * (n+m+1)
  inv = [0] * (n+m+1)
  finv = [0] * (n+m+1)

  fac[0] = fac[1] = 1
  inv[1] = 1
  finv[0] = finv[1] = 1
  
  for i in range(2,n+m+1):
    fac[i] = fac[i-1] * i % p
    inv[i] = p - inv[p%i] * (p // i) % p
    finv[i] = finv[i-1] * inv[i] % p

  print(fac[n+m] * finv[n] * finv[m] % p)

Submission status: Accepted

Solution code:
mod=1000000007
fact=[None for i in range(1000000)]
fact[0]=1
for i in range(1,1000000):
  fact[i]=fact[i-1]*i
  fact[i]%=mod

def inv(x):
  n = mod-2
  ans = 1
  while n!=0:
    if n&1:
      ans = ans*x % mod
    x = x*x % mod
    n //= 2
  return ans
 
def comb(n,r):
  return (fact[n]*inv(fact[r])*inv(fact[n-r]))%mod

a,b=map(int,input().split())
j=None
for i in range(1000000):
  j=b-i*2
  if j<0:
    break
  if i+j*2==a:
    print(comb(i+j, i))
    break
if j<0:
  print(0)

Submission status: Accepted

Solution code:
import sys
import math
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]
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

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 = na()
# a = (-1/3) * x + (2/3) * y
# b = (2/3) * x - (1/3) * y

if ((x+y) % 3) == 0:
    i = (x+y)//3
    print(cmb(i,x-i, mod))
else:
    print(0)

Submission status: Accepted

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


def modconb(n,k,mod):
    # テーブルを作る
    fac = [0]*(n+1)
    finv = [0]*(n+1)
    inv = [0]*(n+1)  

    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2,n+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
    # 計算
    if n<k: return 0
    if n<0 or k<0: return 0
    return(fac[n]*(finv[k]*finv[n-k]%mod)%mod)
    
mod = 10**9 + 7 
if (x+y) % 3 != 0:
    print(0)
    exit()
i = (x+y)//3
j = (x-i)
print(modconb(i,j,mod))

Submission status: Accepted

Solution code:
import math
M = 10**9+7
X,Y = map(int,input().split())
if (X+Y)/3 != (X+Y)//3:
    print(0)
    exit()
n = (X+Y)//3
r = Y-n
if r<0 or r>n:
    print(0)
    exit()


#nCr and Mod
def nCr(n, r, 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(n,r,M))

Submission status: Accepted

Solution code:
def nCr(n, r, 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


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

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

# 以下の連立方程式を解いて、代入
# n + 2m  = X
# 2n+ m = Y
# (n+m)Cn
print(nCr((x + y)//3, (-x+2*y)//3))

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

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

if (2*y-x)%3==0:
    a=(2*y-x)//3
    b=(2*x-y)//3
    mod = 10**9+7 #出力の制限
    N = a+b
    r=min(a,b)
    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(N,r,mod))
else:
    print(0)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def modpow(a, b, mod):
    ret = 1
    while b > 0:
        if b % 2 == 1:
            ret = ret * a % mod
        a = a * a % mod
        b //= 2
    return ret


X, Y = map(int, input().split())
if (2 * X - Y) % 3 != 0 or (2 * Y - X) % 3 != 0:
    print(0)
elif (2 * X - Y) // 3 < 0 or (2 * Y - X) // 3 < 0:
    print(0)
else:
    A, B = (2 * X - Y) // 3, (2 * Y - X) // 3
    ans = 1
    for n in range(A + B, A, -1):
        ans = ans * n % MOD
    for n in range(1, B + 1):
        ans = ans * modpow(n, MOD - 2, MOD) % MOD
    print(ans % MOD)

Submission status: Accepted

Solution code:
def combnk_mod(n, k, p):
    # pが素数かつaとpが互いに素であるとき
    # フェルマーの小定理より以下が成り立つ.
    # 1 / a = a ** (p - 2) (mod p)
    # これを使って (1 / k!) mod p を計算する.

    if  2 * k > n:
        k = n - k
    x = 1 # 分母にあたる数 1 / n! mod p
    y = 1 # 分子にあたる数. n! / (n - k)! mod p
    for i in range(1, k + 1):
        x *= pow(i, p - 2, p)
        y *= n - i + 1
        x %= p
        y %= p
    return (x * y) % p

MOD = 10 ** 9 + 7
x, y = map(int, input().split())
m = 2 * x - y
n = 2 * y - x
if m < 0 or n < 0:
    ans = 0
elif m % 3 > 0 or n % 3 > 0:
    ans = 0
else:
    m = m // 3
    n = n // 3
    ans = combnk_mod(m + n, min(m, n), MOD)
print(ans)

Submission status: Accepted

Solution code:
def combnk_mod(n, k, p):
    # pが素数かつaとpが互いに素であるとき
    # フェルマーの小定理より以下が成り立つ.
    # 1 / a = a ** (p - 2) (mod p)
    # これを使って (1 / k!) mod p を計算する.

    if  2 * k > n:
        k = n - k
    x = 1 # 分母にあたる数 1 / n! mod p
    y = 1 # 分子にあたる数. n! / (n - k)! mod p
    for i in range(1, k + 1):
        x *= pow(i, p - 2, p)
        y *= n - i + 1
        x %= p
        y %= p
    return (x * y) % p

MOD = 10 ** 9 + 7
x, y = map(int, input().split())
m = 2 * x - y
n = 2 * y - x
if m < 0 or n < 0:
    ans = 0
elif m % 3 > 0 or n % 3 > 0:
    ans = 0
else:
    m = (2 * x - y) // 3
    n = (2 * y - x) // 3
    ans = combnk_mod(m + n, min(m, n), 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())

b = max(x, y)
s = min(x, y)

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

ans = 0
if (x+y) % 3 != 0 or b / s > 2:
    print(ans)
else:
    print(cmb(n+m, n) % (10 ** 9 + 7) )

Submission status: Accepted

Solution code:
from sys import stdin


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


def main():
    X, Y = [int(x) for x in stdin.readline().rstrip().split()]
    if (X + Y) % 3:
        print(0)
    else:
        m = (2 * X - Y) // 3
        n = X - 2 * m
        if n < 0 or m < 0:
            print(0)
        else:
            ans = cmb(n + m, min(n, m))
            print(ans % (10 ** 9 + 7))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin

MAX = 10 ** 6
MOD = 10 ** 9 + 7
fac = [0] * MAX
finv = fac[:]
inv = fac[:]


def cmb_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD


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


def main():
    X, Y = [int(x) for x in stdin.readline().rstrip().split()]
    if (X + Y) % 3:
        print(0)
    else:
        m = (2 * X - Y) // 3
        n = X - 2 * m
        if n < 0 or m < 0:
            print(0)
        else:
            cmb_init()
            ans = cmb(n + m, min(n, m))
            print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import functools

law = 10 ** 9 + 7
def mul_mod(x, y):
  return x * y % law

def prod_mod(seq):
  return functools.reduce(mul_mod, seq, 1)
#互いに素なa,bについて、a*x+b*y=1の一つの解
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
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m
  
def comb(n, k):
  return prod_mod(i for i in range(n - k + 1, n + 1)) * mod_inv(prod_mod(i for i in range(1, k + 1)), law) % law

if __name__ == "__main__":
  
  x, y = sorted(map(int, input().split()), reverse=True)
  
  if (x + y) % 3 != 0:
    print(0)
  else:
    print(comb((x + y) // 3, x - (x + y) // 3))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math

MOD = 10**9+7  # type: int

def combi_count(n, r):
    x = 1
    y = 1
    for i in range(1, r+1):
        x = x * (n-i) % MOD
        y = y * i % MOD

    # nCr = n!/((n-r)!*r!) = (n!/(n-r)!) / r! 
    #     :=                 (    x    ) / y

    # x / y            % MOD
    # x * y^(-1)       % MOD
    # x * y**(MOD - 2) % MOD (from フェルマー定理)

    return x * pow(y, MOD-2, MOD) % MOD

def solve(X: int, Y: int):
    a = int((2*Y - X)/3)
    b = int((2*X - Y)/3)
    if ( ((2*Y - X)%3 != 0) and ((2*X - Y)%3 != 0) )  or ((a<0) or (b<0)):
        ans = 0
    else:
        ans = combi_count(a+b+1, min(a, b))
    print(ans)

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    X, Y = map(int, input().split())
    solve(X, Y)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np
mod = 10**9+7
X, Y = [int(x) for x in stdin.readline().rstrip().split()]


def mul(a, b):
    return ((a % mod) * (b % mod)) % mod


def div(a, b):
    return mul(a, pow(b, mod-2, mod))


def fact(n):
    f = 1
    for i in range(1, n+1):
        f *= i
        f %= mod
    return f


A = np.matrix([[2, 1], [1, 2]])
Y = np.matrix([[X], [Y]])
if np.linalg.matrix_rank(np.c_[A, Y]) == np.linalg.matrix_rank(A):
    x, y = np.linalg.solve(A, Y)
    x = float(x)
    y = float(y)
    if x < 0 or y < 0:
        print(0)
    elif (not x.is_integer()) or (not y.is_integer()):
        print(0)
    else:
        x = int(x)
        y = int(y)
        ans = fact(x+y)
        ans = div(ans, fact(x))
        ans = div(ans, fact(y))
        print(ans % mod)
else:
    print(0)

Submission status: Accepted

Solution code:
sosu = 10 ** 9 + 7
X, Y = map(int, input().split())
amari = (X + Y) % 3
sho = (X + Y) // 3
x = 2 * sho - X
if amari == 0 and x >= 0 and x <= sho:
    fac = [1 for i in range(sho+1)]
    finv = [1 for i in range(sho+1)]
    inv = [1 for i in range(sho+1)]
    for i in range(2, sho+1):
        fac[i] = fac[i-1] * i % sosu
        inv[i] = sosu - inv[sosu%i] * (sosu//i) % sosu
        finv[i] = finv[i-1] * inv[i] % sosu
    #print(fac)
    #print(finv)
    ans = int(fac[sho] * (finv[x] * finv[sho-x] % sosu) % sosu)
else:
    ans = 0
print(ans)

Submission status: Accepted

Solution code:
X,Y=map(int, input().split())
if (X+Y)%3!=0:
  print(0)
  exit()
n=(X+Y)//3
flg=True
for i in range(n+1):
  if 2*i +(n-i) == X:
    right=i
    up=n-i
    flg=False
    break
  elif 2*(n-i)+i == X:
    up=i
    right=n-i
    flg=False
    break
if flg:
  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 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

a = cmb(n,right,mod)
print(a)

Submission status: Accepted

Solution code:
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

import itertools

X, Y = two_int()

def comb(n,r,mod, N):
    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] #逆元テーブル計算用テーブル

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

def calc(a, b, p):
    if b==0:
        return 1
    elif b%2==0:
        d=calc(a,b//2, p)
        return (d*d)%p
    else:
        return (a*calc(a,b-1,p))%p

dan = (X+Y)/3
if dan.is_integer():
    n = int(dan+1)
    k = Y-(n-1)+1
    print(int(comb(n-1,k-1,(10**9+7),X)))
else:
    print(0)

Submission status: Accepted

Solution code:
X, Y = map(int, input().split())
M = 10**9+7
if (X + Y) % 3:
    print(0)
else:
    m = (2 * X - Y)//3
    n = (2 * Y - X)//3
    if m < 0 or n < 0:
        print(0)
    else:
        a = 1
        for i in range(1, n+m+1):
            a =  a * i % M
        b = 1
        for i in range(1, n+1):
            b = b * i % M
        c = 1
        for i in range(1, m+1):
            c = c * i % M
        print(a * pow(b, M-2, M) * pow(c, M-2, M) % M)

Submission status: Accepted

Solution code:
#import heapq
import itertools
import math
#import numpy as np
import sys

def modc(a, b, m):
    c = 1
    for i in range(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1, m) % m
    return c

def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m

#N = int(input())
X, Y = list(map(int, input().split()))
#S = [input() for _ in range(H)]
#T = [list(map(int,input().split())) for _ in range(N)]
#sys.exit()

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

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

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

ans = modc(n + m, n, 10 ** 9 + 7)
print(ans)

Submission status: Accepted

Solution code:
import math

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

comb_list = {}
mod_param = 10**9 + 7

def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

# ax ≡ 1 (mod m)
def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m

def comb(a, b):
  ans = 1
  for i in range(b+1, a+1):
    ans *= i
    ans %= mod_param
  for i in range(1, a-b+1):
    k = modinv(i, mod_param)
    ans *= k
    ans %= mod_param
  return ans

if (abs(2*X-Y)%3 != 0):
  print(0)
else:
  alpha = (2*Y-X)//3
  beta = (2*X-Y)//3
  if alpha > beta:
    print(comb(alpha+beta, beta))
  else:
    print(comb(alpha+beta, alpha))

Submission status: Accepted

Solution code:
def cmb(m, n):
    if m - n < n:
        n = m - n
    if n == 0:
        return 1
    if n == 1:
        return m
    
    numerator = [m - n + k + 1 for k in range(n)]
    denominator = [k + 1 for k in range(n)]

    for p in range(2, n+1):
        pivot = denominator[p-1]
        if pivot > 1:
            offset = (m-n) % p
            for k in range(p-1, n, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    
    result = 1
    for k in range(n):
        if numerator[k] > 1:
            result = result * int(numerator[k]) % (10**9 + 7)

    return result

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

if (X+Y) % 3 != 0:
    print(0)
else:
    m = int((2*X - Y) / 3)
    n = int((2*Y - X) / 3)
    if m < 0 or n < 0:
        print(0)
    else:
        ans = cmb(m+n, n)
        print(int(ans))