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())
MOD = 10**9 + 7

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

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

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
    
comb = Combination(1000000)
print(comb(SUM, n)%MOD)

Submission status: Accepted

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

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

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

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


mod = 10**9+7
N = 10**6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

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

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

Submission status: Accepted

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

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

if 2 * min(X, Y) < max(X, Y):
    print(0)
    sys.exit()

def f(n, A):
    if A == 0:
        return 1
    bunsi = reduce(lambda x, y: x*y%mod, range(n, n-A, -1))
    bunbo = reduce(lambda x, y: x*y%mod, range(1, A+1))
    return bunsi * pow(bunbo, mod-2, mod) % mod

ans = 0
r, d = 0, 0
if X == Y:
    r, d = X//3, Y//3
    ans = f(r+d, d)%mod
else:
    r = abs(X-Y) + ((X+Y) - 3*abs(X-Y))//6
    d = ((X+Y) - 3*abs(X-Y))//6
    ans = f(r+d, d)%mod

print(ans)

Submission status: Accepted

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

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

if 2 * min(X, Y) < max(X, Y):
    print(0)
    sys.exit()

def f(n, A):
    bunsi = reduce(lambda x, y: x*y%mod, range(n, n-A, -1))
    bunbo = reduce(lambda x, y: x*y%mod, range(1, A+1))
    return bunsi * pow(bunbo, mod-2, mod) % mod

ans = 0
r, d = 0, 0
if X == Y:
    r, d = X//3, Y//3
    ans = f(r+d, d)%mod
else:
    r = abs(X-Y) + ((X+Y) - 3*abs(X-Y))//6
    d = ((X+Y) - 3*abs(X-Y))//6
    if d == 0:
        print(1)
        sys.exit()
    ans = f(r+d, d)%mod

print(ans)

Submission status: Accepted

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

def factorial(n):
    res = 1
    for i in range(2, n+1):
        res *= i
        res %= P
    return res

if (2*X-Y)%3 == 0 and (-X+2*Y)%3 == 0 and 2*X-Y >= 0 and -X+2*Y >= 0:
    a = (-X+2*Y)//3
    b = (2*X-Y)//3
    print((factorial(a+b)*pow(factorial(a), P-2, P)*pow(factorial(b), P-2, P))%P)
else:
    print(0)

Submission status: Accepted

Solution code:
mod = 10**9 + 7
def cmb(n,r,mod):
	a=1
	b=1
	r = min(r,n-r)
	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 = map(int,input().split())
if (X+Y)%3 != 0:
  ans = 0
else:
  n = (2*X-Y)//3
  m = (2*Y-X)//3
  if n < 0 or m < 0:
    ans = 0
  else:
    ans = cmb(n+m,m,mod)
print(ans)

Submission status: Accepted

Solution code:
# 726 diff 1000
# 解法 836 XYへ到達する場合はどの経路も合計の長さは同じ = 動き方1,2の合計は同じ．
# なので合計値 L がわかればLについてmove1=i,move2=L-iとして，実際の経路の構成の仕方は,L_C_iなので

move1 = [1,2]
move2 = [2,1]
X,Y = map(int,input().split())
# まず，目的地へ到達できるか？到達できる場合は合計どれだけの移動量が必要かを計算する
max_move1 = int(Y/2)
move2_num = -1
move1_num = -1
for i in range(max_move1+1):
    rest = [X-i,Y-2*i]
    if (X-i) == 2*(Y-2*i):
        move1_num = i
        move2_num = (Y-2*i)
if move1_num == -1:
    print(0)
    exit()

# 到達するのに必要な合計の移動量がわかったので，それらの並べ替えについて考える．
# 求めるのは nCk　すなわち，いつもの奴
large = 10**9 + 7
# mod(x^p-1,p) = 1 よってmod(x^p-2,p) = 1/x となる.
ans = 1
for i in range(move1_num):
    ans *= (move1_num+move2_num - i)
    ans %= large
for j in range(2,move1_num+1):
    ans *= pow(j,large-2,large)
    ans %= large
print(ans)

Submission status: Accepted

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

    return ret


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

MOD = 10 ** 9 + 7

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

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

print(comb(a + b, a))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 10**9+7
X,Y = map(int,readline().split())
if X > Y:
    X,Y = Y,X
Z = X+Y
if Z % 3 == 0 and X <= Y <= 2*X:
    N = Z//3
    r = (N-(Y-X)) // 2
else:
    print(0)
    sys.exit()
f = [1]*(N+1)
for i in range(1,N+1):
    f[i] = i * f[i-1] % mod
a = pow(f[r],mod-2,mod)
b = pow(f[N-r],mod-2,mod)
ans = f[N] * a * b % mod
print(ans)

Submission status: Accepted

Solution code:
def main():
    from functools import reduce
    class comb_mod:
        mod = 1000000007
        MAX = pow(10, 6)
        fac = [0 for i in range(MAX)]
        finv = [0 for i in range(MAX)]
        inv = [0 for i in range(MAX)]

        def __init__(self):
            self.fac[0], self.fac[1] = 1, 1
            self.finv[0], self.finv[1] = 1, 1
            self.inv[1] = 1
            for i in range(2, self.MAX):
                self.fac[i] = self.fac[i - 1] * i % self.mod
                self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
                self.finv[i] = self.finv[i - 1] * self.inv[i] % self.mod
        def combination(self, n, r):
            if n < r:
                return 0
            if n < 0 or r < 0:
                return 0
            return self.fac[n] * (self.finv[r] * self.finv[n - r] % self.mod) % self.mod
        def combination_mul(self, N, R):
            return reduce(lambda x, y: x * self.combination(y[0], y[1]) % self.mod, zip(N, R), 1)
    x, y = list(map(int, input().split()))
    ans = 0
    C = comb_mod()
    for i in range(x, -1, -2):
        j = (x - i) // 2
        if 2 * i + j == y:
            ans += C.combination(i + j, i)
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

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

def comb(n, r, mod):
    n1 = n+1
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer*(n1-i)%mod # combの分子
        denom = denom*i%mod #combの分母
    return numer*pow(denom, mod-2, mod)%mod #(n!*(r**(mod-2)%mod))%mod
    #a/b mod p = (a*(1/b) mod p)なので1/b(b**-1)を求めたい（つまりcombの分母）
    #(b**(p-2)*b mod p) = 1 なので
    #b**-1 = b**-2 mod p　が成立！！！
    #return内のpowがb**-1を求める部分

if (x+y)%3 != 0 or (2*x-y)//3 < 0 or (2*y-x)//3 < 0:
    print(0)
else:
    n = (2*x-y)//3
    m = (2*y-x)//3
    print(comb(n+m, min(n, m), mod))


#TLE解
# from collections import deque

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

# knight = [(1, 2), (2, 1)]
# dp = [[0 for _ in range(Y+1)] for _ in range(X+1)]
# dp[0][0] = 1

# que = deque([(0, 0)])

# while que:

#     x, y = que.pop()
#     for x1, y1 in knight:
#         if x+x1 > X or y+y1 > Y:
#             continue
#         dp[x+x1][y+y1] += dp[x][y]
#         que.append((x+x1, y+y1))
#     # print(que)
# print(dp[X][Y]%1000000007)
# # print(dp)

Submission status: Accepted

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


def conb(n, r):
    x = 1
    y = 1
    for i in range(n - r + 1, n + 1):
        x = (x * i % P)
    for i in range(1, r + 1):
        y = (y * i % P)
    y_inv = power(y, P - 2)
    return (x * y_inv)%P


def power(x, n):
    ans = 1
    while (n > 0):
        if (bin(n & 1) == bin(1)):
            ans = (ans * x) % P
        x = (x * x) % P
        n = n >> 1  # ビットシフト
    return ans


if (2 * X - Y) % 3 == 0 and (2 * Y - X) % 3 == 0:
    u = (2 * Y - X) // 3
    r = (2 * X - Y) // 3
    if u < 0 or r < 0:
        print(0)
    else:
        print(conb(u + r, r))


else:
    print(0)

Submission status: Accepted

Solution code:
def nck(n, k):
    numer, denom = 1, 1
    for i in range(k):
        numer = numer * (n-i) % MOD
        denom = denom * (k-i) % MOD
    return numer * pow(denom, MOD-2, MOD) % MOD

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

i = 2 * y - x
j = 2 * x - y
if i % 3 != 0 or j % 3 != 0 or i < 0 or j < 0:
    print(0)
else:
    i, j = i // 3, j // 3
    print(nck(i+j, min(i, j)))

Submission status: Accepted

Solution code:
def pre_combi1(n, p):
    fact = [1]*(n+1)  # fact[n] = (n! mod p)
    factinv = [1]*(n+1)  # factinv[n] = ((n!)^(-1) mod p)
    inv = [0]*(n+1)  # factinv 計算用
    inv[1] = 1
    # 前処理
    for i in range(2, n + 1):
        fact[i]= fact[i-1] * i % p
        inv[i]= -inv[p % i] * (p // i) % p
        factinv[i]= factinv[i-1] * inv[i] % p
    return fact, factinv

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

import sys
x,y=map(int,input().split())
if (x+y)%3 > 0:
  print(0)
  sys.exit()
n=(x+y)//3
r=x-n
f,inv=pre_combi1(n,1000000007)
print(combi1(n,r,1000000007,f,inv))

Submission status: Accepted

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

def comb(n,r,mod):
    n1 = n+1
    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 (x+y)%3 != 0 or (2*x-y)//3 < 0 or (2*y-x)//3 < 0:
    print(0)
else:
    n = (2*x-y)//3
    m = (2*y-x)//3
    
    print(comb(n+m,min(n,m),MOD))

Submission status: Accepted

Solution code:
def mod_inverse(x, mod):
    return pow(x, mod - 2, mod)


# return nCk % mod
# it takes O(k)
def mod_comb(n, k, mod):
    numer, denom = 1, 1
    for i in range(k):
        numer = numer * ((n - i) % mod) % mod
        denom = denom * ((i + 1) % mod) % mod

    return numer * mod_inverse(denom, mod) % mod


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

    t1, t2 = 2 * Y - X, 2 * X - Y
    if t1 % 3 != 0 or t2 % 3 != 0 or t1 < 0 or t2 < 0:
        print(0)
        return

    a, b = t1 // 3, t2 // 3
    print(mod_comb(a + b, a, mod))


main()

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
def comb(n,m,p=10**9+7):
    if n < m : return 0
    if n < 0 or m < 0:return 0
    m = min(m, n-m)
    top = bot = 1
    for i in range(m):
        top = top*(n-i) % p
        bot = bot*(i+1) % p
    bot = pow(bot, p-2, p)
    return top*bot % p
if 1/2 <= y/x <= 2 and (x+y)/3 % 1 == 0:
    yy = int((x+y)/3)
    u = int(y - yy)
    r = int(yy - u)
    print(comb(yy,r)%(10**9+7))
else:
    print(0)

Submission status: Accepted

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

A = (2*Y - X)/3
B = (2*X - Y)/3
if (2*Y - X) % 3 != 0 or (2*X - Y) % 3 != 0 or A < 0 or B < 0:
    ans = 0
    print(ans)
else:
    A = int(A)
    B = int(B)
    p = 10**9 + 7
    def comb(n, r, p):
        num1, num2 = 1, 1
        for i in range(r):
            num1 *= n-i
            num2 *= i+1
            num1 %= p
            num2 %= p
        return int(num1 * pow(num2, p-2, p))
    ans = comb(A+B, A, p)
    print(ans % p)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc145/tasks/abc145_d


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

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

x = (2*Y - X) // 3
y = (2*X - Y) // 3

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

n = x + y
r = x


mod = 10**9 + 7
f = 1
for i in range(1, n + 1):
    f = f*i % mod
fac = f
f = pow(f, mod-2, mod)
facinv = [f]
for i in range(n, 0, -1):
    f = f*i % mod
    facinv.append(f)
facinv.append(1)

print(fac * facinv[r] * facinv[n - r] % mod)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc145/tasks/abc145_d


class Combination:                                      # 計算量は O(n_max + log(mod))
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):                     # 階乗(= n_max !)の逆元を生成
            f = f * i % mod                             # 動的計画法による階乗の高速計算
            fac.append(f)                               # fac は階乗のリスト
        f = pow(f, mod-2, mod)                          # 階乗から階乗の逆元を計算。フェルマーの小定理より、　a^-1 = a^(p-2) (mod p) if p = prime number and p and a are coprime
                                                        # python の pow 関数は自動的に mod の下での高速累乗を行ってくれる
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):                   # 上記の階乗の逆元から階乗の逆元のリストを生成（＝ facinv ）
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    # "n 要素" は区別できる n 要素
    # "k グループ" はちょうど k グループ

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def C(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

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

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

x = (2*Y - X) // 3
y = (2*X - Y) // 3

n = x + y
r = x


mod = 10**9 + 7
f = 1
for i in range(1, n + 1):
    f = f*i % mod
fac = f
f = pow(f, mod-2, mod)
facinv = [f]
for i in range(n, 0, -1):
    f = f*i % mod
    facinv.append(f)
facinv.append(1)

comb = Combination(n)
print(comb.C(n,r))

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def combinations_mod(n, r, mod=1000000007):
    """Returns nCr in mod."""
    r = min(r, n - r)
    combs = 1
    for i, j in zip(range(n - r + 1, n + 1), range(1, r + 1)):
        combs *= (i % mod) * pow(j, mod - 2, mod)
        combs %= mod
    return combs


def main():
    X, Y = NMI()
    if (2*Y - X)%3 or (2*X - Y)%3:
        print(0)
        exit()

    A = (2*Y - X) // 3
    B = (2*X - Y) // 3
    if A < 0 or B < 0:
        print(0)
        exit()
    print(combinations_mod(A+B, A))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def modinv(a, m):
    b, u, v = m, 1, 0
    while(b):
        a, b, u, v = b, a%b, v, u-(a//b)*v
    return u % m

def modfac(n, m):
    res = [1] * (n+1)
    for i in range(2, n+1):
        res[i] = res[i-1] * i % m
    return res

def modc(n, r, m):
    lst = modfac(n, m)
    return lst[n] * modinv(lst[r], m) * modinv(lst[n-r], m) % m

x, y = map(int, input().split())
if (x+y)%3 == 0 and x >= (x+y)//3 and x <= 2*(x+y)//3:
    print(modc((x+y)//3, x-(x+y)//3, 1000000007))
else:
    print(0)

Submission status: Accepted

Solution code:
import sys
 
X, Y = map(int, input().split())
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

if 2*Y < X or 2*X < Y or (X+Y)%3 != 0:
  print(0)
  sys.exit()
  
n1 = (2*Y-X)//3
n2 = (2*X-Y)//3

print(combination(n1+n2, min(n1, n2), 10**9+7))

Submission status: Accepted

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

diff = abs(x - y)
large = max(x, y)
small = min(x, y)

if (small * 2 < large):
    print(0)
    exit()


# ans = diff
large -= diff * 2
small -= diff

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


num = int(small / 3)
nn = int(num * 2 + diff)
# rr = num

factorial = [0] * (nn + 1)
factorial[0] = 1
for i in range(nn):
    factorial[i + 1] = factorial[i] * (i + 1) % p


def cmb(n, k):
    # if (n == 1 or k == 1):
    if (n == 0 or k == 0):
        return 1
    if (n < 0 or k < 0):
        return 0

    return factorial[n] * pow(factorial[n - k], p - 2, p) * pow(factorial[k], p - 2, p) % p


ans = cmb(int(nn), int(num))
print(int(ans))

Submission status: Accepted

Solution code:
def comb_mod(n,r,m):
    ans = 1
    for i in range(1,r+1):
        ans *= (n-i+1) % m
        ans *= pow(i,m-2,m) % m
        ans = ans % m
    return ans
x,y = map(int,input().split())
m = 10**9+7
n = (x+y)//3
c = 0
if x*0.5 <= y <= 2*x and (x+y)%3 == 0:
    r = x - n
    c = comb_mod(n,r,m)
else:
    ans = 0
print(c)

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
m = 10**9+7
n = (x+y)//3
c = 0
if x*0.5 <= y <= 2*x and (x+y)%3 == 0:
    r = x - n
    c = 1
    for i in range(1,r+1):
        c *= (n-i+1) % m
        c *= pow(i,m-2,m)
        c = c % m
else:
    ans = 0
print(c)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

MOD = 10**9+7

class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

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

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

Submission status: Accepted

Solution code:
import sys

p=10**9+7

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

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

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

A=1
for i in range(1,a+1):
    A=A*i
    A=A%p
B=1
for i in range(1,b+1):
    B=B*i
    B=B%p

AB=1
for i in range(1,a+b+1):
    AB=AB*i
    AB=AB%p

C=(AB*pow(A,p-2,p)*pow(B,p-2,p))%p

print(C)

Submission status: Accepted

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

X, Y = map(int, input().split())
mod = 10 ** 9 + 7
if (X + Y) % 3:
    print(0)
else:
    if 2 * Y - X < 0 or 2 * X - Y < 0:
        print(0)
    else:
        n = (X + Y) // 3
        r = (2 * Y - X) // 3
        print(comb(n, r))

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import queue
from collections import deque
from fractions import Fraction

def comb(n, r, mod):
    ans = 1
    for i in range(max(r, n - r) + 1, n + 1):
        ans *= i
        ans %= mod
    for i in range(1, min(r, n - r) + 1):
        ans *= pow(i, mod - 2, mod)
        ans %= mod
    return ans


def main():
    x, y = map(int, input().split())

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

    tate = (2 * y - x) // 3
    yoko = (2 * x - y) // 3

    if tate < 0 or yoko < 0:
        print(0)
        sys.exit()

    mod = 10 ** 9 + 7
    ans = comb(tate + yoko, tate, mod)
    print(ans)







if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def mod_com_once(n, r, MOD):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    r = min(r, n - r)
    numer = denom = 1
    for i in range(n - r + 1, n + 1):
        numer = numer * i % MOD
    for i in range(1, r + 1):
        denom = denom * i % MOD
    return numer * pow(denom, MOD - 2, MOD) % MOD


def main():
    MOD = 1000000007
    X, Y = map(int, readline().split())

    p = (2 * X - Y) // 3
    q = (-X + 2 * Y) // 3

    if (X + Y) % 3 or p < 0 or q < 0:
        print(0)
        return

    print(mod_com_once(p + q, p, MOD))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def mod_com_once(n, r, MOD):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    r = min(r, n - r)
    numer = denom = 1
    for i in range(1, r + 1):
        numer = numer * (n - r + i) % MOD
        denom = denom * i % MOD
    return numer * pow(denom, MOD - 2, MOD) % MOD


def main():
    MOD = 1000000007
    X, Y = map(int, readline().split())

    p = (2 * X - Y) // 3
    q = (-X + 2 * Y) // 3

    if (X + Y) % 3 or p < 0 or q < 0:
        print(0)
        return

    print(mod_com_once(p + q, p, MOD))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def choose(n, a):
    x, y = 1, 1
    for i in range(a):
        x = x * (n - i) % MD
        y = y * (i + 1) % MD
    return x * pow(y, MD - 2, MD) % MD

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

Submission status: Accepted

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

MOD = 10**9 + 7

def comb(n, r):
    if n < r or n < 0 or r < 0:
        return 0

    n += 1
    over = 1
    under = 1
    for i in range(1,r + 1):
      over = over * (n - i) % MOD
      under = under * i % MOD
    return over * pow(under, MOD - 2, MOD) % MOD

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

Submission status: Accepted

Solution code:
import numpy as np
import sys
x, y = map(int, input().split())

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

# 手数
n = (x + y) // 3
x -= n
y -= n

MOD = 10**9 + 7


def prepare(n, MOD):
    nrt = int(n ** 0.5) + 1
    nsq = nrt * nrt
    facts = np.arange(nsq, dtype=np.int64).reshape(nrt, nrt)
    facts[0, 0] = 1
    for i in range(1, nrt):
        facts[:, i] = facts[:, i] * facts[:, i - 1] % MOD
    for i in range(1, nrt):
        facts[i] = facts[i] * facts[i - 1, -1] % MOD
    facts = facts.ravel().tolist()

    invs = np.arange(1, nsq + 1, dtype=np.int64).reshape(nrt, nrt)
    invs[-1, -1] = pow(facts[-1], MOD - 2, MOD)
    for i in range(nrt - 2, -1, -1):
        invs[:, i] = invs[:, i] * invs[:, i + 1] % MOD
    for i in range(nrt - 2, -1, -1):
        invs[i] = invs[i] * invs[i + 1, 0] % MOD
    invs = invs.ravel().tolist()

    return facts, invs


facts, invs = prepare(n, MOD)

print(facts[n] * invs[x] * invs[y] % MOD)

Submission status: Accepted

Solution code:
import numpy as np
import sys
x, y = map(int, input().split())

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

# 手数
n = (x + y) // 3
x -= n
y -= n

MOD = 10**9 + 7

# モジュラ逆数戦法
def prepare(n, MOD):

    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f

    inv = pow(f, MOD - 2, MOD)
    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


fact, invs = prepare(n, MOD)

print(fact * invs[x] * invs[y] % MOD)

Submission status: Accepted

Solution code:
import numpy as np
import sys
x, y = map(int, input().split())

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

# 手数
n = (x + y) // 3
x -= n
y -= n


MOD = 10**9 + 7


def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f

    inv = pow(f, MOD - 2, MOD)
    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


fact, invs = prepare(n, MOD)

print(fact * invs[x] * invs[y] % MOD)

Submission status: Accepted

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

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

# 手数
n = (x + y) // 3
x -= n
y -= n


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


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

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

print(cmb(x + y, x, MOD))

Submission status: Accepted

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

Submission status: Accepted

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

MD = pow(10, 9) + 7

def choose(n, a):
    x, y = 1, 1
    for i in range(a):
        x = x * (n - i) % MD
        y = y * (i + 1) % MD
    return x * pow(y, MD - 2, MD) % MD


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

if a < 0 or b < 0 or (X+Y) % 3 != 0:
    print(0)
    import sys
    sys.exit()

print(choose(a+b, min(a,b)))

Submission status: Accepted

Solution code:
X, Y = map(int, input().split())
a = 2*Y-X
b = 2*X-Y

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

if a%3==0 and b%3==0 and a>=0 and b>=0:
    a //= 3 
    b //= 3
    print(combination(a+b, a))
else:
    print(0)

Submission status: Accepted

Solution code:
N=10**9+7
x , y = map(int, input().split())
a=(2*x-y)//3
b=(2*y-x)//3

if 2*a+b!=x:
    print(0)
    exit()

n=a+b
r=a

def fac(n,r,N):
    ans=1
    for i in range(r):
        ans=ans*(n-i)%N
    return ans

def combi(n,r,N):
    if n<r or n<0 or r<0:
        ans = 0
        return ans
    r= min(r, n-r)
    ans = fac(n,r,N)*pow(fac(r,r,N),N-2,N)%N
    return ans

ans = combi(n,r,N)
print(ans)

Submission status: Accepted

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

def modinv(a):
	return pow(a,MOD-2,MOD)

x=(2*Y-X)//3
y=(2*X-Y)//3

if (2*Y-X)%3!=0 or (2*X-Y)%3!=0 or x<0 or y<0:
	print(0)
else:
	r=1
	n=x+y
	k=min(x,y)
	for i in range(k):
		r*=(n-i)
		r*=modinv(i+1)
		r%=MOD
	print(r)

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
if not((2*x-y)%3==0 and (-x+2*y)%3==0):
  print(0)
  exit()
p=(2*x-y)//3
q=(-x+2*y)//3

def cmb(n,r,mod):
  if r<0 or n<r:
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod
n=p+q
mod=10**9+7
g1=[1,1]#元table
g2=[1,1]#逆元table
inv=[0,1]#逆元table計算用
for i in range(2,n+1):
  g1.append(g1[-1]*i%mod)
  inv.append(-inv[mod%i]*(mod//i)%mod)
  g2.append(g2[-1]*inv[-1]%mod)

print(cmb(n,p,mod))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    MOD = 10 ** 9 + 7

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

    if (X + Y) % 3:
        print(0)
        return

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

    def choose(n, a, mod):
        x, y = 1, 1
        for i in range(a):
            x = x * (n - i) % mod
            y = y * (i + 1) % mod
        return x * pow(y, mod - 2, mod) % mod

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

    ans = choose(a + b, min(a, b), mod=MOD)
    print(ans)


if __name__ == '__main__':
    main()