Problem:


Score : 400 points

Problem Statement

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

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

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

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

Constraints

1 \leq X \leq 10^6

1 \leq Y \leq 10^6

All values in input are integers.

Input

Input is given from Standard Input in the following format:

X Y

Output

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

Sample Input 1

3 3

Sample Output 1

2

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

Sample Input 2

2 2

Sample Output 2

0

The knight cannot reach (2,2).

Sample Input 3

999999 999999

Sample Output 3

151840682

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



Sample input:
3 3


Sample output:
2

Submission status: Accepted

Solution code:
import sys


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():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    x, y = list(map(int, input().rstrip('\n').split()))
    if (x + y) % 3 != 0 or x <= 0 or y <= 0:
        print(0)
    else:
        t = (x + y) // 3
        for i in range(t + 1):
            xn = i * 2 + (t - i)
            yn = i + (t - i) * 2
            if xn == x and yn == y:
                print(alg_combination_mod(i + t - i, i, mod))
                exit()
        print(0)


if __name__ == '__main__':
    solve()

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
a=(2*y-x)/3
b=(2*x-y)/3
c=(x+y)/3
if (x+y)%3!=0 :
    print(0)
elif a<0 or b<0:
    print(0)
else:
    print(int(comb(int(c),int(a))))

Submission status: Accepted

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

def combinations_count(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 A(i, j):
    if 0.5*i <= j and j <= 2*i and (i+j)%3==0:
        n, m = (2*j-i)//3, (2*i-j)//3
        return combinations_count(n+m,m)%((10**9)+7)
    else:
        return 0

print(A(x, y))

Submission status: Accepted

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

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

n=((x+y)//3) + 1
k=y-(n-2)

fac=[0 for _ in range(n)]   #n!
finv=[0 for _ in range(n)]  #1/n!
inv=[0 for _ in range(n)]   #

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

for i in range(2,n):
    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 ncr(n,k):
    if(n < k):
        return 0
    elif(n < 0 or k < 0):
        return 0
    else:
        return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


print(ncr(n-1,k-1))

Submission status: Accepted

Solution code:
import numpy as np


MOD = 10**9 + 7

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

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

else:
    if (Y < X/2) or (Y > 2*X):
        print(0)
    
    else:
      
        h = (2 * X - Y) // 3
        v = (2 * Y - X) // 3

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

        def low_inverse(a):
            ret, _ = extgcd(a, MOD)
            return ret

        def low_combination(m, n):
            # calculate (m+n)!/n!m!
            ret = 1
            numerator = m + n
            for i in range(min(m, n)):
                inv_i = low_inverse(i + 1)
                ret = ret * (numerator - i) * inv_i % MOD
            return ret

        print(low_combination(h, v))

Submission status: Accepted

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

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

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):
    print(0)
else:
    n = - (X - 2 * Y) / 3
    m = (2 * X - Y) / 3
    if not (n % 1 == 0 and m % 1 == 0):
        print(0)
    else:
        if n < 0 or m < 0:
            print(0)
        else:
            print(comb(int(n+m), int(n), mod))

Submission status: Accepted

Solution code:
#組み合わせの計算
def combi(n, r, mod):
    r = min(r, n-r)
    numer = denom = 1

    for i in range(r):
        numer = numer * (n-i) % mod
        denom = denom * (i+1) % mod
    return numer * pow(denom, mod-2, mod) % mod #逆元

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

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

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

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

ans = combi(int(n+m), int(n), 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


if __name__ == "__main__":
    mod = 10**9 + 7
    x, y = map(int, input().split())

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

    n = (x + y) // 3
    k = (2 * x - y) // 3
    g1 = [1, 1]  # 元テーブル
    g2 = [1, 1]  # 逆元テーブル
    inv = [0, 1]  # 逆元テーブル計算用テーブル

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

    print(cmb(n, k, mod))

Submission status: Accepted

Solution code:
X, Y = map(int,input().split())
if 2 * X < Y or 2 * Y < X or (X+Y) % 3:
  print(0)
  quit()

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 )

print(cmb((X+Y)//3,(-X+2*Y)//3,mod))

Submission status: Accepted

Solution code:
mod = 10**9 + 7

def init(n):
    # 階乗とその逆元をグローバルに定義
    global factorial, inverse
    # 0-indexedでそれぞれ１で初期化
    factorial = [1]*(n+1)
    inverse = [1]*(n+1)

    fact = 1
    for p in range(1,n+1):
        fact *= p
        fact %= mod
        factorial[p] = fact

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

def comb(n,r):
    if n < r:
        return 0
    return factorial[n] * inverse[n-r] * inverse[r] % mod

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

n = (2*Y - X) / 3
m = (2*X - Y) / 3
if not(int(n) == n and n >= 0 and int(m) == m and m >= 0):
    print(0)
    exit()

n = int(n)
m = int(m)

init(10**6)

ans = comb(n+m, n)
print(ans)

Submission status: Accepted

Solution code:
import math
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
MOD = 1000000007
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

X,Y=LI()

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

FACT = [1]*1000001
for i in range(1, 1000001):
    FACT[i] = (FACT[i-1]*i)%MOD

if (2*X - Y)%3 == 0 and (2*Y - X)%3 == 0 and a >= 0 and b >= 0:
    print(DIV(DIV(FACT[a+b], FACT[a]), FACT[b]))
else:
    print(0)

Submission status: Accepted

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

mod=10**9+7 
def nCr(n, r, mod):#mod=10**9+7 
    r = min(r, n-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

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

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

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

print(nCr(n+m,min(n,m),mod))

Submission status: Accepted

Solution code:
import sys

x,y = map(int,input().split())
MOD = 10**9+7
N = 10**6
if (x+y)%3 != 0:
    print(0)
    sys.exit()
else:
    m = (2*x-y)//3
    n = (2*y-x)//3
    if n < 0 or m < 0:
        print(0)
        sys.exit()
    else:
        A = [1,1]
        B = [1,1]
        Inv = [0,1]
        for i in range(2,N+1):
            A.append((A[-1]*i)%MOD)
            Inv.append((-Inv[MOD%i]*(MOD//i))%MOD)
            B.append((B[-1]*Inv[-1])%MOD)
print(A[m+n]*B[m]*B[n]%MOD)

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
if (x+y)%3:
    print(0)
    exit()
c = (x+y)//3
x -= c; y -= c
if x<0 or y<0:
    print(0)
    exit()

n = x+y
mod = 10**9+7
fun = [1]*(n+1)
for i in range(1,n+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n+1)
rev[n] = pow(fun[n],mod-2,mod)
for i in range(n-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod

def nCr(n,r):
    if r > n:
        return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

print(nCr(x+y,x))

Submission status: Accepted

Solution code:
import math
x, y = map(int, input().split())
mod = 10**9 +7
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:
    b = (2*x-y)//3
    a = x - 2*b
    c = min(a, b)
    s = 1
    t = 1
    for i in range(c):
        s = s*(a+b-i)%mod
        t = t*(c-i)%mod
    print(s*pow(t, mod-2, mod)%mod)

Submission status: Accepted

Solution code:
# from scipy.special import comb
# from math import factorial
# from operator import mul
# from functools import reduce

# def combination(n, r):
#     r = min(n - r, r)
#     if r == 0:
#         return 1
#     over = reduce(mul, range(n, n - r, -1))
#     under = reduce(mul, range(1, r + 1))
#     return over // under


def combination(n, r, mod=10 ** 9 + 7):
    n1, r = n + 1, min(r, n - r)
    numerator = denominator = 1
    for i in range(1, r + 1):
        numerator = numerator * (n1 - 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 or (x > 2 * y or y > 2 * x):
    print(0)
else:
    # (+1, +2) n
    # (+2, +1) m
    # n + 2m = x
    # 2n + m = y
    m = (2 * x - y) // 3
    n = (2 * y - x) // 3
    # score = factorial(n + m) // factorial(n) // factorial(m)
    # score = comb(n + m, n, exact=True)
    score = combination(n + m, n)
    print(score)

Submission status: Accepted

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


x,y = map(int,input().split())
diff = abs(x-y)
mod = 10**9 + 7
if (x+y) % 3 != 0:
    print("0")
    exit()
else:
    cir = (min(x,y) - diff) // 3
    if cir < 0:
        print("0")
        exit()
    all_step = (x+y) // 3
    print(combination(all_step, cir, mod))

Submission status: Accepted

Solution code:
import math
import sys

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


ans = 1
x,y = map(int,input().split())
if (x+y) % 3 != 0:
    print(0)
    
    sys.exit()
a = max(x,y)
b = min(x,y)
ab_sum = a+b
ab_diff = a-b
turn = ab_sum // 3
a_turn = ab_diff + (ab_sum//3 - ab_diff)//2
b_turn = turn - a_turn
# print(a_turn,b_turn)
# ab_fac = math.factorial(turn)
# b_fac = math.factorial(b_turn)
# print(a_fac,b_fac)
# for i in range(a_turn+1,turn+1):
#     print(i)
mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
n = turn
r = b_turn
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(n,r,mod)
print(ans)

Submission status: Accepted

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

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

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

if m<0 or n<0:
    print(0)
elif m.is_integer()==False or n.is_integer==False:
    print(0)
else:
    print(combination(int(n+m),int(n)))

Submission status: Accepted

Solution code:
# Contest: AtCoder Beginner Contest 145 (https://atcoder.jp/contests/abc145)
# Problem: D: Knight (https://atcoder.jp/contests/abc145/tasks/abc145_d)

def rint():
    return int(input())


def rints():
    return list(map(int, input().split()))


x, y = rints()
if y > x:
    x, y = y, x
d = x - y
if d > y:
    print(0)
    exit(0)
x -= 2 * d
y -= d
if x % 3 != 0:
    print(0)
    exit(0)
rj = d + x // 3
lj = x // 3
M = 10**9 + 7
f = [1]
for i in range(1, rj + lj + 1):
    f.append(f[-1] * i % M)
print(f[rj + lj] * pow(f[lj], M - 2, M) * pow(f[rj], M - 2, M) % M)

Submission status: Accepted

Solution code:
# nCkの計算するやつ
# (n!)/(k!(n-k)!) mod p
# (n!) * (k!)^-1 * ((n-k)!)^-1 mod p

def comInit(MOD, n):
    fact=[1,1] # fact[n]はnの階乗
    invr=[0,1] # invr[n]はnの逆元
    invr_fact=[1,1] # invr_fact[n]は逆元の階乗

    for i in range(2,n+1):
        fact.append(fact[-1]*i%MOD)
        invr.append(-invr[MOD%i]*(MOD//i)%MOD)
        invr_fact.append(invr_fact[-1]*invr[-1]%MOD)
    return fact,invr_fact

def calCom(n,k,MOD,fact,invr_fact):
    k=min(k,n-k)
    return fact[n]*invr_fact[k]*invr_fact[n-k]%MOD

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

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

    temp=int((x+y)/3)
    if temp*2 < x or temp > x:
        print(0)
        return
    f,inf=comInit(10**9+7,temp)
    # n,kはしっかりはっきりさせよ明日

    # ans=factorial(temp) / factorial(x-temp) / factorial(2*temp-x)
    ans=calCom(temp,abs(x-temp),10**9+7,f,inf)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import factorial
def com(n,k,mod,fac,infac):
    k=min(k,n-k)
    return fac[n]*infac[k]*infac[n-k]%mod

def cominit(mod,n):
    fac=[1,1]
    infac=[1,1]
    inv=[0,1]

    for i in range(2,n+1):
        fac.append(fac[-1]*i%mod)
        inv.append(-inv[mod%i]*(mod//i)%mod)
        infac.append(infac[-1]*inv[-1]%mod)

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

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

    temp=int((x+y)/3)
    if temp*2 < x or temp > x:
        print(0)
        return
    f,inf=cominit(10**9+7,temp)
    # n,kはしっかりはっきりさせよ明日

    # ans=factorial(temp) / factorial(x-temp) / factorial(2*temp-x)
    ans=com(temp,abs(x-temp),10**9+7,f,inf)

    print(ans)

if __name__ == '__main__':
    main()

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 )
flag = False
x , y = map(int,input().split())
MOD = 10 ** 9 + 7
for s in range(max(x,y)):
    if 2 * x - 3 * s == y:
        flag = True
        break
t = x - 2 * s
if flag:
    print(cmb((t+s),s,mod))
else:
    print(0)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


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


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

# a := →→↑ の個数
# b := →↑↑ の個数
# 2a + b = X
# a + 2b = Y より、
a = (2 * X - Y) / 3
b = (2 * Y - X) / 3

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

ans = combination(int(a + b), int(a), mod=MOD)
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
from operator import mul
MOD = 10 ** 9 + 7

def combination(n, r, mod=None):
    r = min(n - r, r)
    if r == 0:
        return 1
    elif n < r:
        return 0
    if mod is None:
        over = reduce(mul, range(n, n - r, -1))
        under = reduce(mul, range(1, r + 1))
        return over // under
    else:
        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())

# a := →→↑ の個数
# b := →↑↑ の個数
# 2a + b = X
# a + 2b = Y より、
a = (2 * X - Y) / 3
b = (2 * Y - X) / 3

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

ans = combination(int(a + b), int(a), mod=MOD)
print(ans)

Submission status: Accepted

Solution code:
M=10**9+7
f=[1]
for j in range(1,10**6):f+=f[-1]*j%M,
i=[pow(f[-1],M-2,M)]
for j in range(1,10**6)[::-1]:i+=i[-1]*j%M,
x,y=map(int,input().split())
n,m=divmod(x+y,3)
print((m<1)*(x*2>=y)*(y*2>=x)*f[n]*i[~n-n+y]*i[~y+n]%M)

Submission status: Accepted

Solution code:
import math
x, y = map(int, input().split())
if (2*x-y)%3 != 0 or (-x+2*y)%3 != 0:
    print(0)
    exit()
a = (2*x-y)//3
b = (-x+2*y)//3
if a < 0 or b < 0:
    print(0)
    exit()
def comb(n, r, mod):
    r = min(r, n-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
print(comb(a+b, a, 10**9+7))

Submission status: Accepted

Solution code:
def combination(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod
 
 
def main():
    X, Y = map(int, input().split())
 
    if (X + Y) % 3 or X > Y*2 or Y > X*2:
        return 0
 
    n = (X + Y) // 3
    r = Y - n
    return(combination(n, r))
 
 
print(main())

Submission status: Accepted

Solution code:
def ext_gcd(p, a):
  #require a, m be relative prime
  #m > a  
  if a == 0:
    return 1, 0
  else:
    x1, y1 = ext_gcd(a, p%a)
    y = x1 - y1 * int(p/a)
    x = y1
    return x, y

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

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

if n != int(n) or m != int(m) or n<0 or m<0:
  ans = 0
else:
   n = int(n)
   m = int(m)
   if n < m :
      c = m
      m = n
      n = c
   # (n+m!)/(n!)(m!) mod (1e9+7)
   ans = 1
   prime = 1000000007 
   for i in range(n+1,m+n+1):
        ans = int(ans * i) 
        ans = (ans % prime)
   for i in range(1, m+1):
      ori_inv = int(ext_gcd(prime, i)[1])
      while ori_inv < 0 :
        ori_inv += prime
      ans = int(ans * ori_inv)  
      ans = (ans % prime)
print(ans)

Submission status: Accepted

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

if (X+Y)%3 != 0:
    ans = 0
else:
    p = (2*Y - X)//3
    q = (2*X - Y)//3
    if p<0 or q<0:
        ans = 0
    else:
        a = b = 1
        pq = min(p,q)
        for i in range(0,pq):
            a *= (p+q-i)
            b *= (pq-i)
            a %= M
            b %= M
        ans = a*pow(b,M-2,M)%M
print(ans)

Submission status: Accepted

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

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

if (X+Y)%3 != 0:
      print(0)
      exit()
 
n=((2*X)-Y)//3

m=((X+Y)//3)-n

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

ans = nCr(n+m,n,mod)
print(ans)

Submission status: Accepted

Solution code:
M=10**9+7
f=[1]
for j in range(1,10**6):f+=f[-1]*j%M,
i=[pow(f[-1],M-2,M)]
for j in range(1,10**6)[::-1]:i+=i[-1]*j%M,
x,y=map(int,input().split())
n,m=divmod(x+y,3)
print((m<1)*(x*2>=y)*(y*2>=x)*f[n]*i[~n-n+y]*i[~y+n]%M)

Submission status: Accepted

Solution code:
M=10**9+7
f=[1]
for j in range(1,10**6):f+=f[-1]*j%M,
i=[pow(f[-1],M-2,M)]
for j in range(1,10**6)[::-1]:i+=i[-1]*j%M,
x,y=map(int,input().split())
n,m=divmod(x+y,3)
print((m<1)*(x*2>=y)*(y*2>=x)*(y-n<=n)*f[n]*i[~n-n+y]*i[~y+n]%M)

Submission status: Accepted

Solution code:
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
if n < 0 or m < 0:
    print(0)
    exit()    

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

Submission status: Accepted

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

res = 0
mod = 10 ** 9 + 7

def IsPositiveAndInt(num):
    return int(num)-num == 0.0 and num >= 0

# Copy from https://atcoder.jp/contests/abc145/submissions/8515099
def Comb(n, r, mod=mod):
    r = min(r, n-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

if (X+Y) % 3 == 0:
    A = (2*X-Y) / 3
    B = (-X + 2*Y) / 3
    if IsPositiveAndInt(A) and IsPositiveAndInt(B):
        A, B = int(A), int(B)
        res = Comb(A+B, A, mod)
        
print(res)

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 not (X+Y) % 3 == 0:
    print(0)
else:
    # 2n + m = X
    # n + 2m = Y
    n = (Y - 2*X) // -3
    m = X - (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, 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 not (X+Y) % 3 == 0:
    print(0)
else:
    # 2n + m = X
    # n + 2m = Y
    n = (Y - 2*X) // -3
    m = X - (2 * n)
    if n < 0 or m < 0:
        print(0)
    else:
        print(cmb(n+m, n, mod))

Submission status: Accepted

Solution code:
import sys

fact = [1]
p = 10**9 + 7

def fact1(n,m):
    for i in range(1,n+m+1):
        new_fact = fact[i-1]*i %p
        fact.append(new_fact)

#ax+by=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

    return [w[0],w[1]]
#aの逆元(mod m) a,mは互いに素
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return x%m
if __name__ == "__main__":
    x, y = (int(i) for i in input().split())
    if (x+y)%3 != 0 or 2*x < y or 2*y < x:
        print(0)
        exit()
    n = int((2*y-x)/3)
    m = int((2*x-y)/3)
    fact1(n,m)
    n1 = mod_inv(fact[n],p)
    m1 = mod_inv(fact[m],p)
    ans = fact[n+m] * (n1*m1 %p) % p
    print(ans)

Submission status: Accepted

Solution code:
from numpy.linalg import solve
import numpy

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())
N = X + Y

left = [[1, 2], [2, 1]]
right = [X, Y]
s = solve(left, right)

if s[0] < 0 or s[1] < 0 or N % 3 != 0:
  print(0)
else:
  a = cmb(int(s[0]) + int(s[1]) , min(int(s[0]), int(s[1])))
  print(a % (10**9 + 7))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32

MOD = 1000000007  # type: int

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

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

    n = (X+Y)//3
    r = Y-n

    print(combination(n, r))

    return



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:
# -*- coding: utf-8 -*-

from math import factorial

MOD = 10 ** 9 + 7

def readInts():
  return [int(s) for s in input().split(" ")]

def combi(n, r):
  num = 1
  den1 = 1
  den2 = 1

  for i in range(1, n + 1):
    num = (num * i) % MOD

  for i in range(1, r + 1):
    den1 = (den1 * i) % MOD

  for i in range(1, n - r + 1):
    den2 = (den2 * i) % MOD

  return (num * pow(den1 * den2, MOD - 2, MOD)) % MOD

def solve():
  X, Y = readInts()

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

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

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

  if a < 0 or b < 0:
    return 0

  return combi(a + b, min(a, b)) % MOD

def main():
  print(solve())

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
MAX_NUM = 10**6 + 1
MOD = 10**9+7

fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]

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

for i in range(2,MAX_NUM):
    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

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

if (-Y + 2*X) % 3 != 0 or (2*Y - X) %3 != 0 or (-Y + 2*X) < 0 or (2*Y - X) <0:
    print(0)
else:
    x = (-Y + 2*X) // 3
    y = (2*Y - X) // 3
    
    result = combinations(x+y,min(x,y))
    print(int(result % MOD))

Submission status: Accepted

Solution code:
import sys
MOD = 10**9 + 7
list_size = 700000

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

def comb(n, r):
	if n < r or r < 0:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

x, y = map(int, input().split())
if (x+y)%3 != 0:
	print(0)
	sys.exit()
n = (x+y)//3
r = n - (n-x+y)//2
print(comb(n, r))

Submission status: Accepted

Solution code:
def cmd(n,r,mod=10**9+7):
    fac = [0] * (n+1)
    finv = [0] * (n+1)
    inv = [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

    if n < r: return 0
    if n < 0 or r < 0: return 0
    return (fac[n]*(finv[r]*finv[n-r]%mod)%mod)

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

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

i = (x+y)//3
j = x-i

print(cmd(i,j))

Submission status: Accepted

Solution code:
MAX_NUM = 10**6 + 1
MOD = 10**9+7

fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]

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

for i in range(2,MAX_NUM):
    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

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

if (-Y + 2*X) % 3 == 0 and (2*Y - X) %3 == 0:
    x = (-Y + 2*X) // 3
    y = (2*Y - X) // 3
    
    result = combinations(x+y,min(x,y))
    print(int(result % MOD))
    
else:
    print(0)

Submission status: Accepted

Solution code:
import math
M = 10**9+7
X,Y = map(int,input().split())
if (X+Y)/3 != (X+Y)//3:
    print(0)
    exit()
n = (X+Y)//3
r = Y-n
if r<0 or r>n:
    print(0)
    exit()
 
 
#nCr and Mod
def nCr(n, r, mod=10**9+7):
    r = min(r, n-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
 
print(nCr(n,r,M))

Submission status: Accepted

Solution code:
x, y = map(int, input().split())
a = (- x + 2 * y) // 3
b = (2 * x - y) // 3
p = 1000000007
if (x + y) % 3 != 0 or a < 0 or b < 0:
    print(0)
else:
    fact = [1] * 700000
    for i in range(2, a + b + 1):
        fact[i] = fact[i - 1] * i % p

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

    print(fact[a + b] * pow(fact[a], p - 2) * pow(fact[b], p - 2) % p)

Submission status: Accepted

Solution code:
import math
from operator import mul
from functools import reduce

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

if (2*xy[1]-xy[0]) % 3 == 0 and (2*xy[0]-xy[1]) % 3 == 0 and 2*xy[1]-xy[0] > -1 and 2*xy[0]-xy[1] > -1:
    a = (2*xy[1]-xy[0]) // 3
    b = (2*xy[0]-xy[1]) // 3
    print(cmb(a+b, a)%(10**9 + 7))
else:
    print(0)