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:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
        result %= 10 ** 9 + 7
    return result

x, y = readmi()
if (x + y) % 3 != 0:
    print(0)
else:
    n = (x + y) // 3
    x -= n
    y -= n
    if x < 0 or y < 0:
        print(0)
    else:
        a = cmb(x + y, x)
        print(a)

Submission status: Accepted

Solution code:
def mod_inv(a, m):
    return pow(a, m-2, m)


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

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

n = (X + Y) // 3
nx, ny = X - n, Y - n

if nx < 0 or ny < 0:
    print(0)
    exit()

ans = 1
for i in range(nx + 1, nx + ny + 1):
    ans = ans * i % MOD
for i in range(1, ny + 1):
    ans = ans * mod_inv(i, MOD) % MOD

print(ans)

Submission status: Accepted

Solution code:
def extgcd(a, b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2] // w[2]
        r2 = w
        w2 = [r[0] - q * w[0], r[1] - q * w[1], r[2] - q * w[2]]
        r = r2
        w = w2
    return [w[0], w[1]]


def mod_inv(a, m):
    x = extgcd(a, m)[0]
    return (m + x % m) % m


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

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

n = (X + Y) // 3
nx, ny = X - n, Y - n

if nx < 0 or ny < 0:
    print(0)
    exit()

ans = 1
for i in range(1, nx + ny + 1):
    ans = ans * i % MOD
for i in range(1, nx + 1):
    ans = ans * mod_inv(i, MOD) % MOD
for i in range(1, ny + 1):
    ans = ans * mod_inv(i, MOD) % MOD

print(ans)

Submission status: Accepted

Solution code:
X, Y = map(int, input().split())
def comb(n, r, mod=10 ** 9 + 7):
  n1 = n + 1
  r = min(n, 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 coordinates increase by 3 per one move
# x + y should be factor of 3
ans = 0
if (X + Y) % 3 == 0 and 2 * Y >= X and 2 * X >= Y:
  # The number of up move and right move
  up, right = (2 * Y - X) // 3, (2 * X - Y) // 3
  # up + right = (X + Y) % 3
  ans = comb(up + right, right)
print(ans)

Submission status: Accepted

Solution code:
def combination(n, r, mod):
    numerator, denominator = 1, 1
    for _ in range(r):
        numerator = numerator * n % mod
        denominator = denominator * r % mod
        n -= 1
        r -= 1
    return numerator * pow(denominator, mod - 2, mod) % mod


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

m, n = (2 * x - y) // 3, (2 * y - x) // 3
if m < 0 or n < 0:
    answer = 0
    print(answer)
    exit()

mod = 10**9 + 7
answer = combination(m + n, m, mod)
print(answer)

Submission status: Accepted

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

class BiCoeff(object):
    def __init__(self, MAX, m):
        super(BiCoeff, self).__init__()
        fac = [0]*MAX
        finv = [0]*MAX
        inv = [0]*MAX

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

        self.MAX = MAX
        self.m = m
        self.fac = fac
        self.finv = finv
        self.inv = inv

    def calc(self,n,k):
        if n<k:
            return 0
        if n<0 or k<0:
            return 0
        return (self.fac[n] * (self.finv[k]*self.finv[n-k])%self.m)%self.m



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

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

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

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

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

MOD = 10**9 + 7
coeff = BiCoeff(10**6+10, MOD)

print(coeff.calc(n+m,n))

Submission status: Accepted

Solution code:
import sys
bbn=1000000007
	
#+++++
#knight
#https://atcoder.jp/contests/abc145/tasks/abc145_d


def kk(n,a_mod=1):
	ret=1
	for i in range(1, n+1):
		ret = (ret * i) % a_mod
	return ret
	
def pp(n,m,a_mod=1):
	ret=1
	for i in range(m):
		ret *= n - i
		ret = ret % a_mod
	return ret

def modinv(a,m):
	b=m
	u=1
	v=0
	
	while b > 0:
		t = a //b
		a = a - (t * b)
		a,b = b,a
		u = u - (t * v)
		u,v=v,u
	
	u = u % m
	if u < 0:
		u+=m
	return u
	
def cnv(a_total, a_sub,a_mod):
	ret = pp(a_total,a_sub,a_mod)
	ww = kk(a_sub,a_mod)
	ret *= modinv(ww,a_mod)
	ret %= a_mod
	return ret
	
	

def main():
	x,y = map(int, input().split())
	if (x+y)%3!=0:
		return 0
	
	if x > y:
		x,y=y,x
	
	if x*2 < y:
		return 0
	
	turn = (x+y)//3
	xp2=x-turn
	return cnv(turn, xp2, bbn)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
def num_combinations_mod2(n, r, mod=10 ** 9 + 7):
    # mod must be a prime.
    # nCr = (n! / (n-r)!) * (r!)^-1
    # a = n! / (n-r)!
    # b = (r!)^-1
    if r > n:
        return 0
    if r < 0 or n < 0:
        return 0
    r = min(r, n - r)
    a = 1
    b = 1
    for i in range(1, r + 1):
        a = a * (n + 1 - i) % mod
        b = b * i % mod
    return a * pow(b, mod - 2, mod) % mod


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

    total = (x + y) // 3
    n = (2 * x - y) // 3
    m = total - n
    answer = num_combinations_mod2(m+n, n, 10**9+7)
    return answer


X, Y = map(int, input().split(" "))
print(main(X, Y))

Submission status: Accepted

Solution code:
def num_combinations_mod(n, r, mod, num_max=10**6):
    # if this functions is called twice or more, init process should be placed before calling this function to
    # save time.
    if r > n:
        return 0
    elif r == n:
        return 1
    elif r < 0 or n < 0:
        return 0
    f_mod, f_mod_inv = num_combinations_mod_init(num_max, mod)
    return f_mod[n] * (f_mod_inv[r] * f_mod_inv[n-r] % mod) % mod


def num_combinations_mod_init(num_max, mod):
    factorials_mod = dict()
    factorials_mod_inv = dict()
    factorials_mod[0] = 1
    factorials_mod[1] = 1
    factorials_mod_inv[0] = 1
    factorials_mod_inv[1] = 1
    mod_inv = dict()
    mod_inv[1] = 1
    for i in range(2, num_max):
        factorials_mod[i] = factorials_mod[i - 1] * i % mod
        mod_inv[i] = mod - mod_inv[mod % i] * (mod // i) % mod
        factorials_mod_inv[i] = factorials_mod_inv[i - 1] * mod_inv[i] % mod
    return factorials_mod, factorials_mod_inv


def get(num1, num2):
    if num1 > num2:
        num = num2
    else:
        num = num1
    return num_combinations_mod(num1+num2, num, 10**9+7)


def main(X, Y):
    if (X + Y) % 3 != 0:
        return 0

    total = (X + Y) // 3
    n_moveB = (2 * X - Y) // 3
    n_moveA = total - n_moveB
    answer = get(n_moveA, n_moveB)

    return answer


X, Y = map(int, input().split(" "))
print(main(X, Y))

Submission status: Accepted

Solution code:

def num_combinations_mod(n, r, mod, num_max=10**6):
    # if this functions is called twice or more, init process should be placed before calling this function to
    # save time.
    if r > n:
        return 0
    elif r == n:
        return 1
    elif r < 0 or n < 0:
        return 0
    f_mod, f_mod_inv = num_combinations_mod_init(num_max, mod)
    return f_mod[n] * (f_mod_inv[r] * f_mod_inv[n-r] % mod) % mod


def num_combinations_mod_init(num_max, mod):
    factorials_mod = dict()
    factorials_mod_inv = dict()
    factorials_mod[0] = 1
    factorials_mod[1] = 1
    factorials_mod_inv[0] = 1
    factorials_mod_inv[1] = 1
    mod_inv = dict()
    mod_inv[1] = 1
    for i in range(2, num_max):
        factorials_mod[i] = factorials_mod[i - 1] * i % mod
        mod_inv[i] = mod - mod_inv[mod % i] * (mod // i) % mod
        factorials_mod_inv[i] = factorials_mod_inv[i - 1] * mod_inv[i] % mod
    return factorials_mod, factorials_mod_inv


def get(num1, num2):
    if num1 > num2:
        num = num2
    else:
        num = num1
    return num_combinations_mod(num1+num2, num, 10**9+7)


def main(X, Y):
    if (X + Y) % 3 != 0:
        return 0

    total = (X + Y) // 3
    n_moveB = (2 * X - Y) // 3
    n_moveA = total - n_moveB
    answer = get(n_moveA, n_moveB)

    return answer


X, Y = map(int, input().split(" "))
print(main(X, Y))

Submission status: Accepted

Solution code:
#べき乗関数powを使った逆元の計算
def modinv2(a,m):
    return pow(a,m-2,m)
 
X,Y = map(int,input().split())
 
X,Y = min(X,Y),max(X,Y)
 
if (X+Y)%3 != 0 or X*2-Y < 0:
    ans = 0
else:
    a = (2*X-Y)//3
    b = (2*Y-X)//3
    m = 10**9+7
    ans = 1
    for i in range(b+1,a+b+1):
        ans = ans*i%m
    for i in range(1,a+1):
        ans = ans*modinv2(i,m)%m
print(ans)

Submission status: Accepted

Solution code:
#拡張ユークリッド互除法
#ax+by=1の1つの解(gcd(a,b)=1)
#仕組みをちゃんと理解していない
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def modinv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m #負の値を返さないように

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

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

if (X+Y)%3 != 0 or X*2-Y < 0:
    ans = 0
else:
    a = (2*X-Y)//3
    b = (2*Y-X)//3
    m = 10**9+7
    ans = 1
    for i in range(b+1,a+b+1):
        ans = ans*i%m
    for i in range(1,a+1):
        ans = ans*modinv(i,m)%m
print(ans)

Submission status: Accepted

Solution code:
#べき乗関数powを使った逆元の計算
def modinv2(a,m):
    return pow(a,m-2,m)

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

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

if (X+Y)%3 != 0 or X*2-Y < 0:
    ans = 0
else:
    a = (2*X-Y)//3
    b = (2*Y-X)//3
    m = 10**9+7
    ans = 1
    for i in range(b+1,a+b+1):
        ans = ans*i%m
    for i in range(1,a+1):
        ans = ans*modinv2(i,m)%m
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def comb(n, k):
    N = n + k + 1
    fact = [1] * (N + 1)
    rfact = [1] * (N + 1)
    r = 1
    for i in range(1, N + 1):
        fact[i] = r = r * i % MOD

    rfact[N] = r = pow(fact[N], MOD - 2, MOD)
    for i in range(N, 0, -1):
        rfact[i - 1] = r = r * i % MOD
    return fact[n] * rfact[k] * rfact[n - k] % MOD


X, Y = map(int, input().split())
x = 2 * X - Y
y = 2 * Y - X

if (x % 3 and y % 3) or x < 0 or y < 0:
    print(0)
else:
    xx = x // 3
    yy = y // 3
    print(comb(xx + yy, xx))

Submission status: Accepted

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

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

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

MOD = int(1.0e+9 + 7)
N = int(7.0e+5) # 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)

if((2 * y - x) % 3 != 0 or (2 * x - y) % 3 != 0 or
   (2 * y - x) < 0 or (2 * x - y) < 0):
    print(0)
else:
    print(cmb(X + Y, Y, MOD))

Submission status: Accepted

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

MOD = int(1.0e+9 + 7)
DP_max = 3333334

DP = []

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

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

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

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

if((2 * y - x) % 3 != 0 or (2 * x - y) % 3 != 0 or
   (2 * y - x) < 0 or (2 * x - y) < 0):
    print(0)
else:
    print(cmb(X + Y, Y, MOD))

Submission status: Accepted

Solution code:
from functools import lru_cache
MOD = 10**9 + 7

def is_prime(n):
    assert n >= 1,  'Argument Error! n is "1 <= n".'
    for i in range(2, n + 1):
        if i ** 2 > n:
            break
        if n % i == 0:
            return False
    return n != 1

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

@lru_cache(maxsize=MOD)
def modinv(a, mod):
    g, x, y = xgcd(a, mod)
    assert g == 1, 'modular inverse does not exist'
    return x % mod

factorials = [1]
def factorial(n, mod):
    # n! % mod
    assert n >= 0, 'Argument Error! n is "0 <= n".'
    if len(factorials) < n+1:
        for i in range(len(factorials), n+1):
            factorials.append(factorials[-1]*i % mod)
    return factorials[n]

def comb(n, r, mod):
    # nCr % mod
    assert n >= 0, 'Argument Error! n is "0 <= n".'
    assert n >= r >= 0, 'Argument Error! r is "0 <= r <= n".'
    
    return perm(n, r, mod) * modinv(factorial(r, mod), mod) % mod

def comb_with_repetition(n, r, mod):
    # nHr % mod
    assert n >= 0, 'Argument Error! n is "0 <= n".'
    assert n+r-1 >= r >= 0, 'Argument Error! r is "0 <= r <= n+r-1".'
    
    return comb(n+r-1, r, mod)

def perm(n, r, mod):
    # nPr % mod
    assert n >= 0, 'Argument Error! n is "0 <= n".'
    assert n >= r >= 0, 'Argument Error! r is "0 <= r <= n".'
    return factorial(n, mod) * modinv(factorial(n-r, mod), mod) % mod

x, y = sorted(list(map(int, input().split())))
MOD = 10 ** 9 + 7
q, r = divmod(x+y, 3)

if r != 0:
    print(0)
else:
    try:
        print(comb(q, y - q, MOD))
    except AssertionError:
        print(0)

Submission status: Accepted

Solution code:
x, y = map(int, input().split())
if 2 * x < y or 2 * y < x:
    print(0)
    exit()
elif (x + y) % 3 != 0:
    print(0)
    exit()

fix_x, fix_y = 0, 0

tmp_x, tmp_y = x, y
while True:
    if tmp_x == 2 * tmp_y:
        break
    tmp_x -= 1
    tmp_y -= 2
    fix_y += 1

tmp_x, tmp_y = x, y
while True:
    if tmp_x * 2 == tmp_y:
        break
    tmp_x -= 2
    tmp_y -= 1
    fix_x += 1


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

a = cmb(fix_x + fix_y, fix_x,mod)
print(a)

Submission status: Accepted

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

if (x+y) % 3 != 0:
    print(0)
else:
    mod = int(1e9 + 7)
    n = (2*y - x) // 3
    m = y - 2 * n
    if n < 0 or m < 0:
        print(0)
    else:
        f = [1]
        for i in range(1, n+m+1):
            f.append(f[-1] * i % mod)
        ans = f[n+m] * pow(f[n] * f[m], mod - 2, mod) % mod
        print(ans)

Submission status: Accepted

Solution code:
def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % mod


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

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

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

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

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

ans = cmb(int(m_n), int(n), mod)
print(ans)

Submission status: Accepted

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

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

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


if a+2*b==x and b+2*a==y and a>=0 and b>=0:
    ans=fact(n,mod) * pow(fact(b,mod),mod-2,mod)*pow(fact(a,mod),mod-2,mod)
    print(ans%mod)
else:
    print("0")

Submission status: Accepted

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


sys.setrecursionlimit(10**8)

MOD = 10 ** 9 + 7


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

if a != int(a) or b != int(b):
    print(0)
    sys.exit(0)


def factorial(x, p):
    a = 1
    for i in range(1, x + 1):
        a *= i
        a %= p
    return a


def comb(a, b, p):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= factorial(a, p)
    c *= pow(factorial(b, p), p - 2, p)
    c *= pow(factorial(a - b, p), p - 2, p)
    return c % p


print(comb(int(a+b), int(a), MOD))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

fac = [-1] * (10**7+1)
finv = [-1] * (10**7+1)
inv = [-1] * (10**7+1)

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

def initNCMMod(limit):
    for i in range(2, limit):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod

initNCMMod(666670)

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

def main():
    X, Y = LI()
    if (2 * X - Y) % 3 > 0:
        ans = 0
    elif (2 * Y - X) % 3 > 0:
        ans = 0
    else:
        i = (2 * X - Y) // 3
        j = (2 * Y - X) // 3
        ans = NCMMod(i+j, i)
    print(ans)
    return

'''
def main():
    X, Y = LI()
    g = [[0 for _ in range(X+1)] for __ in range(Y+1)]
    def reachable(row, col):
        if row > Y or col > X:
            return 0
        if row == Y and col == X:
            return 1
        ans = reachable(row + 1, col + 2) % mod + reachable(row + 2, col + 1) % mod
        ans = ans % mod
        return ans
    print(reachable(0, 0))
'''
main()

Submission status: Accepted

Solution code:
import sys


def alg_combination_mod(n, r, mod):
    r = min(n - r, r)
    if r == 0:
        return 1
    else:
        denominator = 1
        for i in range(n, n - r, -1):
            denominator = (denominator * i) % mod
        molecule = 1
        for i in range(1, r + 1):
            molecule = (molecule * i) % mod
        return denominator * pow(molecule, mod - 2, mod) % mod


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    x, y = list(map(int, readline().split()))
    if (x + y) % 3 == 0:
        t = (x + y) // 3
        if x >= 0 and y >= 0:
            for i in range(t + 1):
                if i + 2 * (t - i) == x and (t - i) + i * 2 == y:
                    print(alg_combination_mod(t, i, mod))
                    exit()
            print(0)
        else:
            print(0)
    else:
        print(0)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

ans = 0
[x,y] = inpl()

alpha = ( 2*x-y )//3
beta = (2*y-x)//3
alpha_c = ( 2*x-y )%3
beta_c = (2*y-x)%3

MAX_NUM = 10**6 + 1
MOD = 10**9+7

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

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

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

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

ans = combinations(alpha+beta,alpha) if alpha_c == 0 and beta_c == 0 else 0
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial
sys.setrecursionlimit(200000)
input = sys.stdin.readline

X, Y, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

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

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

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

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

print(combination(a+b,a))

Submission status: Accepted

Solution code:
mod = 1000000007
x, y = map(int, input().split())
x, y = min(x, y), max(x, y)

if 2*x < y or (2*x-y)%3 != 0:
  print(0)
else:
  b = (2*x-y)//3
  a = x-2*b
  afact, bfact, abfact = 1, 1, 1
  for i in range(1, a+1):
    afact = (afact * i)%mod
  for i in range(1, b+1):
    bfact = (bfact * i)%mod
  for i in range(1, a+b+1):
    abfact = (abfact * i)%mod
    
  print((abfact * pow(afact, mod-2, mod) * pow(bfact, mod-2, mod))%mod)

Submission status: Accepted

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

def c(n,k,m):
    n1, k = n+1, min(k, n-k)
    numer = denom = 1
    for i in range(1,k+1):
        numer = numer*(n1-i)%m
        denom = denom*i%m
    return numer*pow(denom,m-2,m)%m

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

    if a<0 or b < 0:
        print(0)
    else:
        ans = c(a+b,a,mod)
        print(ans)

Submission status: Accepted

Solution code:
MOD = int(1e9+7)

def fast_power(b, e):
    res = 1
    while e > 0:
        if e % 2 == 1:
            res = res * b % MOD
        b = b * b % MOD
        e >>= 1
    return res

def mod_inverse(n):
    return fast_power(n, MOD-2)
def mul(x, y):
    return ((x % MOD) * (y % MOD) % MOD + MOD) % MOD
def multiply(x, y, z):
    return mul(mul(x, y), z)

def nCr(n, r):
    if r == 0:
        return 1
    fac = [1] * (n+1)
    for i in range(1, n+1):
        fac[i] = fac[i-1] * i % MOD
    # n! / (r! * (n-r)!)
    return multiply(fac[n], mod_inverse(fac[r]), mod_inverse(fac[n-r]))

x, y = map(int, input().split())
n = (2*x-y) // 3
m = (2*y-x) // 3
if min(n, m) < 0 or (x+y)%3 != 0:
    print(0)
    exit()
print(nCr(m+n, n))

Submission status: Accepted

Solution code:
def ints():
  return [int(x) for x in input().split()]
def readi():
  return int(input())
X, Y = ints()

start = (0, 0)
end = (X, Y)
memo = {}
MOD = 10**9+7
N = 10**6+1
fact = [None]*N
fact[0] = 1
for i in range(1, N):
  fact[i] = fact[i-1]*i % MOD

def no():
  print(0)
  exit()

def inv(x):
  res = 1
  k = MOD-2
  y = x
  while k>0:
    if k%2==1:
      res = (res * y) % MOD
    y = (y * y) % MOD
    k //= 2
  return res

def C(n, k):
  a = fact[n]
  b = fact[k]
  c = fact[n-k]
  bc = (b*c) % MOD

  return (a * inv(bc)) % MOD

x = X+Y
y = -X+Y

if x%3>0:
  no()

xn = x//3
yn= (y+xn)//2
if yn<0 or yn>xn:
  no()
print(C(xn, yn))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline
#再起のlimitを上げる
import sys
sys.setrecursionlimit(4100000)

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

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

import math
#組み合わせ kumiawase
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

m = (2 * x - y)//3
n = x - m * 2
if m < 0 or n < 0:
    print(0)
    import sys
    sys.exit()

print(combination(n+m,n))

Submission status: Accepted

Solution code:
import numpy as np
from math import factorial

# combination の実装は以下参照
# https://qiita.com/derodero24/items/91b6468e66923a87f39f#%E7%95%AA%E5%A4%96%E7%B7%A8

from operator import mul
from functools import reduce

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 = [int(i) for i in input().split()]

points = np.array([[1, 2], [2, 1]])
values = np.array([x, y])
a, b = np.linalg.solve(points, values).tolist()

if a.is_integer() and b.is_integer():
  a = int(a)
  b = int(b)

  r = a if a < b else b

  print(cmb(a+b, r, 10 ** 9 + 7))

else:
    print(0)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
def add(a, b):
  return (a + b) % MOD
def sub(a, b):
  return (a - b) % MOD
def mul(a, b):
  return ((a % MOD) * (b % MOD)) % MOD
def div(a, b):
  return ( (a % MOD) * (power(b, MOD)) ) % MOD
def power(a, b):
  return pow(a, b, MOD)

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())
N = (x + y) // 3 + 1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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


if (x+y) % 3 != 0:
  print(0)
else:
  n = (x+y) // 3
  d = abs(x - y)
  r = (n-d) // 2
  print(cmb(n, r, MOD))

Submission status: Accepted

Solution code:
# ABC-145-D
X, Y = map(int, input().split())
ans = 0
mod = 10**9 + 7

# 組み合わせを出す関数
# https://qiita.com/derodero24/items/91b6468e66923a87f39f
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: 
    ans = 0
else:
    #(+1,+2)を行う回数nを求める。
    n = (2*Y - X)//3
    #(+2,+1)を行う回数mを求める。    
    m = Y - 2*n
    # 例えば、X=18, Y=6のときはnがマイナスになってしまう。
    if n < 0 or m < 0:
        ans = 0
    else:
        ans = cmb(n+m, n)
    
print(ans%mod)

Submission status: Accepted

Solution code:
# ABC-145-D
X, Y = map(int, input().split())
ans = 0
mod = 10**9 + 7

# 組み合わせを出す関数
# https://qiita.com/derodero24/items/91b6468e66923a87f39f
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: 
    ans = 0
else:
    #(+1,+2)を行う回数nを求める。
    n = (2*Y - X)//3
    #(+2,+1)を行う回数mを求める。    
    m = Y - 2*n
    if n < 0 or m < 0:
        ans = 0
    else:
        ans = cmb(n+m, n)
    
print(ans%mod)

Submission status: Accepted

Solution code:
import math

def combination(n,r,mod=10**9+7):
    n1 = n+1
    r = 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())

ans = 0

if (X+Y)%3 == 0 and 2*Y-X>=0 and 2*X-Y>=0:
    up,right = (2*Y-X)//3,(2*X-Y)//3
    ans = combination(up+right,right)

print(ans)

Submission status: Accepted

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


data = input().split(' ')
x = int(data[0])
y = int(data[1])
if(2 * x - y < 0 or 2 * y - x < 0):
    print(0)
elif((2 * x - y) % 3 != 0 or (2 * y - x) % 3 != 0):
    print(0)
else:
    a = (2 * x - y) // 3
    b = (2 * y - x) // 3

    result = cmb(a + b,a)

    print(result % (10**9 + 7))