Problem:


Score : 400 points

Problem Statement

There is a knight - the chess piece - at the origin (0, 0) of a two-dimensional grid.

When the knight is at the square (i, j), it can be moved to either (i+1,j+2) or (i+2, j+1).

In how many ways can the knight reach the square (X, Y)?

Find the number of ways modulo 10^9 + 7.

Constraints

1 \leq X \leq 10^6

1 \leq Y \leq 10^6

All values in input are integers.

Input

Input is given from Standard Input in the following format:

X Y

Output

Print the number of ways for the knight to reach (X, Y) from (0, 0), modulo 10^9 + 7.

Sample Input 1

3 3

Sample Output 1

2

There are two ways: (0,0) \to (1,2) \to (3,3) and (0,0) \to (2,1) \to (3,3).

Sample Input 2

2 2

Sample Output 2

0

The knight cannot reach (2,2).

Sample Input 3

999999 999999

Sample Output 3

151840682

Print the number of ways modulo 10^9 + 7.



Sample input:
3 3


Sample output:
2

Submission status: Accepted

Solution code:
import sys

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

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

n1 = (2 * X - Y) // 3
n2 = (2 * Y - X) // 3

if n1 < 0 or n2 < 0:
    print(0)
    sys.exit()

P = 10 ** 9 + 7
N = 10 ** 6 + 5
inv_t = [0]+[1]
for i in range(2, N):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

m = 10 ** 9 + 7
res = 1
for i in range(2, n1 + n2 + 1):
    res = res * i % m
for i in range(1, n2 + 1):
    res = res * inv_t[i] % m
for i in range(1, n1 + 1):
    res = res * inv_t[i] % m
print(res)

Submission status: Accepted

Solution code:
MAX = 1000000
MOD = 1000000007

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


def comb_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 comb(n, k):
    if n < 0 or k < 0 or n < k:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


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


def solve(x, y):

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

    n = (2 * y - x) // 3
    m = (2 * x - y) // 3
    if n < 0 or m < 0:
        return 0

    return comb(n + m, n)


print(solve(x, y))

Submission status: Accepted

Solution code:
def main():
    X, Y = map(int, input().split())
    a = (X+Y)//3
    ans = 0
    mod = 10**9+7

    f = [1]
    for i in range(a):
        f.append(f[i]*(i+1)%mod)

    if (X+Y)%3 == 0:
        for i in range(a+1):
            x = i + 2 * (a - i)
            y = (2 * i) + (a - i)
            if X == x and Y == y:
                 ans += f[a] * pow(f[i], mod-2, mod)%mod * pow(f[a-i], mod-2, mod)%mod
                                                             
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def mod_Combination(n, k, mod):
    def ext_gcd(a, b):
        if b == 0:
            return a, 1, 0
        else:
            d,x,y = ext_gcd(b,a%b)
            x-=(a//b)*y 
        return d,y,x
    p,q=1,1
    for i in range(n-k+1, n+1):
        p=(p*i)%mod
    for i in range(2, k+1):
        q=(q*i)%mod
    return int(p*(ext_gcd(q, mod)[1]%mod)%mod)

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 = mod_Combination(int(a + b), int(b), 10**9 + 7)

print(ans)

Submission status: Accepted

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

def mod_Combination(n, k, mod):
    def ext_gcd(a, b):
        if b == 0:
            return a, 1, 0
        else:
            d,x,y = ext_gcd(b,a%b)
            x-=(a//b)*y 
        return d,y,x
    p,q=1,1
    for i in range(n-k+1, n+1):
        p=(p*i)%mod
    for i in range(2, k+1):
        q=(q*i)%mod
    return int(p*(ext_gcd(q, mod)[1]%mod)%mod)

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 = mod_Combination(int(a + b), int(a), 10**9 + 7)

print(ans)

Submission status: Accepted

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

def mod_Combination(n, k, mod):
    def ext_gcd(a, b):
        if b == 0:
            return a, 1, 0
        else:
            d,x,y = ext_gcd(b,a%b)
            x-=(a//b)*y 
        return d,y,x
    p,q=1,1
    for i in range(n-k+1, n+1):
        p=(p*i)%mod
    for i in range(2, k+1):
        q=(q*i)%mod
    return int(p*(ext_gcd(q, mod)[1]%mod)%mod)

if X > Y:
    X, Y = Y, X

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 = mod_Combination(int(a + b), int(a), 10**9 + 7)

print(ans)

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 power(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1
 
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x % mod
        x *= x % mod
        n //= 2
 
    return K * x % mod
 
def div(a, b):
    return mul(a, power(b, mod-2))
 
def fact(n):
    f = 1
    for i in range(1,n+1):
        f *= i
        f %= mod
    return f

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

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

Submission status: Accepted

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

def mod_Combination(n, k, mod):
    def ext_gcd(a, b):
        if b == 0:
            return a, 1, 0
        else:
            d,x,y = ext_gcd(b,a%b)
            x-=(a//b)*y 
        return d,y,x
    p,q=1,1
    for i in range(n-k+1, n+1):
        p=(p*i)%mod
    for i in range(2, k+1):
        q=(q*i)%mod
    return int(p*(ext_gcd(q, mod)[1]%mod)%mod)

if X > Y:
    X, Y = Y, X

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

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

elif Y > 2*X:
    ans = 0

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

print(ans)

Submission status: Accepted

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



if (2 * Y - X) % 3 != 0 or (2 * X - Y) % 3 != 0 or (2 * Y - X) // 3 < 0 or (2 * X - Y) // 3 < 0:
	print(0)
else:
	a = (2 * Y - X) // 3
	b = (2 * X - Y) // 3
	factorial = [1]
	inverse = [1]
	for i in range(1, a + b + 5):
		factorial.append(factorial[-1] * i % MOD)
		inverse.append(pow(factorial[-1], MOD - 2, MOD))
	print(factorial[a + b] * inverse[a] * inverse[b] % MOD)

Submission status: Accepted

Solution code:
import sys
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 (x+y)%3!=0:
  print(0)
  sys.exit()
n=(x+y)//3

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 )

print(cmb(n,x-n,mod))

Submission status: Accepted

Solution code:
import sys

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

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

mod = 10 ** 9 + 7

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

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

a = y - (x + y) // 3
b = x - (x + y) // 3

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

ans = fac(a+b)
ans = (ans * inv(fac(a))) % mod
ans = (ans * inv(fac(b))) % mod
print (ans)

Submission status: Accepted

Solution code:
X, Y = [int(i) for i in input().split(' ')]
mod = 10**9+7

x =0
y =0
x += X
y += Y
counter =[0,0]
while x > 0 or y > 0:
    if x >= y:
        x -= 2
        y -= 1
        counter[0] +=1 
    else:
        x -= 1
        y -= 2
        counter[1] +=1 
        

def nCr(n,r,mod):
    if (r<0 or r>n):
        return 0

    return (n_legular[n]*r_inverse[r]*r_inverse[n-r]) % mod

N =counter[0]+counter[1]
n_legular = [1,1]
r_inverse = [1,1] 
inverse_calc = [0,1]

for i in range(2,N+1):
    n_legular.append(n_legular[-1]*i%mod)
    inverse_calc.append(-inverse_calc[mod % i] * (mod//i)  % mod)
    r_inverse.append(r_inverse[-1]*inverse_calc[-1] % mod)
    
if (X+Y) % 3 != 0:
    print(0)
elif (X > 2*Y) or (Y > 2*X):
    print(0)
    
else:
    print(nCr(counter[0]+counter[1],counter[0],mod))

Submission status: Accepted

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

def f(x, p):
    a = 1
    for i in range(1, x + 1):
        a *= i
        a %= p
    return a
def nCr(a, b, p):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= f(a, p)
    c *= pow(f(b, p), p - 2, p)
    c *= pow(f(a - b, p), p - 2, p)
    return c % p

if (2*X-Y)%3 != 0 or (2*Y-X)%3 != 0 or Y > X*2 or X > Y*2:
  print(0)
else:
  m = (2*X-Y)//3
  n = (2*Y-X)//3
  print(nCr(m+n, n, 10**9+7))

Submission status: Accepted

Solution code:
from math import factorial
mod = int(1e+9 + 7)

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

X2 = 2*X - Y
Y2 = -X + 2*Y

if X2 < 0:
    print "0"
    exit()
elif Y2 < 0:
    print "0"
    exit()

if X2%3 != 0:
    print "0"
    exit()
elif Y2%3 != 0:
    print "0"
    exit()

X2 = X2/3
Y2 = Y2/3

ans = 1

n = X2+Y2
m = Y2

for i in range(n-m+1, n+1):
    ans = (ans*i)%mod


new = 1
for i in range(2, m+1):
    new = (new*i)%mod

new = pow(new, mod-2, mod)

ans = (ans*new)%mod

print ans

Submission status: Accepted

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


def count_combination(n: int, r: int, mod: int = 10 ** 9 + 7) -> int:
    '''Count the total number of combinations.
        nCr % mod.
        nHr % mod = (n + r - 1)Cr % mod.
    Args:
        n   : Elements. Int of number (greater than 1).
        r   : The number of r-th combinations. Int of number (greater than 0).
        mod : Modulo. The default is 10 ** 9 + 7.
    Returns:
        The total number of combinations.
    Landau notation: O(n)
    See:
    https://qiita.com/derodero24/items/91b6468e66923a87f39f
    '''

    if (r > n) or (n < 0) or (r < 0):
        return 0

    if r > (n - r):
        return count_combination(n, n - r, mod)

    if r == 0 or r == n:
        return 1

    if r == 1:
        return n

    multiple = 1
    division = 1

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

    return multiple * pow(division, mod - 2, mod) % mod


def main():
    large_x, large_y = map(int, input().split())
    x = -large_x + 2 * large_y
    y = 2 * large_x - large_y

    # ■ポイント1
    # 原点から(X, Y)に到達するには，
    # (i + 1, j + 2)をx回, (i + 2, j + 1)をy回操作する必要がある，と言い換える

    # 移動したマスの数と操作回数に関する連立方程式を立てる
    #  x + 2y = X
    # 2x +  y = Y
    # これを解くと，x = (-X + 2Y) / 3, y = (2X - y) / 3

    # 到達できないパターン：x, yが整数でないとき
    if x % 3 != 0 or y % 3 != 0:
        print(0)
        exit()

    # ■ポイント2
    # 組み合わせは，(x + y)回のうちx回もしくはy回を選ぶ方法と同じ
    xy = (x + y) // 3
    y = y // 3
    print(count_combination(xy, y))

    # 類題: ARC035B
    # https://atcoder.jp/contests/arc035/tasks/arc035_b


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def count_combination(n: int, r: int, mod: int = 10 ** 9 + 7) -> int:
    '''Count the total number of combinations.
        nCr % mod.
        nHr % mod = (n + r - 1)Cr % mod.
    Args:
        n   : Elements. Int of number (greater than 1).
        r   : The number of r-th combinations. Int of number (greater than 0).
        mod : Modulo. The default is 10 ** 9 + 7.
    Returns:
        The total number of combinations.
    Landau notation: O(n)
    See:
    https://qiita.com/derodero24/items/91b6468e66923a87f39f
    '''

    if (r > n) or (n < 0) or (r < 0):
        return 0

    if r > (n - r):
        return count_combination(n, n - r, mod)

    if r == 0 or r == n:
        return 1

    if r == 1:
        return n

    multiple = 1
    division = 1

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

    return multiple * pow(division, mod - 2, mod) % mod


def main():
    large_x, large_y = map(int, input().split())
    x = -large_x + 2 * large_y
    y = 2 * large_x - large_y

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

    xy = (x + y) // 3
    y = y // 3
    print(count_combination(xy, y))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def nCr(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 max(x, y) > 2 * min(x, y) or (x+y) % 3 != 0:
    print(0)
else:
    n = (x + y) // 3
    r = 2 * n - x
    print(nCr(n, r))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
from math import factorial

# fac = [0] * (10**6+5)
# ifac = [0] * (10**6+5)
# d = 10**9 + 7

# def mpow(x, n):
#     ans = 1
#     while n != 0:
#         if n&1:
#             ans = ans * x % d
#         x = x*x % d
#         n = n >> 1
#     return ans

# def comb(a, b):
#     if a == 0 and b == 0:
#         return 1
#     if a < b or a < 0:
#         return 0
#     tmp = ifac[a-b] * ifac[b] % d
#     return tmp * fac[a] % d

def make_comb(m, d):
    def div(i, j):
        # 1/i mod(j)
        # calc i**(j-2) mod(j)
        p = j - 2
        ans = 1
        while p != 0:
            if p % 2 == 1:
                ans = (ans * i) % d
            i = i**2 % d
            p >>= 1
        return ans

    fac = [0] * (m+1)
    ifac = [0] * (m+1)
    # nCk
    fac[0] = 1
    ifac[0] = 1
    for i in range(m):
        fac[i+1] = (fac[i] * (i+1)) % d
        ifac[i+1] = (ifac[i] * div(i+1, d)) % d
    def comb(n, k):
        if n == 0 and k == 0:
            return 1
        if n < k or n < 0:
            return 0
        return (fac[n] * ifac[k] * ifac[n-k]) % d
    return comb

def main():
    x, y = map(int, input().strip().split())
    if (x + y) % 3 != 0:
        print(0)
        return
    k = (x+y) // 3
    q = x - k
    if x - 2 * q < 0 or q < 0:
        print(0)
        return
    comb = make_comb(10**6, 10**9+7)
    print(comb(k, q))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def cmb(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    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:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

MOD = 10**9 + 7


def cmb(n, k, fac, ifac):
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % MOD


def make_table(n):
    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 main():
    X, Y = map(int, input().split())

    if X > Y:
        X, Y = Y, X
    dist = X + Y

    if dist % 3 != 0:
        print(0)
        exit()

    total = int((X+Y) / 3)
    n = X - total

    if Y > 2 * X:
        print(0)
    else:
        fac, ifac = make_table(total)
        ans = cmb(total, n, fac, ifac)
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

if x == 0 or y == 0:
    print(0)
    exit()

X = max(x,y)
Y = min(x,y)

all_move = (X+Y)//3
diff = (X-Y)
Y_move = (all_move - diff)//2


def mod_cmb(n, r, mod): # nCr mod p
    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 ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

print(mod_cmb(all_move, Y_move,MOD))

Submission status: Accepted

Solution code:
def nCr(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 max(x,y) > 2 *min(x,y):
    print(0)
elif (x+y) % 3 == 0:
    k = (x+y)//3
    n = (2*x-y)//3
    print(nCr(k,n))
else:
    print(0)

Submission status: Accepted

Solution code:
X, Y = map(int, input().split())
MOD = int(pow(10, 9) + 7)
def isValid(x, y):
    if (X + Y) % 3 != 0:
        return False
    S = (X + Y) // 3
    return Y >= S and X >= S

if not isValid(X, Y):
    print(0)
    quit()

S = (X + Y) // 3
A = (2 * X - Y) // 3

fact = [1 for i in range(S+1)]
for i in range(1, S+1): fact[i] = (i * fact[i - 1]) % MOD

def modInverse(x, power=MOD - 2):
    if power == 0: return 1
    cur = modInverse(x, power // 2); cur *= cur; cur %= MOD
    if power % 2 == 1:
        cur *= x
    cur %= MOD
    return cur


print((fact[S] * modInverse(fact[A]) * modInverse(fact[S-A])) % MOD)

Submission status: Accepted

Solution code:
# coding UTF-8
# 
# problem D
# 
import itertools
import numpy as np
from scipy.spatial import distance

# 組み合わせ関数の定義
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

# データ入力
P = list(map(int, input().split()))

# X の値から, 2進む回数最大回数をX2に格納する
if P[0]%2 == 0:
    X2 = int(P[0]/2); X1 = 0
else:
    X2 = int(P[0]/2); X1 = 1

# Y の進み方として存在する, y軸に2進む回数をYに格納する
Y_check = []
Y = []
for y in range(X2+1):
    if 2*(P[0]-2*y)+y == P[1]:
        Y.append(y)
    Y_check.append(2*(P[0]-2*y)+y)

# 進み方を調べる
x = np.array(["1", "2"])
for i in range(len(Y)):
    #print(len(Y))
    #print(np.repeat(x, [Y[i], P[0]-2*Y[i]], axis=0))
    print(cmb(Y[i]+P[0]-2*Y[i], Y[i])%(10**9+7))

if not Y:
    print(0)

Submission status: Accepted

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

def nCr(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

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

Submission status: Accepted

Solution code:
def nCk(n,k):
    if n<k or (n<0 or k<0):
        return 0
    #k=min(k,n-k)
    num,denum=1,1
    for i in range(k):
        num=num*(n-i)%mod
        denum=denum*(i+1)%mod
    return num*pow(denum,mod-2,mod)%mod

x,y=map(int,input().split())
mod=10**9+7
n=(y-0.5*x)/1.5
if int(n)!=n:
    print(0)
else:
    m=(y+x)//3
    l=int(n)
    print(nCk(m,l))

Submission status: Accepted

Solution code:
# 2019-11-16 21:01:15(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 


mod = 10 ** 9 + 7

def comb(n, r):
    r = min(r, n - r)
    if r == 0: return 1
    if r == 1: return n

    numerator = list(range(n-r+1, n+1))
    denominator = list(range(1, r+1))

    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 sys.stdin.readline().split()]
    # n(+1, +2), m(+2, +1)
    n, m = (2 * y - x) / 3, (2 * x - y) / 3

    if n != abs(int(n)) or m != abs(int(m)):
        print(0)
        sys.exit()
    else:
        n, m = int(n), int(m)
        ans = comb(n+m, n) % mod
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def make_tables(m):
    fac=[1,1]
    finv=[1,1]
    inv=[0,1]
    for i in range(2,m+1):
        fac.append((fac[-1]*i)%mod)
        inv.append((-inv[mod%i]*(mod//i))%mod)
        finv.append(finv[i-1]*inv[i]%mod)
    return fac,finv

def calc_nCk(n,k,fac,finv):
    if n<k or (n<0 or k<0):
        return 0
#    k=min(k,n-k)
    return fac[n]*(finv[k]*finv[n-k]%mod)%mod

x,y=map(int,input().split())
mod=10**9+7
n=(y-0.5*x)/1.5
if int(n)!=n:
    print(0)
else:
    m=(y+x)//3
    l=int(n)
    fac,finv=make_tables(m)
    ans = calc_nCk(m,l,fac,finv)
    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 % (10 ** 9 + 7)
ab = input().split()
a, b = int(ab[0]), int(ab[1])
sum = a + b
if a>(2*b) or b>(2*a):
	print("0")
elif sum % 3 == 0:
    n = int(sum / 3)
    m = b - n
    print(cmb(n, m))
else:
	print("0")

Submission status: Accepted

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


def main():
    X, Y = map(int, input().split())

    if (X + Y) % 3 or X > Y*2 or Y > X*2:
        return 0

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


print(main())

Submission status: Accepted

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

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

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

X, Y = [int(x) for x in input().strip().split()]
p = (X, 2 * X)
n1 = X
n2 = 0
f = True
while p != (X, Y):
    n1 -= 2
    n2 += 1
    p = (n1 + 2 * n2, 2 * n1 + n2)
    if p[1] <= 0:
        f = False
        break

if n1 < 0 or n2 < 0:
    print(0)
else:
    print(combination(n1 + n2, n1))

Submission status: Accepted

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

MOD = 1000000007  # type: int

def ncr(n, r, p): 
    # initialize numerator 
    # and denominator 
    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 

#
# X : X座標
# Y : Y座標
#
def solve(X: int, Y: int):
    # 3 の倍数のとき、(+1,+2) の移動の回数を n
    # n + 2m = X
    # n
    # (+2,+1) の移動の回数を m 
    # 2n + m = Y
    # m

    n = -1
    for m in range(X + 1):

        # print("{} {}".format(m, m / (X + 1) * 100))

        # print('---')
        # print(m)
        # print(X - m)
        # print(Y - (2 * m))

        if (X - m) / 2 == (Y - (2 * m)):
            n = int((X - m) / 2)
            # print("{} {}".format(m, n))
            break

    # print("{} {}".format(m, n))

    if(n == -1):
        print(0)
    else:
        # print(math.factorial(m + n))
        print(ncr((m + n), n, MOD))

    return


# 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():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(X, Y)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
x, y = map(int, input().split())
mod = 10**9+7
def inv(x):
        return pow(x, mod-2, mod)
def fact(x):
        f = 1 
        for i in range(1, x + 1): 
                f *= i
                f %= mod    
        return f
def comb(n, r): 
        return (fact(n) * inv(fact(n-r)) * inv(fact(r))) % mod 
if (x + y) % 3 != 0:
  print(0)
else:
  n = (x + y) // 3
  if n > x or n > y:
    print(0)
  else:
    nx = x - n
    print(comb(n, nx))

Submission status: Accepted

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

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

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

X, Y = [int(x) for x in input().strip().split()]
p = (X, 2 * X)
n1 = X
n2 = 0
f = True
while p != (X, Y):
    n1 -= 2
    n2 += 1
    p = (n1 + 2 * n2, 2 * n1 + n2)
    if p[1] <= 0:
        f = False
        break

if n1 < 0 or n2 < 0:
    print(0)
else:
    print(combination(n1 + n2, n1) % (10 ** 9 + 7))

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

# X = 2n+m, Y = n+2mとして
n = (2*X-Y)//3
m = (Y-n)//2

mod = 10**9+7 #出力の制限
N = n+m
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 (X + Y) % 3 != 0:
    print(0)
elif n < 0 or m < 0:
    print(0)
else:
    print(cmb(n+m, n, mod))

Submission status: Accepted

Solution code:
import sys
from math import factorial

def ncr(n, r, p): 
    # initialize numerator 
    # and denominator 
    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 

def check(x, y):
    if (x + y) % 3 == 0:
        return True
    else:
        return False
    

# Read
line = sys.stdin.readlines()[0]
X, Y = map(int,line.split(' '))

if not check(X, Y):
    print(0)
    exit(0)

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

if n < 0 or m < 0:
    print(0)
else:
    print(ncr(n+m, n, 10**9+7))

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())
if (x+y)%3!=0 or min(x,y)<(x+y)/3:
    print(0)
    exit()
n=(x+y)//3
r=(n-abs(x-y))//2
mod=10**9+7
a = cmb(n,r)
print(a%mod)

Submission status: Accepted

Solution code:
# 2019-11-16 21:01:15(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 


def comb(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 # 問題によってNの大きさは変える
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 )


def main():
    x, y = [int(x) for x in sys.stdin.readline().split()]
    # n(+1, +2), m(+2, +1)
    n, m = (2 * y - x) / 3, (2 * x - y) / 3

    if n != abs(int(n)) or m != abs(int(m)):
        print(0)
        sys.exit()
    else:
        n, m = int(n), int(m)
        ans = comb(n+m, m, mod)
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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
    
X,Y = [int(i) for i in input().split()]
def check(x,y):
    if x/2 == y:
        return 0
    elif x/2 < y:
        return 1
    else:
        return 9
cnt = 0
possible = True
MOD = 10**9 + 7

while True:
    check_num =  check(X,Y)
    if check_num == 0:
        break
    elif check_num == 1:
        X += 1
        Y -= 1
        cnt += 1
    else:
        possible = False
        break
if possible == True:
    n = X // 2 
    r = cnt
    print(getComb(n,r,MOD))
else:
    print(0)

Submission status: Accepted

Solution code:
def fact(n, r):
    calc_a = 1
    calc_b = 1
    for i in range(1, r + 1):
        calc_a = (calc_a * (n + 1 - i)) % p
        calc_b = (calc_b * i) % p
    ans = (calc_a * pow(calc_b, p - 2, p)) % p
    return ans


p = (10 ** 9) + 7
x, y = map(int, input().split())
if ((2 * y - x) % 3 == 0) & ((2 * x - y) % 3 == 0) & (2 * y >= x) & (2 * x >= y):
    a = (2 * y - x) // 3
    b = (2 * x - y) // 3
    print(fact(a + b, min(a, b)))
else:
    print(0)