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

x, y = map(int, input().split())
fl = True
a = ((2*x - y)/3)
b = ((2*y - x)/3)
if a < 0 or b < 0 or a % 1 != 0 or b % 1 != 0:
  fl = False

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 )

  

if fl:
  a = int(a)
  b = int(b)
  ans = cmb(a + b,a,mod)
  print(ans)
else:
  print(0)

Submission status: Accepted

Solution code:
MAX = 1000000
MOD = 1000000007

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


def com_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 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


def resolve():
    com_init()
    X, Y = map(int, input().split())
    if (X + Y) % 3 != 0 or max(X, Y) > min(X, Y) * 2:
        print(0)
        return
    c = (X + Y) // 3
    X -= c
    Y -= c
    print(com(X + Y, X))
    
    
if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys

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

inf = 10**9+7

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

if a<0 or b<0:
    print(0)
    sys.exit()

def nCr(n, r):
    r = min(r, n - r)
    if r == 0: return 1;
    if r == 1: return int(n%inf);
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i 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 = (result*numerator[k])%inf
    return int(result)

print(nCr(a+b, a))

Submission status: Accepted

Solution code:
import math

def cmb(n, r, mod):
    r = min(r, n-r)

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

X, Y = [int(i) for i in input().split()]
mod = 10**9+7 
x_tmp = 2*X - Y
y_tmp = 2*Y - X

if x_tmp < 0 or y_tmp < 0:
    ans = 0
elif x_tmp % 3 != 0 or y_tmp % 3 != 0:
    ans = 0
else:
    x = x_tmp // 3
    y = y_tmp // 3
    ans = cmb(x + y, y, mod)

print(ans)

Submission status: Accepted

Solution code:
X,Y = map(int,input().split())
if X>Y:
    X,Y = Y,X
if(X+Y)%3:
    print(0)
    exit()
n = (X+Y)//3
if X < n:
    print(0)
    exit()

MOD = 10**9+7
r = X-n

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

def ncr(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

print(ncr(n,r))

Submission status: Accepted

Solution code:
import math
import numpy as np

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:

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

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

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


    if N[0].is_integer() == True and N[1].is_integer() == True and N[0] >=0 and N[1] >=0:
          
        print(cmb(int(N[0]+N[1]),int(N[0]),mod))

    else:
        print(0)

else:
    print(0)

Submission status: Accepted

Solution code:
# nCr mod m
# rがn/2に近いと非常に重くなる
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
  
X, Y = map(int, input().split())
if (X+Y) % 3 != 0 or not (X <= 2*Y and Y <= 2*X):
    print(0)
    exit()

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

Submission status: Accepted

Solution code:
# nCrの左項には nn しか来ない場合、1!～(n-1)!は保持しなくてよいバージョン 
def prepare(n, MOD):
  # n! の計算
  f = 1
  for m in range(1, n+1):
    f *= m
    f %= MOD
  fn = f
  # n!^-1 の計算
  inv = pow(f, MOD-2, MOD)
  # n!^-1 - 1!^-1 の計算
  invs = [1]*(n+1)
  invs[n] = inv
  for m in range(n, 1, -1):
    inv *= m
    inv %= MOD
    invs[m-1] = inv
    
  return fn, invs

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

d, m = divmod(x+y, 3)
if m != 0 or x/y > 2 or y/x > 2:
  print(0)
  exit()
c = abs(d-x)
f, invs = prepare(d, MOD)
ans = f * invs[c] * invs[d-c] % MOD
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
def mod_comb(n, k, mod):
    return fact[n] * fact_inv[n-k]%mod * fact_inv[k]%mod

X, Y = map(int, input().split())
if X > Y:
    X, Y = Y, X
if (X + Y) % 3 != 0:
    print(0)
else:
    N = (X + Y) // 3
    M = Y - X
    if M > N:
        print(0)
    else:
        # 計算結果自体はcomb(N, (N-M)//2) % MODになる
        # これの高速化
        fact = [1]
        fact_inv = [1]
        for i in range(N):
            new_fact = fact[-1] * (i+1) % MOD
            fact.append(new_fact)
            fact_inv.append(pow(new_fact, MOD - 2, MOD))
        print(mod_comb(N, (N-M)//2, MOD))

Submission status: Accepted

Solution code:
from numpy.linalg import solve

#制約
MOD = 10**9 +7
MAX = 10**6

#　組み合わせ計算
def COM(n, r):
    fac = [1, 1]
    finv = [1, 1]
    inv = [0, 1]
    for i in range(2, MAX):
        fac.append(fac[i - 1] * i % MOD)
        inv.append(-inv[MOD % i] * (MOD // i))
        finv.append(finv[i - 1] * inv[i] % MOD)
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD

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

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

l = solve([[2, 1], [1, 2]], [x, y])
if l[0] < 0 or l[1] < 0: #n,m <0の時0
    print(0)
    exit()
# n+m回のうち，どのn回で移動するか n+mCOMnを計算
print(COM(int(l[0]+l[1]), int(l[0])))

Submission status: Accepted

Solution code:
X, Y = map(int,input().split())
# https://qiita.com/derodero24/items/
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

if (X+Y)%3!=0:
    print(0)
else:
    itr=(X+Y)//3
    x_mx=itr*2
    if itr<=X and X<=x_mx and itr<=Y and Y<=x_mx and X+Y==itr+x_mx:
        c=X-itr
        f=cmb(itr, c)
        f=f%(10**9+7)
        print(f)
    else:
        print(0)

Submission status: Accepted

Solution code:
import math
#import numpy as np 

#参照
#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())
#x,y = np.sum(1/3*(np.array([[ 2., -1.],[-1.,  2.]])*np.array([X,Y])),axis=1).astype(np.int32)
#print(x)
x = int(X-(X+Y)//3)
y = int(Y-(X+Y)//3)
if (X+Y)%3==0 and x>=0 and y>=0:
    print(cmb(x+y,x,mod))
else:
    print(0)

Submission status: Accepted

Solution code:
import math
#import numpy as np 

#参照
#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 = 5*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())
#x,y = np.sum(1/3*(np.array([[ 2., -1.],[-1.,  2.]])*np.array([X,Y])),axis=1).astype(np.int32)
#print(x)
x = int(X-(X+Y)//3)
y = int(Y-(X+Y)//3)
if (X+Y)%3==0 and x>=0 and y>=0:
    print(cmb(x+y,x,mod))
else:
    print(0)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class ModTools:
    """ 階乗たくさん使う時用のテーブル準備 """

    def __init__(self, MAX, MOD):
        """ MAX：階乗に使う数値の最大以上まで作る """
        
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD
        # 階乗テーブル
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        # 階乗の逆元テーブル
        inverse = [1] * MAX
        # powに第三引数入れると冪乗のmod付計算を高速にやってくれる
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, 0, -1):
            # 最後から戻っていくこのループならMAX回powするより処理が速い
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse
    
    def nCr(self, n, r):
        """ 組み合わせの数 (必要な階乗と逆元のテーブルを事前に作っておく) """

        if n < r: return 0
        # 10C7 = 10C3
        r = min(r, n-r)
        # 分子の計算
        numerator = self.fact[n]
        # 分母の計算
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

    def nPr(self, n, r):
        """ 順列 """

        if n < r: return 0
        return self.fact[n] * self.inv[n-r] % self.MOD

    def nHr(self, n, r):
        """ 重複組み合わせ """

        # r個選ぶところにN-1個の仕切りを入れる
        return self.nCr(r+n-1, r)

x, y = MAP()

x, y = min(x, y), max(x, y)
sm = x + y
if sm % 3 != 0:
    print(0)
    exit()
if y - x > sm // 3:
    print(0)
    exit()

# 連立方程式から式変形
a = (2*y-x) // 3
b = (2*x-y) // 3

mt = ModTools(a+b, MOD)
print(mt.nCr(a+b, a))

Submission status: Accepted

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

def mod_factorial(n):
    mod = 10**9+7

    if n < 1:
        return 1

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

def mod_pow(n,m):

    mod = 10**9+7
    r = 1

    while m > 0:
        if m & 1:
            r = r*n % mod
        n = n * n % mod
        m = m>>1

    return(r)



def mod_comb(n, k):
    mod = 10**9+7

    if n+k < 1:
        return 1
    
    a = mod_factorial(n)
    b = mod_pow(mod_factorial(k), mod-2)
    c = mod_pow(mod_factorial(n-k), mod-2)


    return (a * ((b * c) % mod)) % mod


a, b= map(int, input().split())

t = [a,b]

r = 0
mod = 10**9+7

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

if x%3 == 0 and y%3 == 0 and x*y >=0:
    m = int(x/3)
    n = int(y/3)

    r += mod_comb(n+m,m)

print(r)

Submission status: Accepted

Solution code:
# https://www.geeksforgeeks.org/compute-ncr-p-set-3-using-fermat-little-theorem/
def comb(n, r, p): 
    num = den = 1 
    for i in range(r): 
        num = (num * (n - i)) % p 
        den = (den * (i + 1)) % p 
    return (num * pow(den,  p - 2, p)) % p 
  
m = 10**9 + 7
x, y = (int(x) for x in input().split())
ans = 0
if (x - 2*y) % 3 == 0:
    beta = (x - 2*y) // -3
    alpha = y - 2*beta
    ans = comb(alpha+beta, max(alpha, beta), m)
print(ans)

Submission status: Accepted

Solution code:
M = 10 ** 9 + 7
 
x, y = map(int, input().split())
 
r = 0
if (x + y) % 3 == 0:
  a, b = (2 * y - x) // 3, (2 * x - y ) // 3
  if a >= 0 <= b:
    f = [1]
    for i in range(1, a + b + 1):
      f.append(f[-1] * i % M)
    r = f[a + b] * pow(f[a] * f[b], M - 2, M) % M
print(r)

Submission status: Accepted

Solution code:
M = 10 ** 9 + 7

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

r = 0
if (x + y) % 3 == 0:
  m = (x + y ) // 3
  a, b = (2 * y - x) // 3, (2 * x - y ) // 3
  if x >= m <= y:
    f = [1]
    for i in range(1, m + 1):
      f.append(f[-1] * i % M)
    r = f[m] * pow(f[a] * f[b], M - 2, M) % M
print(r)

Submission status: Accepted

Solution code:
from math import factorial
X,Y = map(int,input().split())
if (X + Y) % 3 != 0:
  print(0)
  exit()
MOD = 10**9 + 7
i2 = (2 * X - Y) // 3
i1 = X - 2 * i2
if i1 < 0 or i2 < 0:
  print(0)
  exit()
  
def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs

factorials, invs = prepare(i1+i2,MOD)
print(factorials[i1+i2] * invs[i1] % MOD * invs[i2] % MOD)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
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())
x = (-X+2*Y)/3
y = (2*X-Y)/3
if x.is_integer() and y.is_integer() and x>=0 and y>=0:
    x = int(x)
    y = int(y)
    maximam = max(x,y)
    minimam = min(x,y)
    mod = 10**9+7 #出力の制限
    N = x+y
    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(x+y,minimam,mod))
else:
    print(0)

Submission status: Accepted

Solution code:
x, y = map(int, input().split())
z = x + y
mod = 10 ** 9 + 7
if z % 3 == 0:
  w = z // 3
  a, b = sorted([x - w, y - w])
  if a < 0:
    print(0)
  elif a == 0:
    print(1)
  else:
    inv_mod = [1] * (a + 1)
    num = b + 1
    den = 1
    for i in range(2, a + 1):
      num = num * (b + i) % mod
      inv_mod[i] = -inv_mod[mod % i] * (mod // i) % mod
      den = den * inv_mod[i] % mod
    print(num * den % mod)
else:
  print(0)

Submission status: Accepted

Solution code:
mod = 10**9+7

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


def comb(n, r, mod):
    if r < 0 or n < r:
        return 0
    return fact[n]*pow(fact[r], mod-2, mod) * pow(fact[n-r], mod-2, mod) % mod


if (X + Y) % 3 != 0:
    ans = 0
else:
    n = (X + Y) // 3
    r = min(X, Y)-n
    # nCr
    fact = [1, 1]
    for i in range(2, n+1):
        fact.append(fact[-1] * i % mod)
    ans = comb(n, r, mod)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
import math

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

z = 10**9+7

X, Y = map(int, input().split())
x = (-X+2*Y)/3
y = (2*X-Y)/3
if x.is_integer() and y.is_integer() and x>=0 and y>=0:
    x = int(x)
    y = int(y)
    maximam = max(x,y)
    minimam = min(x,y)
    print(cmb(x+y,minimam)%z)
else:
    print(0)

Submission status: Accepted

Solution code:
import math
import sys
sys.setrecursionlimit(10000)

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

if (X + Y) % 3 != 0:
    print(0)
else:
    N_r = int((2*X-Y) / 3)
    N_u = int((2*Y-X) / 3)

    if N_u < 0 or N_r < 0:
        print(0)
    elif N_u == 0 or N_r == 0:
        print(1)
    else:

        mod = 1000000007
        ans = 0

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

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

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


        factorial = [1]
        for n in range(N_r + N_u-1):
            factorial.append(factorial[n]*(n+2)%mod)

        inverse_factorial = [0] * (N_u + N_r)
        inverse_factorial[-1] = power(factorial[-1], mod-2)

        for n in range(N_u+N_r-2, -1, -1):
            inverse_factorial[n] = (inverse_factorial[n+1] * (n+2)) % mod

        def combi(n, m):
            return factorial[n-1] * inverse_factorial[m-1] * inverse_factorial[n-m-1] % mod

        print(int(combi(N_u+N_r, N_u)))

Submission status: Accepted

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

_x, _y = map(int, input().split())


def nCk(n, k, m=10 ** 9 + 7):
    a = b = 1
    k = min(k, n - k)
    for i in range(k):
        a = (a * (n - i)) % m
        b = (b * (i + 1)) % m

    return (a * pow(b, m - 2, m)) % m


def chker(x, y):
    if (x + y) % 3 != 0 or x > 2 * y or y > 2 * x:
        print(0)
        return

    if x == y:
        b = x // 3
        print(nCk(2 * b, b))
        return

    x, y = (x, y) if x < y else (y, x)

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

    d1, d2 = b // 3, x - 2 * (b // 3)
    u = d1 + d2

    print(nCk(u, d1))


chker(_x, _y)

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 #出力の制限x
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().strip().split())
if (X + Y) % 3 != 0:
    print(0)
    exit(0)

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

if a < 0 or b < 0:
    print(0)
    exit(0)

print(cmb(a+b,a, mod))

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
def comb(n, k, MOD):
    if n < k or n < 0 or k < 0:
        return 0
    # k = min(k, n - k)
    if k == 0:
        return 1
    iinv = [1] * (k + 1)
    ans = n
    for i in range(2, k + 1):
        iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
        ans *= (n + 1 - i) * iinv[i] % MOD
        ans %= MOD
    return ans
X, Y = map(int,input().split())
if (X+Y) % 3 != 0:
    print(0)
    exit()
n = (2*Y-X)//3
m = (2*X-Y)//3
print(comb(n+m,m,MOD))

Submission status: Accepted

Solution code:
def comb(n, k, MOD):
    if n < k or n < 0 or k < 0:
        return 0
    k = min(k, n - k)
    if k == 0:
        return 1
    iinv = [1] * (k + 1)
    ans = n
    for i in range(2, k + 1):
        iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
        ans *= (n + 1 - i) * iinv[i] % MOD
        ans %= MOD
    return ans

mm = 10**9 + 7
x, y = (int(x) for x in input().split())
ans = 0
if (x - 2*y) % 3 == 0:
    beta = (x - 2*y) // -3
    alpha = y - 2*beta
    ans = comb(alpha+beta, beta, mm)
print(ans)

Submission status: Accepted

Solution code:
import math
tmp = input().split()
X = int(tmp[0])
Y = int(tmp[1])

mod = 10 ** 9 + 7

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

    r = n
    n = n+m
    # 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
    print(result % mod)

Submission status: Accepted

Solution code:
INF = 1000000000+7

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

n = a//3
m = b//3
nm = n+m

def cmb(n,r):
    if r > n:
        return 0
    if n - r < r:
         r = n - r
    if r > n:
        return 0
    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

if n<0 or m<0:
    print(0)
    exit()
ans = cmb(nm,n)
print(ans%INF)

Submission status: Accepted

Solution code:
import sys 
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 10**9 + 7

def calc_combination(n, k, MOD):
    if k > n - k:
        k = n - k
    ans = 1
    for i in range(1, k + 1):
        ans *= n + 1 - i
        ans *= pow(i, MOD - 2, MOD)
        ans %= MOD
    return ans
 
 
x, y = map(int, input().split())
m = 2 * y - x
n = 2 * x - y
 
if m < 0 or n < 0:
    ans = 0
elif m % 3 != 0 or n % 3 != 0:
    ans = 0
else:
    m //= 3
    n //= 3
    ans = calc_combination(m + n, n, MOD)

print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
def comb(n, k, MOD):
    if n < k or n < 0 or k < 0:
        return 0
    k = min(k, n - k)
    if k == 0:
        return 1
    iinv = [1] * (k + 1)
    ans = n
    for i in range(2, k + 1):
        iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
        ans *= (n + 1 - i) * iinv[i] % MOD
        ans %= MOD
    return ans
X, Y = map(int,input().split())
if (X+Y) % 3 != 0:
    print(0)
    exit()
n = (2*Y-X)//3
m = (2*X-Y)//3
print(comb(n+m,m,MOD))

Submission status: Accepted

Solution code:
MOD = 10**9 + 7


def comb(n, k, MOD):
    if n < k or n < 0 or k < 0:
        return 0
    k = min(k, n - k)
    if k == 0:
        return 1
    iinv = [1] * (k + 1)
    ans = n
    for i in range(2, k + 1):
        iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
        ans *= (n + 1 - i) * iinv[i] % MOD
        ans %= MOD
    return ans


x, y = map(int, input().split())
a = 2 * y - x
b = 2 * x - y

if a < 0 or b < 0:
    ans = 0
elif a % 3 != 0 or b % 3 != 0:
    ans = 0
else:
    a //= 3
    b //= 3
    # print(a, b)
    ans = comb(a + b, a, MOD)

print(ans)

Submission status: Accepted

Solution code:

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


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

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


ans = combination(a+b,a)

print(ans)

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
MOD=10**9+7
ans=0
if y>x:
    x,y=y,x
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 = 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 )

for a in range(1,x//2+1):
    b=x-2*a
    if 2*b+a==y:
        tmp=cmb(b+a,a,mod)%MOD
        ans+=tmp
        ans%=MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

MOD = 10 ** 9 + 7

import functools
import math

def mpow(x, n):
    result = 1
    while n > 0:
        if (n & 1):
            result = (result * x) % MOD
        x = (x * x) % MOD
        n >>= 1
    return result

# 方程式を解けば解が一意に定まるため、全パターンを試すのは無駄
def solver_not_good():
    factorial = [0] * (10 ** 6 + 1)
    inverse = [0] * (10 ** 6 + 1)
    factorial[0] = 1
    inverse[0] = 1
    for i in range(1, 10 ** 6 + 1):
        factorial[i] = (i * factorial[i-1]) % MOD
        inverse[i] = mpow(factorial[i], MOD - 2) % MOD

    total = 0
    twopath_maxnum = x // 2
    for twopath_num in range(twopath_maxnum + 1):
        onepath_num = x - twopath_num * 2
        if (onepath_num * 2 + twopath_num * 1) == y:
            a = factorial[onepath_num + twopath_num]
            b = inverse[onepath_num]
            c = inverse[twopath_num]
            total += (a * b * c) % MOD
    return total

def solver_better():
    # 剰余演算を都度挟みたいため、math.factorialは使えない
    factorial = [0] * (10 ** 6 + 1)
    factorial[0] = 1
    for i in range(1, 10 ** 6 + 1):
        factorial[i] = (i * factorial[i-1]) % MOD

    # x + y が3の倍数でないときは到達できない
    if ((x + y) % 3) != 0:
        return 0

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

    # x座標/y座標のどちらかに先に到達してしまう
    if a < 0 or b < 0:
        return 0

    return (factorial[a+b] * (mpow(factorial[a], MOD - 2) % MOD) * (mpow(factorial[b], MOD -2) % MOD)) % MOD

#solver = solver_not_good
solver = solver_better
print(solver())

Submission status: Accepted

Solution code:
def nCk(n, k, m=10**9+7):
    a = b = 1
    for i in range(k):
        a = (a * (n-i)) % m
        b = (b * (i+1)) % m
    return (a * pow(b, m-2, m)) % m

x,y = map(int,input().split())
if (x+y)%3 != 0 or min(x,y)*2 < max(x,y):
    ans = 0
else:
#パスカルの三角形より,n-1Ck-1を求める
    n = (x+y)//3 + 1
    k = x - (n-1) + 1
    ans = nCk(n-1,k-1)
print(ans)

Submission status: Accepted

Solution code:
p = 10 ** 9 + 7
 
def mod_inverse(a, p):
    mod = 1
    p_bin = bin(p-2)
    for i in range(len(p_bin) - 1, 1, -1):
        if i == len(p_bin) - 1:
            mul = a
            mul %= p
            mod *= (mul ** int(p_bin[i]))
            mod %= p
        else:
            mul = mul ** 2
            mul %= p
            mod *= (mul ** int(p_bin[i]))
            mod %= p
    return mod
 
def combination(n, k, p):
    a = 1
    for i in range(n, n - k, -1):
        a *= i
        a %= p
    b = 1
    for i in range(k):
        b *= (i + 1)
        b %= p
    return (a * mod_inverse(b, p)) % p

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

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

Submission status: Accepted

Solution code:
x,y=[int(j) for j in input().split()]
U = 2*10**6
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
  fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U],MOD-2,MOD)
 
for i in range(U,0,-1):
	fact_inv[i-1] = (fact_inv[i]*i)%MOD
 
def comb(n,k):
  if k < 0 or k > n:
    return 0
  x = fact[n]
  x *= fact_inv[k]
  x %= MOD
  x *= fact_inv[n-k]
  x %= MOD
  return x

if (2*y-x)//3==(2*y-x)/3 and (2*x-y)//3==(2*x-y)/3:
    i=(2*y-x)//3
    j=(2*x-y)//3
    print(comb(i+j,min(i,j)))
else:
    print(0)

Submission status: Accepted

Solution code:
import sys 
input = sys.stdin.readline
# readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

MOD = 10**9 + 7

def calc_combination(n, k, MOD):
    if k > n - k:
        k = n - k
    ans = 1
    for i in range(1, k + 1):
        ans *= n + 1 - i
        ans *= pow(i, MOD - 2, MOD)
        ans %= MOD
    return ans
 
 
x, y = map(int, input().split())
m = 2 * y - x
n = 2 * x - y
 
if m < 0 or n < 0:
    ans = 0
elif m % 3 != 0 or n % 3 != 0:
    ans = 0
else:
    m //= 3
    n //= 3
    ans = calc_combination(m + n, n, MOD)

print(ans)

Submission status: Accepted

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


# modしながらコンビネーションを求める
def mod_cmb(n, r, mod):
    p, q = 1, 1
    for i in range(r):
        p = p * (n - i) % mod
        q = q * (i + 1) % mod
    return p * mod_inverse(q, mod) % mod


# modしたa^bを求める
def mod_pow(a, p, mod):
    if p == 0:
        return 1
    elif p % 2 == 1:
        return a * mod_pow(a, p - 1, mod)
    else:
        return (mod_pow(a, p // 2, mod) % mod) ** 2 % mod


# aで割りたいときはa^(p-2)をかければよい（pは素数かつmodで使うやつ）
def mod_inverse(a, mod):
    return mod_pow(a, (mod - 2), mod)


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

# 移動1, 2を使う回数
n = (2 * Y - X) // 3
m = (2 * X - Y) // 3

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

print(mod_cmb(n + m, n, mod))