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 collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
sys.setrecursionlimit(10 ** 9)



INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7



x, y = LI()


n = max(x, y)
fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


if (x + y) % 3 or y * 2 < x or x * 2 < y:
    print(0)
else:
    a = x - (x + y) // 3
    b = y - (x + y) // 3
    print(fac[a + b] * inv[a] % mod * inv[b] % mod)

Submission status: Accepted

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

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

move = (X + Y) // 3
yori = int(abs(X - Y))
move1 = (move - yori) // 2


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 )

Ans = cmb(move,move1,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


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

if (x+y) % 3 != 0:
    print(0)
else:
    n = (x+y)//3
    r = min(x, y) - n
    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, r, mod))

Submission status: Accepted

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

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

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

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

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

if x/2 > y or y/2 > x:
    print(0)
    exit()

maxi = max(x, y)
mini = min(x, y)

tate = 0
yoko = 0
while mini/2 != maxi:
    tate += 1
    maxi -= 2
    mini -= 1
yoko = maxi

print(modc(yoko+tate, yoko, 10**9+7))

Submission status: Accepted

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

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 2*X-Y>=0 and (2*X-Y)%3==0 and 2*Y-X>=0 and (2*Y-X)%3==0:
    n = (2*X-Y)//3
    m = (2*Y-X)//3
    res=combination(n+m,n,MOD)
    print(res)

else:print(0)

Submission status: Accepted

Solution code:
from math import factorial
X, Y = map(int, input().split())
MOD = 10 ** 9 + 7
#a(1,2)+b(2,1)
if (2 * Y - X) % 3 != 0:
  ans = 0
  print(ans)
  quit()
if (2 * X - Y) % 3 != 0:
  ans = 0  
  print(ans)
  quit()

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

if (a < 0) or (b < 0):
  ans = 0
  print(ans)
  quit()
  
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

ans = cmb(a + b,a)

print(int(ans % MOD))

Submission status: Accepted

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


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


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

if (X + Y) % 3 != 0:
    ans = 0
else:
    n = (X + Y) // 3
    r = min(X, Y) - n
    ans = cmb(n, r, mod)
print(ans)

Submission status: Accepted

Solution code:
x,y = map(int,input().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])
    return result
if all([2*y-x >= 0,2*x-y >= 0,(2*y-x)%3==0,(2*x-y)%3==0]):
  m = (2*y-x)//3
  n = (2*x-y)//3
  print((cmb(m+n,n))%(10**9+7))
else:
  print(0)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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

# a + 2b = X
# 2a + b = Y
b = (2 * X - Y) / 3  # 下2、右1移動の回数
a = X - 2 * b  # 下1、右2移動の回数
mod = 10 ** 9 + 7

if int(b) != b or int(a) != a:
    ans = 0
elif b < 0 or a < 0:
    ans = 0
else:
    fact_list = []
    N = int(a + b)
    R = int(min(a, b))

    if R != 0:
        for i in range(1, N + 1):
            if i == 1:
                fact_n = 1 % mod
            else:
                fact_n = fact_list[i - 2] * i % mod
            fact_list.append(fact_n)

        fact_n_r = fact_list[N - R - 1]
        fact_r = fact_list[R - 1]

        w = pow(fact_n_r * fact_r % mod, (mod - 2), mod)

        ans = fact_n * w % mod
    else:
        ans = 1 % mod

print(ans)

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
import math
if (a+b)%3!=0:
  print(0)
  exit()
f=(a+b)//3
g=a-f
f=f-g
if f<0 or g<0:
  print(0)
  exit()
h=min(f,g)
ans=1

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

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod
def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod
  

print(comb(f+g,min(f,g),10**9+7))

Submission status: Accepted

Solution code:
mod = 10**9 + 7

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

def main():
    x, y = map(int, input().split(' '))
    if (2*x-y) % 3 == 0 and (2*y-x) % 3 == 0:
        n = (2*x-y) // 3
        m = (2*y-x) // 3
        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+m, n, mod))
    else:
        print(0)


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    if (abs(X) + abs(Y)) % 3 != 0 or Y > 2 * X or 2 * Y < X:
        return 0

    n = (abs(X) + abs(Y)) // 3
    k = -1
    for x in range(n, 2 * n + 1):
        if Y == 3 * n - x:
            k = x - n
            break

    class Combination(object):
        """参考: https://harigami.net/contents?id=5f169f85-5707-4137-87a5-f0068749d9bb"""
        __slots__ = ['mod', 'factorial', 'inverse']

        def __init__(self, max_val_arg: int = 10**6, mod: int = 10**9 + 7):
            fac, inv = [1], []
            fac_append, inv_append = fac.append, inv.append

            for i in range(1, max_val_arg + 1):
                fac_append(fac[-1] * i % mod)

            inv_append(pow(fac[-1], mod - 2, mod))

            for i in range(max_val_arg, 0, -1):
                inv_append((inv[-1] * i) % mod)

            self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]

        def combination(self, n, r):
            if n < 0 or r < 0 or n < r:
                return 0
            return self.factorial[n] * self.inverse[r] * self.inverse[n - r] % self.mod
    return Combination().combination(n, k)

print(d_knight())

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


x, y = map(int, input().split())
if ((x + y) % 3 != 0):
	print("0")
elif (x > 2*y or y > 2*x):
	print("0")
else:
	n_x = (2 * x - y) // 3
	n_y = (2 * y - x) // 3
	n_xy = (x + y) // 3
	print(cmb(n_xy,n_x)%1000000007)

Submission status: Accepted

Solution code:
import math

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]]

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

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

def mod_fact(frm, to):
	ans = 1
	for i in range(frm, to + 1):
		ans = (ans * i) % mod
	return ans



if (x + y) % 3 == 0 and x <= y * 2 and y <= x * 2:
	n = (y * 2 - x) // 3
	m = (x + y) // 3
	#print(n, m)
	#print(mod_fact(m - n + 1, m))
	#print(mod_fact(1, n))

	print((mod_fact(m - n + 1, m) * (mod_inv(mod_fact(1, n), mod)) % mod))
else:
	print(0)

Submission status: Accepted

Solution code:
import sys

mod = 1000000007

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

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

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

def nCr(n,r):

    if r * 2 > n:
        r = n-r

    now = 1
    for i in range(r):
        now *= n - i
        now *= gdic[r-i]
        now %= mod
    return now


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

a = 0
b = 0

while X > 0 and Y > 0:

    if X > Y:
        a += 1
        X -= 2
        Y -= 1

    else:
        b += 1
        X -= 1
        Y -= 2

"""
factorial = [1]
for n in range(1, a+b):
    factorial.append(factorial[n-1]*n%mod)

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

inverseFactorial = [0] * (a+b)
inverseFactorial[a+b-1] = power(factorial[a+b-1], mod-2)
for n in range(a+b-2, -1, -1):
    inverseFactorial[n] = inverseFactorial[n+1] * (n+1) % mod

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

sys.setrecursionlimit(500000)

gdic = [0]
gyaku = 1
for i in range(min(a,b)):

    i += 2
    gdic.append(gyaku)
    gyaku = mod -gdic[mod % i] * (mod // i) % mod



if X != 0 or Y != 0:
    print (0)

else:
    print (nCr(a+b,a) % mod)

Submission status: Accepted

Solution code:
x, y = map(int, input().split())                               
                                                               
if (x+y)%3!=0:                                                 
    print(0)                                                   
    exit()                                                     
                                                               
all = (x+y)//3                                                 
                                                               
if 2*all-x==y-all:                                             
    migi = 2*all-x                                             
else:                                                          
    print(0)                                                   
    exit()                                                     
                                                               
                                                               
mod = 10**9+7 #出力の制限                                           
N = 10**6                                                      
g1 = [1, 1] # 元テーブル                                            
g2 = [1, 1] #逆元テーブル                                            
inverse = [0, 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                       
                                                               
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 0 <= migi <= all:                                           
    migi = min(migi, all-migi)                                 
    print(cmb(all, migi, mod))                                 
else:                                                          
    print(0)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
N = 10 ** 6
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

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % MOD

# nCk (mod MOD) を求める
def comb(n, k):
  return (fact[n] * rfact[k] * rfact[n-k]) % MOD

x,y = map(int, input().split())
ans = 0
if not (x + y) % 3:
  cnt = (x+y) // 3
  a = abs(x-y)
  if cnt >= a:
    r = (cnt - a) // 2
    ans = comb(cnt,r)
print(ans)

Submission status: Accepted

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

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

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

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

if (x + y) % 3 == 0 :
    moves = (x + y) // 3
    tate = (moves + abs(x - y)) // 2

    print(cmb(moves, tate, mod))
else :
    print(0)

Submission status: Accepted

Solution code:
LARGE = 10 ** 9 + 7


def solve(x, y):
    if (x + y) % 3 != 0:
        return 0
    z = (x + y) // 3
    if x < z or y < z:
        return 0
    # zC(x-z)
    r = min(x - z, y - z)
    res = 1
    for i in range(r):
        res *= z - i
        res *= pow(i + 1, LARGE - 2, LARGE)
        res %= LARGE
    return res


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


def test():
    assert solve(3, 3) == 2
    assert solve(2, 2) == 0
    assert solve(999999, 999999) == 151840682


if __name__ == "__main__":
    # test()
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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

        cnt = 0
        for n in range(X + 1):
            if (X - n) % 2 != 0:
                continue
            else:
                m = (X - n) // 2
                if 2 * n + m == Y:
                    cnt += self.cmb(n+m,n)

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

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

# Run main
if __name__ == '__main__':
    AtCoder().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 cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

n = int(all_move)
r = int(y_move)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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


print(cmb(n,r,mod))

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 = result * int(numerator[k]) % 1000000007
    return result


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

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

num = (X + Y) // 3
ans = cmb(num, X-num)
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


X,Y = map(int,input().split())
a = 2*Y-X
b = 2*X-Y
if (a//3)*3!=a or (b//3)*3!=b or a<0 or b<0:
    ans = 0
else:
    A,B = a//3,b//3
    mod = 10**9+7
    N = A+B
    g1 = [1, 1] 
    g2 = [1, 1] 
    inverse = [0, 1] 

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

    ans = cmb(A+B,A,mod)
print(ans)

Submission status: Accepted

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

import numpy as np

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

MOD = 10**9 + 7

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

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

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

if (X+Y) % 3 != 0:
    print(0)
    exit()
A = (2*X - Y) // 3
B = (2*Y - X) // 3
if A < 0 or B < 0:
    print(0)
    exit()
answer = fact[A+B] * fact_inv[A] % MOD * fact_inv[B] % MOD
print(answer)

Submission status: Accepted

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

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

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod  
  
#まず目的地まで行けるかどうか判定する。
#移動回数
n = (x+y)//3

a = -1
for i in range(n+1):
  if i+2*(n-i) == x and  2*i+(n-i) == y:
    a = i
    
if a == -1:
  print(0)
else:
  ans = comb(n,a,MOD)
  print(ans%MOD)

Submission status: Accepted

Solution code:
MOD = 10**9+7

X,Y = map(int,input().split())
if (X+Y) % 3 != 0:
    print(0)
    exit()
N = (X+Y)//3
X -= N
Y -= N
if X < 0 or Y < 0:
    print(0)
    exit()
si = 1
bo = 1
for i in range(N):
    si = (si*(i+1)) % MOD
for i in range(min(X,Y)):
    bo = (bo*(i+1)) % MOD
for i in range(N-min(X,Y)):
    bo = (bo*(i+1)) % MOD
print((si*pow(bo,MOD-2,MOD))%MOD)

Submission status: Accepted

Solution code:
import itertools
x,y=map(int,input().split())
if x>y:
    x,y=y,x
a=y-x
x-=a
y-=a*2
#print(x,y)
if x!=y or x%3!=0 or y%3!=0 or x<0 or y<0:
    print(0)
else:
    b=x//3
    ans=0
    #print(a,b)
    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+2*b, b, mod=10**9+7))

Submission status: Accepted

Solution code:
x, y = map(int, input().split())
b3 = 2*x - y
a3 = 2*y - x
if a3 % 3 != 0 or b3 % 3 != 0:
    print(0)
else:
    a = a3 // 3
    b = b3 // 3

    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 )

    ans = cmb(a+b , a, 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 + 10
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())

n = (2 * x - y) / 3
m = (2 * y - x) / 3
mod = 10 ** 9 + 7

if int(n) == n and int(m) == m:
    n = int(n)
    m = int(m)
    ans = cmb(n + m, n, mod)
    ans %= mod
    print(ans)

else:
    print(0)

Submission status: Accepted

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

MOD = 10**9 + 7

def modPow(a, b, mod):
    x = 1
    
    while b > 0:
        if b & 1:
            x = (x*a)%mod

        a = (a**2)%mod
        b //= 2

    return x

def modFact(n, mod):
    x = 1

    for i in range(2, n+1):
        x = x*i%mod

    return x


def getModInv(a, b):
    return 1 if (a == 1) else int((1-b*getModInv(b%a, a))/a%b)


def f(X, Y):
    if X*2<Y or Y*2<X or (X+Y)%3 != 0:
        return 0

    N = (X+Y)//3
    K = X - N

    return(modFact(N, MOD)*(getModInv(
        modFact(K, MOD)*modFact(N-K, MOD)%MOD, MOD))%MOD)



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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

if n >= 0 and m >= 0 and n == int(n) and m == int(m):
    print(comb(int(n + m), int(n)))
else:
    print(0)

Submission status: Accepted

Solution code:
#D
def main():
    mod=1000000007
    x,y=map(int,input().split())
    k=min(x,y//2)
    l=min(x//2,y)
    n=k+l
    
    Fact=[1]
    for i in range(1,n+1):
        Fact.append(Fact[i-1]*i%mod)
    Finv=[0]*(n+1) #階乗の逆元
    Finv[-1]=pow(Fact[-1],mod-2,mod)
    for i in range(n-1,-1,-1):
        Finv[i]=Finv[i+1]*(i+1)%mod
    def comb(n,r):
        if n<r:
            return 0
        return Fact[n]*Finv[r]*Finv[n-r]%mod
    
    ans=0
    for a in range(k+1):
        if (x-a)%2!=0:
            continue
        if (x-a)//2==y-2*a:
            b=(x-a)//2
            ans+=comb(a+b,a)
            ans%=mod
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import math
p=10**9+7
def kaijo(n):
    kotae=1
    for i in range(1,n+1):
        kotae*=i
        #kotae%=p
    kotae%=p
    return(kotae)

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

fanc=[1]*(10**6)
finv=[1]*(10**6)
inv=[1]*(10**6)

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

kanou=True

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

if(a<0 or b<0):
    kanou=False
if(a%3!=0 or b%3!=0):
    kanou=False

if(not kanou):
    print(0)
else:
    a//=3
    b//=3
    x-=a+b
    y-=a+b
    so=x+y
    #print(x,y,so)
    #t1=kaijo(so)
    #t2=kaijo(x)
    #t3=kaijo(y)
    #print(t1,t2,t3)
    #ans=t1//(t2*t3)
    #ans=ans%p
    ans=fanc[so]*finv[x]*finv[y]%p
    print(ans)

Submission status: Accepted

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

if (X + Y) % 3 == 0 : 
    n = (X + Y) // 3
    a = 2 * n - X
    
    if 0 <= a <= n and a * 2 + (n - a) == Y :
        fac = [1]
        inv = [1]
        for i in range(1, n + 1) :
            fac.append(fac[-1] * i % mod)
            inv.append(pow(fac[-1], mod - 2, mod))
        print(fac[n] * inv[n-a] * inv[a] % mod)
    
    else :
        print(0)
        
else :
    print(0)

Submission status: Accepted

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

MOD = 1000000007  # type: int

def mpow(x: int, k: int, MOD=1000000007) -> int:
    """
    x^kのmodを返します
    """
    res = 1
    y = x
    while (k):
        if(k % 2 == 1):
            res = (res * y) % MOD
        y = (y ** 2) % MOD
        k = k // 2
    return res

def mfact(MAX=200000, MOD=1000000007) -> 'List[int]':
    """
    MAXまでの階乗のmodの配列を返します
    """
    f = [1]
    for i in range(1, MAX):
        f.append(f[-1] * i % MOD)
    return f

def inv(x: int, MOD=1000000007) -> 'List[int]':
    """
    フェルマーの小定理に基づく逆元を返します
    """
    return mpow(x, MOD - 2, MOD)

def mcomb(n: int, k: int, f: 'List[int]', MOD=1000000007) -> int:
    """
    nCkのmodを返します
    """
    a = f[n]
    b = f[n-k]
    c = f[k]
    bc = (b * c) % MOD
    return (a * inv(bc)) % MOD

def solve(X: int, Y: int):
    if (2*Y-X) % 3 != 0 or (2*X-Y) % 3 != 0:
        print(0)
        return
    if 2*Y - X < 0 or 2 * X - Y < 0:
        print(0)
        return
    x = (2*Y-X) // 3
    y = (2*X-Y) // 3
    f = mfact(2000000)
    print(mcomb(x+y, x, f))
    return


# Generated by 1.1.5 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:
a,b=map(int,input().split())
aa=a
bb=b
x=0
y=0
while aa>0 and bb>0:
	if aa>bb:
		aa-=1
		x+=1
	else:
		bb-=1
		y+=1
	aa-=1
	bb-=1
if aa!=0 or bb!=0:
	print(0)
	exit()
mod=10**9+7
fac=[1]
for i in range(max(a,b)):
	fac.append(fac[i]*(i+1)%mod)
x+=y
r=pow(fac[y]*fac[x-y]%mod,mod-2,mod)
print(fac[x]*r%mod)

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 ((2 * X - Y) >= 0) and ((2 * X - Y) % 3 == 0):
    t = (2 * X - Y) // 3
else:
    print(0)
    exit()

if ((2 * Y - X) >= 0) and ((2 * Y - X) % 3 == 0):
    s = (2 * Y - X) // 3
else:
    print(0)
    exit()

print(cmb(s + t, s, mod))

Submission status: Accepted

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


def solve(x, y):
    d, m = divmod(x + y, 3)
    if m != 0 or x / y > 2 or y / x > 2:
        return 0
    c = abs(d - x)

    MOD = 10 ** 9 + 7
    f, invs = prepare(d, MOD)
    return f * invs[c] * invs[d - c] % MOD


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