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:
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()]

m=1000000007

    

if y<=2*x  and x<=2*y and (2*x-y)%3==0 and (2*y-x)%3==0:
    a=(2*y-x)//3
    b=(2*x-y)//3
    
    print(cmb(a+b,b,m))
else:
    print(0)

Submission status: Accepted

Solution code:
# 二項係数を"やるだけ"にしてくれるライブラリ
from collections import Counter
MAX = 1000010
MOD = 10**9+7
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX


# テーブルを作る前処理
def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD


# 二項係数計算
def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD


# 前処理完了
COMinit()

X, Y = map(int, input().split())
ans = 0
if (X+Y) % 3 != 0:
    print(0)
else:
    ans = 0
    m = (2*X - Y) // 3
    n = X - 2*m
    if m < 0 or n < 0:
        print(0)
    else:
        print(COM(n+m, n))

Submission status: Accepted

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

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

i=(2*Y-X)//3
j=(2*X-Y)//3

def m_pow(n,m):
    ret = 1
    while m:
        if m&1:
            ret=ret*n%MOD
        n=n*n%MOD
        m>>=1
    return ret

def m_fact(n):
    if n==0:
        return 1
    ret = 1
    for i in range(1,n+1):
        ret=ret*i%MOD
    return ret

def m_comb(n,k):
    return m_fact(n) * m_pow(m_fact(k), MOD-2) * m_pow(m_fact(n-k), MOD-2) %MOD

print(m_comb(i+j,min(i,j)))

Submission status: Accepted

Solution code:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
 
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
 
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
 
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
 
    return result
x,y = map(int,input().split())
mod=10**9+7
if (x+y)%3!=0 or x>2*y or y>2*x:
  print('0')
else:
  p=(2*y-x)//3
  q=(2*x-y)//3
  print(cmb(p+q,p)%mod)

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+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:
    count = (x+y)//3
    x -= count
    y -= count
    ans = 0
    if x >= 0 and y >= 0:
        print(cmb(x+y, x, mod))
    else:
        print(0)

else:
    print(0)

Submission status: Accepted

Solution code:
mod = 10**9+7

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())
m = abs(x - y)
n = (x + y) // 3
if (x + y) % 3 == 0 and n >= m:
  print(comb(n, (n - m) // 2))
else:
  print(0)

Submission status: Accepted

Solution code:
mod = 10**9+7

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

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

x, y = map(int, input().split())
m = abs(x - y)
n = (x + y) // 3
if (x + y) % 3 == 0 and n >= m:
  print(comb(n, (n + m) // 2))
else:
  print(0)

Submission status: Accepted

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

#y=2x以下かつy=(1/2)x以上の位置にいなくてはいけない
if (X+Y) % 3 != 0 or not (X<=2*Y and Y <=2*X):
    ans = 0
else:
    N = (X+Y)//3
    r = Y - N
    ans = combination(N,r)
print(ans)

Submission status: Accepted

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

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
      
if (X+Y) % 3 > 0:
  print(0)
  exit(0)
  
K = (X+Y)//3

if X < K or Y < K:
  print(0)
  exit(0)

comb = Combination(K+10)
print(comb(K, X-K))

Submission status: Accepted

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

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
      
if (X+Y) % 3 > 0:
  print(0)
  exit(0)
  
K = (X+Y)//3

if X < K or Y < K:
  print(0)
  exit(0)

comb = Combination(int(1e6+10))
print(comb(K, X-K))

Submission status: Accepted

Solution code:
X, Y = map(int, input().split())
mod = int(1e+9 + 7)
n = mod - 2
x, y = (2 * X - Y) // 3, (- X + 2 * Y) // 3

ax = []
while n != 0:
    ax = [n % 2] + ax[:]
    n //= 2
S = 0
if (2 * X - Y) % 3 != 0 or (-X + 2 * Y) % 3 != 0:
    S = 0
elif X > 2 * Y or Y > 2 * X:
  S = 0
else:
    A = [1]
    for i in range(x+y):
        A.append(((i + 1) * A[i]) % mod)
    inv = [1, 1]
    for i in range(len(ax)):
        if ax[i] == 1:
            inv[0] *= A[x]
            inv[1] *= A[y]
            inv[0] %= mod
            inv[1] %= mod
        if i != len(ax) - 1:
            inv[0] *= inv[0] % mod
            inv[0] %= mod
            inv[1] *= inv[1] % mod
            inv[1] %= mod
    S = (inv[0] * inv[1] * A[x+y]) % mod
print(S)

Submission status: Accepted

Solution code:
import sys
import itertools
import bisect
import math

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

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 )


mod = 10 ** 9 + 7
x, y = na()
if (x + y) % 3 != 0:
    print(0)
else:
    n = ((x + y) // 3 + (y - x)) // 2
    m = y - (2 * n)
    if n < 0 or m < 0:
        print(0)
    else:
        print(cmb(n+m, n, 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 *= int(numerator[k])
    return result

def run():
  X, Y = map(int, input().split())
  b = X+Y
  if b%3 != 0:
    print(0)
    exit()
  x = b//3
  if X < x or Y < x:
    print(0)
    exit()
  i = X - x
  if i > x//2:
    i = x - i
  ans = cmb(x, i)
  mod=10**9+7
  print(ans%(mod))
  
if __name__ == '__main__':
  run()

Submission status: Accepted

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

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 mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

"""
A(x+2y)+B(2x+y) = nx + my
答えは(A+B)CA

xについて
A+2B = n
yについて
2A + B = m

Aは
A = (2m-n)/3
Bは
B = (2n-m)/3
AとBが正の整数で存在しなければ0

"""
A = (2*m-n)/3
B = (2*n-m)/3

if A%1!=0 or B%1!=0 or A<0 or B<0:
    print(0)
    exit()
ans = 1
A,B = int(A),int(B)
for i in range(1,A+B+1):
    ans = ans*i%mod
for i in range(1,A+1):
    ans = ans*mod_inv(i,mod)%mod
for i in range(1,B+1):
    ans = ans*mod_inv(i,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

N = 10**6     #出力の制限
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 )

X ,Y = map(int, input().split())
n = 2 * Y - X
m = 2 * X - Y
r = 1
if n % 3 != 0:
    r = 0
elif m % 3 != 0:
    r = 0
else:
    r = cmb(n//3+m//3,n//3,mod)
print(r)

Submission status: Accepted

Solution code:
'''
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p

def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
'''

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

    factrial = [1] * (n+1)
    for k in range(1, n+1):
        factrial[k] = (factrial[k-1] * k) % MOD

    fact_inv = [1] * (n+1)
    fact_inv[n] = pow(factrial[n], MOD - 2, MOD)
    for k in range(n-1, -1, -1):
        fact_inv[k] = (fact_inv[k+1] * (k+1)) % MOD

    return (factrial[n] * fact_inv[r] * fact_inv[n-r]) % MOD

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

if (2*y-x)%3!=0 or (2*x-y)%3!=0:
    print(0)
else:
    k=(2*y-x)//3
    l=(2*x-y)//3
    a = comb_mod(k+l,l,10**9+7)
    print(a)

Submission status: Accepted

Solution code:
import collections
import math
import operator as op
from functools import reduce

import numpy as np

MOD = 10**9 + 7

# def nCr(n, r):
#     r = min(r, n-r)
#     numer = reduce(op.mul, range(n, n-r, -1), 1)
#     denom = reduce(op.mul, range(1, r+1), 1)
#     return numer // denom


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


# def nCr(n, r):
#     r = min(r, n-r)
#     numer = reduce(op.mul, range(n, n-r, -1), 1)
#     denom = reduce(op.mul, range(1, r+1), 1)
#     return numer // denom

# cache = {}
# def nCr(n, r):
#     r = min(r, n-r)
#     if (n, r) in cache:
#         return cache[(n, r)]

#     if r == 0:
#         ret = 1
#     if n == r:
#         ret = 1
#     else:
#         ret = (nCr(n-1, r-1) + nCr(n-1, r)) % MOD

#     cache[(n, r)] = ret
#     return ret


def main():
    X, Y = list(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)
    else:
        a = (2 * X - Y) // 3
        b = (2 * Y - X) // 3
        print(nCr(a+b, a) % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7  # prime number
 
def cmb(n, r, mod=MOD):
    if r < 0 or n < r:
        return 0
    r = min(r, n-r)
    numerator, denominator = 1, 1
    for i in range(1, r + 1):
        numerator = (numerator * (n + 1 - i)) % mod
        denominator = (denominator * i) % mod
    return numerator * pow(denominator, mod - 2, mod) % mod
 
X, Y = map(int, input().split())
if (X + Y) % 3 != 0:
    print(0)
else:
    n = int((X + Y) / 3)
    a = Y - n
    b = X - n
    if not (a >= 0 and b >= 0):
        print(0)
    else:
        ans = cmb(a + b, a)
        print(ans)

Submission status: Accepted

Solution code:
import sys
import math
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input():
    return sys.stdin.readline().rstrip()


def main():
    def COMinit(n,MOD):
        fac,finv,inv=[0]*(n+1),[0]*(n+1),[0]*(n+1)
        fac[0]=fac[1]=1
        finv[0]=finv[1]=1
        inv[1]=1
        for i in range(2,(n+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
        return fac,finv,inv
        
    def COM(n, k, MOD):
        fac,finv,inv=COMinit(n,MOD)
        if n<k or n<0 or k<0:
            return 0
        return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD
    
    X,Y=map(int,input().split())
    if (X+Y)%3==0:
        z=(X+Y)//3
        a_x=X-z
        a_y=Y-z
        print(COM(a_x+a_y,a_x,MOD))
    else:
        print(0)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7  # prime number

def cmb(n, r, mod=MOD):
    if r < 0 or n < r:
        return 0
    r = min(r, n-r)
    numerator, denominator = 1, 1
    for i in range(1, r + 1):
        numerator = (numerator * (n + 1 - i)) % mod
        denominator = (denominator * i) % mod
    return numerator * pow(denominator, mod - 2, mod) % mod

X, Y = map(int, input().split())
if (X + Y) % 3 != 0:
    print(0)
else:
    n = int((X + Y) / 3)
    a = Y - n
    b = X - n
    if not (a >= 0 and b >= 0):
        print(0)
    else:
        ans = cmb(a + b, a)
        print(ans)

Submission status: Accepted

Solution code:
def cmb(n, r, mod):
    if r < 0 or n < r:
        return 0
    r = min(r, n-r)
    numerator, denominator = 1, 1
    for i in range(1, r + 1):
        numerator = (numerator * (n + 1 - i)) % mod
        denominator = (denominator * i) % mod
    return numerator * pow(denominator, mod - 2, mod) % mod


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

    if (X + Y) % 3 != 0:
        print(0)
        exit()
    
    n = (2 * Y - X) // 3
    m = (X - n) // 2
    
    if n < 0 or m < 0:
        print(0)
        exit()
    
    ans = cmb(n + m, n, MOD)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
X,Y=map(int,input().split())
if (X+Y)%3!=0:
    print(0)
    exit()
mod=10**9+7
N=(X+Y)//3
'''
k*(1,2)+(n-k)*(2,1)=(x,y)
(k+2n-2k,2k+n-k)=(x,y)
(2n-k,n+k)=(x,y)
2y=2n+2k
x=2n-k
2y-x=3k
'''
K=(2*Y-X)//3
if not(0<=K<=N):
    print(0)
    exit()
ans=1
for i in range(1,K+1):
    ans*=(N+1-i)*pow(i,mod-2,mod)
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
z=(x+y)//3
n=abs(y-x)
r = (z-n)//2

def mod(x):
  return(x%(10**9+7))
a=1
for i in range(r,z):
  a=mod(a*(i+1))

b=1
for i in range(z-r):
  b=mod(b*(i+1))
if (x+y)%3!=0:
  a=0

c=pow(b,10**9+5,10**9+7)
print(mod(a*c))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

class modfact(object):
    def __init__(self,n):
        fact=[1]*(n+1); invfact=[1]*(n+1)
        for i in range(1,n+1): fact[i]=i*fact[i-1]%MOD
        invfact[n]=pow(fact[n],MOD-2,MOD)
        for i in range(n-1,-1,-1): invfact[i]=invfact[i+1]*(i+1)%MOD
        self.__fact=fact; self.__invfact=invfact

    def inv(self,n):
        assert(n>0)
        return self.__fact[n-1]*self.__invfact[n]%MOD

    def fact(self,n):
        return self.__fact[n]

    def invfact(self,n):
        return self.__invfact[n]

    def comb(self,n,k):
        if(k<0 or n<k): return 0
        return self.__fact[n]*self.__invfact[k]*self.__invfact[n-k]%MOD

    def perm(self,n,k):
        if(k<0 or n<k): return 0
        return self.__fact[n]*self.__invfact[n-k]%MOD

def resolve():
    x,y=map(int,input().split())
    if((x+y)%3):
        print(0)
        return

    mf=modfact(x+y)
    z=(x+y)//3
    print(mf.comb(z,x-z))
resolve()

Submission status: Accepted

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

def comb(n, r, p):
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]
    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 r < 0 or n < r:
        return 0
    r = min(r, n-r)
    return fact[n] * factinv[r] * factinv[n-r] % p

def solve():
    a = (2*Y-X) / 3
    b = (2*X-Y) / 3
    if a.is_integer() and b.is_integer() and a >= 0 and b >= 0:
        ans = comb(int(a+b), int(min(a, b)), MOD)
        print(ans)
    else:
        print(0)

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

MOD = 1000000007  # type: int


def comb(n, r):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    g1 = [1] * (n + 1)
    g2 = [1] * (n + 1)
    ig = [0] * (n + 1)
    ig[1] = 1
    for i in range(2, n + 1):
        g1[i] = (g1[i-1] * i) % MOD
        ig[i] = (-ig[MOD % i] * (MOD//i)) % MOD
        g2[i] = (g2[i-1] * ig[i]) % MOD
    return g1[n] * g2[r] * g2[n-r] % MOD


def solve(X: int, Y: int):
    if (X + Y) % 3:
        return 0
    t = (X + Y) // 3
    return comb(t, X - t) % MOD


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 10**9+7

FRAC_RANGE = 2000000
frac = [1] * FRAC_RANGE

for i in range(2,FRAC_RANGE):
    frac[i] = frac[i-1] * i % mod

def combi(n,k):
    a = frac[n]
    b = modpow(frac[k],mod-2)
    c = modpow(frac[n-k],mod-2)
    return a*b*c%mod

def bi(x):
    o = []
    while x != 0:
        o.append(x%2)
        x //= 2
    return o

def modpow(m,n):
    o = bi(n)
    p = [m]
    leo = len(o)
    while leo > len(p):
        a = p[-1]
        p.append(a*a%mod)
    b = 1
    for i in range(leo):
        if o[i] == 1:
            b *= p[i]
            b %= mod
    return b

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

A = (-1) * X +   2  * Y
B =   2  * X + (-1) * Y

if A % 3 or B % 3 or A < 0 or B < 0:
    print(0)
    exit()

A //= 3
B //= 3

print(combi(A+B,min(A,B)))

Submission status: Accepted

Solution code:
class Factorials(object):
    def __init__(self, n, mod):
        inv = [1] * (n + 1)
        self.__mod = mod
        self.__fac = [1] * (n + 1)
        self.__fac_inv = [1] * (n + 1)
        for i in range(2, n+1):
            self.__fac[i] = (self.__fac[i-1] * i) % mod
            inv[i] = mod - inv[mod % i] * (mod // i) % mod
            self.__fac_inv[i] = self.__fac_inv[i - 1] * inv[i] % mod
        
    def comb(self, n, k):
        if n < k or n < 0 or k < 0:
            return 0
        return self.__fac[n] * (self.__fac_inv[k] * self.__fac_inv[n - k] % self.__mod) % self.__mod
    
    def fac(self, k):
        return self.__fac[k]
    
    def fac_inv(self, k):
        return self.__fac_inv[k]

MOD = 1000000007
x, y = map(int, input().split())
if (x + y) % 3 != 0:
  print(0)
  exit()
n = (x + y) // 3
f = Factorials(n, MOD)
print(f.comb(n, x-n))

Submission status: Accepted

Solution code:
mod = int(1e9+7)
X, Y = map(int, input().split())

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

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

if x > y:
    tmp = x
    x = y
    y = tmp

ans = 1
for i in range(1, x+1):
    ans *= (i+y)
    ans %= mod
    ans *= pow(i, mod-2, mod)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
# #二項係数(mod)
def comb(n, k, mod, fac, finv):
    if n < k or n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod

# 階乗の逆元(mod)
def factorials_inv_mod(n, mod):
    inv = [1] * (n + 1)
    factorials_inv = [1] * (n + 1)
    for i in range(2, n + 1):
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        factorials_inv[i] = factorials_inv[i - 1] * inv[i] % mod
    return factorials_inv

# 階乗(mod)
def factorials_mod(n, mod):
    factorials = [1] * (n + 1)
    for i in range(2, n+1):
        factorials[i] = (factorials[i-1] * i) % mod
    return factorials

MOD = 1000000007
x, y = map(int, input().split())
if (x + y) % 3 != 0:
  print(0)
  exit()
k = (x + y) // 3
fac = factorials_mod(k, MOD)
finv = factorials_inv_mod(k, MOD)
print(comb(k, x-k, MOD, fac, finv))

Submission status: Accepted

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

m = 10**9 + 7

if (x + y) % 3 != 0:
    print(0)
else:
    s = (x + y) // 3
    k = y - s
    l = x - s
    if k < 0 or l < 0:
        print(0)
    else:
        a = 1
        b = 1
        for i in range(k + 1,k + l + 1):
            a = (a * i) % m
        for i in range(1,l + 1):
            b = (b * i) % m
        ans = a * pow(b,m-2,m) % m
        print(ans)

Submission status: Accepted

Solution code:
# 互いに素なa,bについて、a*x+b*y=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 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 == 0 and min(x, y) * 2 >= max(x, y):
    a = (2 * y - x) // 3
    b = (2 * x - y) // 3
    x = 1
    for i in range(2, a + b + 1):
        x = x * i % mod
    for i in range(2, a + 1):
        x = x * mod_inv(i, mod) % mod
    for i in range(2, b + 1):
        x = x * mod_inv(i, mod) % mod
    print(x)
else:
    print(0)

Submission status: Accepted

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


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


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

count = (x+y)//3
x -= count
y -= count

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

ans = nCr(x+y, x)
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()

count = (x+y)//3
x -= count
y -= count

ans = cmb(x+y, min(x, y), mod)
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

m = 2 * X - Y
n = 2 * Y - X

if m % 3 or n % 3 or m < 0 or n < 0:
    print(0)
    quit()

m //= 3
n //= 3

factorial = [1] * (n + m + 1)
for i in range(n + m):
    factorial[i + 1] = factorial[i] * (i + 1) % MOD

print(factorial[m + n] * pow(factorial[m], MOD - 2, MOD) * pow(factorial[n], MOD - 2, MOD) % MOD)

Submission status: Accepted

Solution code:
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]
factinv = [1, 1]
inv = [0, 1]

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)

x, y = map(int, input().split())
mod = 10**9 + 7
if (x + y) % 3 != 0:
    print(0)
    exit()
n = (2*y - x)//3
m = (2*x - y)//3

print(cmb(n+m, n, p))

Submission status: Accepted

Solution code:
INF = float("inf") #const
MOD = 10**9+7 #const
MAX = 510000 #const

def repeat(n,p):
    if p == 0:
        return 1
    if p%2==0:
        t = repeat(n,p//2)
        return t * t % MOD
    return n * repeat(n,p-1) % MOD


def com(n,r):
    if n < r or n < 0:
        return 0
    if n == 0 and r == 0:
        return 1
    fact = [0] * (10**6+1)
    fact[0] = 1
    for i in range(n):
        fact[i+1] = fact[i] * (i+1) % MOD #階乗計算
    f_inv = repeat(fact[r],MOD-2)
    f = repeat(fact[n-r],MOD-2)
    return fact[n] * f_inv * f % MOD


def main():
    x,y = map(int,input().split())
    if (x+y)%3 != 0:
        print(0)
        return
    n = (2*y - x)//3
    m = (2*x - y)//3
    print(com(n+m,n))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def mulmod(x, y, p=10**9 + 7):
    return x * y % p


def combmod(n, k, p=10**9 + 7):
    from functools import reduce
    k = min(k, n - k)
    x = reduce(mulmod, range(n - k + 1, n + 1), 1)
    y = reduce(mulmod, range(1, k + 1), 1)
    return x * pow(y, p - 2, p) % p


def solve(string):
    x, y = map(int, string.split())
    m0, m1, n = min(x, y), max(x, y), (x + y) // 3
    return "0" if (x + y) % 3 > 0 or m1 / m0 > 2 else str(combmod(n, m0 - n))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read()))

Submission status: Accepted

Solution code:
import sys


def mulmod(x, y, p=10**9 + 7):
    return x * y % p


def combmod(n, k, p=10**9 + 7):
    from functools import reduce
    k = min(k, n - k)
    x = reduce(mulmod, range(n - k + 1, n + 1), 1)
    y = reduce(mulmod, range(1, k + 1), 1)
    return x * pow(y, p - 2, p) % p


def solve(string):
    x, y = map(int, string.split())
    m0, m1, n = min(x, y), max(x, y), (x + y) // 3
    return "0" if (x + y) % 3 > 0 or m1 / m0 > 2 else str(combmod(n, m0 - n))


if __name__ == '__main__':
    print(solve(sys.stdin.read()))

Submission status: Accepted

Solution code:
import sys


def mulmod(x, y, p=10**9 + 7):
    return x * y % p


def combmod(n, k, p=10**9 + 7):
    from functools import reduce
    k = min(k, n - k)
    x = reduce(mulmod, range(n - k + 1, n + 1), 1)
    y = reduce(mulmod, range(1, k + 1), 1)
    return x * pow(y, p - 2, p) % p


def solve(string):
    x, y = map(int, string.split())
    m0, m1 = min(x, y), max(x, y)
    if (x + y) % 3 > 0 or m1 / m0 > 2:
        return "0"
    n = (x + y) // 3
    return str(combmod(n, m0 - n))


if __name__ == '__main__':
    print(solve(sys.stdin.read()))

Submission status: Accepted

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

def nCk(n, k, mod=10 ** 9 + 7):
    if n < k:
        return 0
    k = min(k, n - k)
    
    numer = 1
    for x in range(n - k + 1, n + 1):
        numer = (numer * x) % mod
        
    denom = 1
    for x in range(1, k + 1):
        denom = (denom * x) % mod
## if z=pow(x,-1)%P, where P is prime then according to Fermat's Theorem z=pow(x,P-2)%P,
    return numer * pow(denom, mod - 2, mod) % mod
  
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:
        print(nCk(a+b, a)%(7+10**9))

Submission status: Accepted

Solution code:
def fact_mod(n, mod):
    r = 1
    for i in range(n):
        r = r * (n - i) % mod
    return r


def FLT(n, mod):
    m = fact_mod(n, mod)
    return pow(m, mod - 2, mod)


X, Y = map(int, (input().split()))
x2y1 = (2 * X - Y) // 3
x1y2 = (-X + 2 * Y) // 3
p = 10 ** 9 + 7

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

print(fact_mod(x2y1 + x1y2, p) * FLT(x2y1, p) * FLT(x1y2, p) % p)

Submission status: Accepted

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

mod = 10**9 +7
n = (x+y)//3	# 移動回数

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

x -= n
y -= n

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

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 = x+y
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
 
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
 
ans = cmb(x+y,x,mod)
print(ans)

Submission status: Accepted

Solution code:
X, Y = list(map(int, input().split()))
MOD = int(1e9 + 7)

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

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

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

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

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


print(combination(a+b, a, MOD))