Problem:


Score : 400 points

Problem Statement

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

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

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

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

Constraints

1 \leq X \leq 10^6

1 \leq Y \leq 10^6

All values in input are integers.

Input

Input is given from Standard Input in the following format:

X Y

Output

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

Sample Input 1

3 3

Sample Output 1

2

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

Sample Input 2

2 2

Sample Output 2

0

The knight cannot reach (2,2).

Sample Input 3

999999 999999

Sample Output 3

151840682

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



Sample input:
3 3


Sample output:
2

Submission status: Accepted

Solution code:
from math import factorial
import sys

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

maxim = 10**6+10
mod = 10**9 + 7

fac = [None] * maxim
finv = [None] * maxim
inv = [None] * maxim

def cominit():
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1

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


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

        b = (2*y - x) // 3 
        a = b + x -y
        if a < 0 or b < 0:
            print(0)
            sys.exit()
        
        cominit()
        ans = com(a+b, b)
        return ans 
    # answer = (a+b)! / a!b! mod 10^9+7


    
print(main())

# 999999 999999

Submission status: Accepted

Solution code:
import math
import sys
input = sys.stdin.readline

def main():
    mod = 10 ** 9 + 7
    x, y = map(int, input().split())
    if (2 * y - x) % 3 != 0:
        print(0)
        return None

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

    if n < 0 or m < 0:
        print(0)
    elif n == 0 and m == 0:
        print(0)
    elif n == 0 or m == 0:
        print(1)
    else:
        s = n + m + 1
        f = [1] * s

        for i in range(1, s):
            f[i] = f[i-1] * i % mod

        ans = f[n+m]
        ans = ans * modinv(f[n]) % mod
        ans = ans * modinv(f[m]) % mod
        print(ans)

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

def mod_inverse(n):
    return power(n, MOD-2)

def mul(x, y):
    return (x % MOD) * (y % MOD) % MOD
def multiply(x, y, z):
    return mul(mul(x, y), z)

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

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

Submission status: Accepted

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

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
  return pow(a, mod-2, mod)

# nCr mod m
# modinvが必要
# rがn/2に近いと非常に重くなる
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

## 条件1: Y <= 2X かつ X <= 2Y
## 条件2: (X+Y) % 3== 0

if Y <= 2*X and X <= 2*Y and (X+Y) % 3 == 0:
  # 組み合わせを求める
  
  # (+2, +1) をa回、(+1, +2)をb回とすると、
  # a - b = X - Y
  #  -> a = X - Y + b
  # 2a + b = X
  # a + 2b = Y
  # -> (X - Y + b) + 2b = Y
  # -> 3b = 2Y - X
  # -> b = (2Y - X) // 3
  b = (2*Y - X) // 3
  a = X - Y + b
  # (+2, +1) をa回、(+1, +2)をb回の組み合わせ
  # a + b 個の移動の中から、(+2, +1)の移動を行う場所をa個選ぶ（順不同）
  # すなわち (a+B)_C_aを計算する
  print(combination(a+b, a, MOD))

else:
  print(0)

Submission status: Accepted

Solution code:
import sys
import math
from itertools import permutations
from itertools import combinations
#input = sys.stdin.readline
sys.setrecursionlimit(10**9)

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

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

n = (2*X - Y) // 3
m = (-X + 2*Y) // 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 = (n + m)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

a = cmb(n+m, m, mod)

print(a)

Submission status: Accepted

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

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

n = (2*X - Y) // 3
m = (-X + 2*Y) // 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 = (n + m)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

a = cmb(n+m, m, mod)

print(a)

Submission status: Accepted

Solution code:
import math
import itertools
import sys

x, y = [int(x) for x in input().split()]

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

total_move = (x+y) // 3
move_a = 2 * total_move - x

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 = total_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 )

a = cmb(total_move,move_a,mod)

print(a)

Submission status: Accepted

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

def prepare(N, MOD):
    fac = [None] * (N+1)
    finv = [None] * (N+1)
    inv = [None] * (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

def comb_rem(N, K, fac, finv, MOD):
    if N < K:
        return 0
    if N < 0 or K < 0:
        return 0
    else:
        return fac[N] * (finv[K] * finv[N - K] % MOD) % MOD

MOD = 10 ** 9 + 7

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

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

fac, finv = prepare((X+Y)//3, MOD)
ans = comb_rem((X+Y)//3, (2*X-Y)//3, fac, finv, MOD)

print(ans)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")

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


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

    if (X + Y) % 3 != 0 or 2*X - Y < 0 or 2*Y - X < 0:
        print(0)
        return
    
    n = (2 * X - Y) // 3
    m = (2 * Y - X) // 3
    
    M = 1000000007
    res = 1
    for i in range(1, n+m+1):
        res = res * i % M
    for i in range(1, n+1):
        res = res * mod_inv(i,M) % M
    for i in range(1, m+1):
        res = res * mod_inv(i,M) % M
    
    print(res)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# editorialを参考にした
from functools import reduce
from operator import mul
import math
import sys
sys.setrecursionlimit(1000000)
X, Y = map(int, input().split())


def choose(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 (X + Y) % 3 != 0:
    print(0)
else:
    numof21 = (-Y+2*X)//3
    numof12 = (-X + 2 * Y) // 3
    #print(numof12, numof21)

    if numof12 < 0 or numof21 < 0:
        print(0)
    else:
        mod = 10**9+7  # 出力の制限
        N = numof12+numof21
        g1 = [1, 1]  # 元テーブル
        g2 = [1, 1]  # 逆元テーブル
        inverse = [0, 1]  # 逆元テーブル計算用テーブル

        for i in range(2, N + 1):
            g1.append((g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod//i)) % mod)
            g2.append((g2[-1] * inverse[-1]) % mod)
        # A = (math.factorial(numof12 + numof21))  # % (10**9+7)
        # B = math.factorial(numof21)  # % (10**9+7)
        # C = math.factorial(numof12)  # % (10 ** 9 + 7)
        # D = (B*C)  # % (10**9+7)
        # ans = (A//D) % (10**9+7)
        ans = choose((numof12+numof21), min(numof12, numof21),mod) % (10**9+7)
        print(ans)

Submission status: Accepted

Solution code:
import math
from functools import lru_cache

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


# 08        01
# 07          04
# 06      01    06
# 05        03    04
# 04    01    03    01
# 03      02    01
# 02  01    01
# 01    01
# 00ST
#   000102030405060708

# 到達可能地点の座標はx+y%3==0
# 到達可能手数は座標位置についてパスカルの三角形になる


# 到達可能か調べる
if x <= 2 * y and y <= x * 2 and (x + y) % 3 == 0:
    # 段数と位置を調べる
    total = (x + y) // 3
    # kx = 2 * total - x + 1
    # ky = 2 * total - y + 1
    n=x-total
    # print(total, k)

    # nCk 三角数n段目k番目の数は total! / k!(total-k)! であり
    # 回答は nCk / MOD なので
    # total! % MOD * 1/k! % MOD * (total-k)! % MOD と書ける

    fac = [1, 1]
    ifac = [1, 1]
    inv = [0, 1]

    for i in range(2, total + 1):
        fac.append(fac[-1] * i % MOD)
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
        ifac.append((ifac[-1] * inv[-1]) % MOD)

    def c(n, k):
        k = min(k, n-k)
        # if total < k: return 0
        # if total < 0 or k < 0: return 0
        return fac[n] * ifac[k] * ifac[n-k] % MOD

    # print(nck(total - 1, k - 1))

    print(c(total, n))
else:
    print(0)
    exit()

Submission status: Accepted

Solution code:
def p_d():
    x, y = map(int, input().split())
    if y > x:
        x, y = y, x
    if (x + y) % 3 != 0:
        print(0)
        exit()
    if x - y > (x + y) // 3:
        print(0)
        exit()
    x, y = x - (x + y) // 3, y - (x + y) // 3

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

    print(c_mod(x + y, y))
    
p_d()

Submission status: Accepted

Solution code:
def p_d():
    x, y = map(int, input().split())
    if y > x:
        x, y = y, x
    if (x + y) % 3 != 0:
        print(0)
        exit()
    if x - y > (x + y) // 3:
        print(0)
        exit()
    x, y = x - (x + y) // 3, y - (x + y) // 3

    mod = 10 ** 9 + 7  # 出力の制限
    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)

    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

    print(cmb(x + y, y, mod))
    
p_d()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
x,y=map(int,input().split()) 
mod=10**9+7
m=int((2*y-x)/3)
n=int((2*x-y)/3)
f=[1]

for i in range(1,10**6):
    f.append(f[-1]*i%mod)

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

Submission status: Accepted

Solution code:
import cmath
import numpy as np
import sys

INF=1**18
MOD=10**9+7
MAX=10**5

def moP(x,n):
    res=1
    while n>0:
        if n & 1:
            res=res*x%MOD
        x=x*x%MOD
        n>>=1
    return res

def moF(n):
    res=1
    for i in range(1,n+1):
        res=res*i%MOD
    return res


def C(n,k):
    if n==0 or n==k:
        return 1
    return moF(n)*moP(moF(k), MOD-2)%MOD*moP(moF(n-k), MOD-2)%MOD

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

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

    N=(x+y)//3
    if x<N or y<N:
        print(0)
        exit()

    K=min(x,y)-N
    print(C(N,K))

if __name__=='__main__':
    main()

Submission status: Accepted

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

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

n = (x+y)//3
x,y = 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 )

a = cmb(x+y,x,mod)
print(a)

Submission status: Accepted

Solution code:
MOD = 10**9+7

def comb_mod(a: int, b: int, mod: int = MOD) -> int:
    """Returns Comb(a, b) % mod
    Precondition: mod is prime
    Complexity: O(min(a-b, b))
    :param a:
    :param b:
    :param mod: a prime number
    :return:
    """
    b = min(b, a-b)

    res = 1
    for x in range(a-b+1, a+1):
        res = res * x % mod

    # Using Fermat's little theorem
    # a^{p-1} = 1 mod p
    # a^{p-2} = a^{-1} mod p
    for x in range(1, b+1):
        res = res * pow(x, mod-2, mod) % mod

    return res


def main():
    X, Y = [int(x) for x in input().split()]
    m = (X+X-Y)//3
    n = X - 2*m

    if n+2*m != X or 2*n+m != Y or n < 0 or m < 0:
        print(0)
        return
    print(comb_mod(n+m, n))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

prime = 10**9+7

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

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

n = n // 3
m = m // 3

# (n+m)!/n!m!を求める
# n >= mにする
if n < m:
    n, m = m, n

# (n+m)*...*(n+1)
a = 1
for i in range(n+1, n+m+1):
    a = a * i % prime

# m!
b = 1
for i in range(1, m+1):
    b = b * i % prime

# bの逆数cを求める c = b^p-2
ans = 1
exp = prime - 2
while exp:
    if exp & 1:
        ans = ans*b%prime
    b = b**2%prime
    exp = exp >> 1


print(a*ans%prime)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

def nck_tables(mod, n):
    fac = [1, 1] # 階乗テーブル
    ifac = [1, 1] #階乗の逆元テーブル
    inverse = [0, 1] #逆元テーブル

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

def nck(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod

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

times = (x+y)//3
k = max(x, y) - times
fac, ifac = nck_tables(MOD, times)
ans = nck(times, k, MOD, fac, ifac)
print(ans)

Submission status: Accepted

Solution code:
import math

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

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

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

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

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

print(cmb(n+m,m)%mod)

Submission status: Accepted

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

x,y = map(int,input().split())
n = (2*y-x)/3
m = (2*x-y)/3

if n < 0 or m < 0:
    print(0)
elif int(n) != n or int(m) != m:
    print(0)
else:
    n = int(n)
    m = int(m)
    mod = 10**9+7 #出力の制限
    N = n+m
    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(n+m,n,mod)
    print(ans)

Submission status: Accepted

Solution code:
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  assert(p > n)
  # p は素数である必要がある。典型的には 10**9 + 7 とか

  if n < k:
    return 0
  if n < 0 or k < 0:
    return 0

  fac = [1, 1]
  inv = [1, 1]
  finv = [1, 1]
  for i in range(2, n+k+1):
    fac.append(fac[i-1] * i % p)
    inv.append(p - inv[p%i] * (p//i) % p)
    finv.append(finv[i-1] * inv[i] % p)

  return fac[n] * (finv[k] * finv[n-k] % p) % p



x, y = [int(c) for c in input().split()]

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

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

rem = 10**9 + 7
ans = comb(i + j, i, rem)

print(ans)

Submission status: Accepted

Solution code:
import sys


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


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


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

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

    cnt = [0, 0]
    cnt[0] = (2 * X - Y) // 3
    cnt[1] = (-X + 2 * Y) // 3

    if cnt[0] < 0 or cnt[1] < 0:
        print(0)
        sys.exit()

    ans = 1
    for i in range(1, sum(cnt) + 1):
        ans *= i
        ans %= C
    for i in range(1, cnt[0] + 1):
        ans *= mod_inv(i, C)
        ans %= C
    for i in range(1, cnt[1] + 1):
        ans *= mod_inv(i, C)
        ans %= C

    print(ans)


main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

def mod_inverse(a, m):
    res = 1
    n = m-2
    while n > 0:
        if n & 1:
            res = (res * a) % m
        a = (a * a) % m
        n //= 2
    return res

def solve(x, y):
    a = -y + 2*x
    b = 2*y - x
    if (a < 0) or (b < 0):
        return 0
    if a % 3 + b % 3 != 0:
        return 0
    a //= 3
    b //= 3
    n, k = a+b, a
    p, q = 1, 1
    for i in range(k):
        p = p * (n-i) % MOD
        q = q * (i+1) % MOD
    return (p * mod_inverse(q, MOD)) % MOD

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

Submission status: Accepted

Solution code:
import math

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 )

def Knight(x,y):
    if (x+y)%3!=0:
        return 0
    depth = (x+y)//3
    if not depth<=x<=(x+y)-depth:
        return 0
    a = 1
    if 3*depth<2*y:
        return cmb(depth, 2*depth-y, mod)
    else:
        return cmb(depth, y-depth, mod)
X,Y = map(int,input().split())
print(Knight(X,Y))

Submission status: Accepted

Solution code:
import sys


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


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


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import math
from math import factorial
from operator import mul
from functools import reduce
from numpy.linalg import solve
 
X, Y = map(int, input().split())
 
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
 
 
if ((X + Y) %3!=0):
    print(0)
else :
    min_za = min(X, Y)
    max_za = max(X, Y)
    left = [[1, 2],
            [2, 1]]
 
    right = [X, Y]
    diff = (solve(left, right))
    diff_1 = int(diff[0])
    diff_2 = int(diff[1])

    sum = diff_1 + diff_2

    if (diff_1 >=0 and diff_2 >=0):
        print(comb(sum,diff_1,10**9+7))
    else:
        print(0)

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
if x<y:
	x,y=y,x
naname = x-y
if y-naname<0 or (y-naname)%3!=0:
	print(0)
	exit()

numna=(y-naname)//3
numyo=naname

mod=10**9+7

fac = [0]*1000000
inv = [0]*1000000
fac[0]=1
fac[1]=1
inv[0]=1
inv[1]=1



for i in range(2,10**6-5):
	fac[i] = fac[i-1]*i%mod
	inv[i] = pow(fac[i],mod-2,mod)

def nCr(n,r):
	return fac[n]*inv[r]%mod*inv[n-r]%mod

print(nCr(numna*2+numyo,numna))

Submission status: Accepted

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




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


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

Submission status: Accepted

Solution code:
def mod_comb(n, k, p):
    if k > n - k:
        k = n - k
    
    numerator = 1
    denominator = 1
    for i, j in zip(range(n - k + 1, n + 1), range(1, k + 1)):
        numerator = (numerator * i) % p
        denominator = (denominator * j) % p
    
    return (numerator * pow(denominator, p - 2, p)) % p

def solve():
    mod = 10 ** 9 + 7
    X, Y = map(int, input().split())
    s = 2 * Y - X
    t = 2 * X - Y
    if s >= 0 and s % 3 == 0 and t >= 0 and t % 3 == 0:
        s //= 3
        t //= 3
        print(mod_comb(s + t, s, mod))
    else:
        print(0)

solve()

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())
if (X+Y)%3!=0:
  print(0)
  exit()
for i in range(X+1):
  n=int((X-i)/2)
  if Y==i*2+n*1:
    print(cmb(i+n,i)%1000000007)
    exit()
    
print(0)

Submission status: Accepted

Solution code:
mod = 10**9+7
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]


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


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


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

if not (X+Y) % 3 == 0:
    print(0)
else:
    n = (Y - 2 * X) // -3
    m = X - (2 * n)
    if n < 0 or m < 0:
        print(0)
    else:
        init(n + m)
        print(com(n + m, n, mod))

Submission status: Accepted

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

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

def nCrMOD(n,r,m):
    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]
    for i in range( 2, n + 1 ):
        g1.append( ( g1[-1] * i ) % m )
        inverse.append( ( -inverse[m % i] * (m//i) ) % m )
        g2.append( (g2[-1] * inverse[-1]) % m )
    return cmb(n,r,m,g1,g2)
  
if (x+y)%3!=0:
    print(0)
else:
    n=(x+y)//3
    r=x-n
    mod=10**9+7
    print(nCrMOD(n,r,mod))

Submission status: Accepted

Solution code:
# ABC145 D Knight
def factorial_mod(n, mod):
    a = 1
    for i in range(1, n + 1):
        a *= i
        a %= mod
    return a

def comb_mod(n, k, mod):
    if k > n or k < 0:
        return 0
    fact_n = factorial_mod(n, mod)
    fact_k = factorial_mod(k, mod)
    fact_n_k = factorial_mod(n - k, mod)
    return (fact_n * pow(fact_k, mod - 2, mod) * pow(fact_n_k, mod - 2, mod)) % mod

x, y = map(int, input().split())
MOD = 10**9 + 7
if (2 * x - y) % 3 != 0 or (2 * y - x) % 3 != 0:
    print(0)
    exit()
i = (2 * x - y) // 3
j = (2 * y - x) // 3
print(comb_mod(i + j, i, MOD))

Submission status: Accepted

Solution code:
import numpy as np
MOD = 10**9 + 7
def extgcd(a, b):
    r = np.array([1,0,a], dtype=int)
    w = np.array([0,1,b], dtype=int)
    while w[2] != 1:
        q = r[2] // w[2]
        r, w = w, r - q*w
    return w[:2]

def mod_inverse(a, m):
    x, y = extgcd(a, m)
    return (m + x % m) % m

def solve(x, y):
    a = -y + 2*x
    b = 2*y - x
    if (a < 0) or (b < 0):
        return 0
    if a % 3 + b % 3 != 0:
        return 0
    a //= 3
    b //= 3
    n, k = a+b, a
    p, q = 1, 1
    for i in range(k):
        p = p * (n-i) % MOD
        q = q * (i+1) % MOD
    return (p * mod_inverse(q, MOD)) % MOD

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

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 or not (x <= 2*y and y <= 2*x ):
    print(0)
    exit()
    
a = (x + y) //3
n = y - a

print(nCr(a,n))

Submission status: Accepted

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


def comb_mod(n, k, mod):
    if k > n or k < 0:
        return 0
    fact_n = factorial_mod(n, mod)
    fact_k = factorial_mod(k, mod)
    fact_n_k = factorial_mod(n - k, mod)
    return (fact_n * pow(fact_k, mod - 2, mod) * pow(fact_n_k, mod - 2, mod)) % mod


def main():
    x, y = map(int, input().split())
    MOD = 10 ** 9 + 7
    if (2 * x - y) % 3 != 0 or (2 * y - x) % 3 != 0:
        print(0)
        exit()
    i = (2 * x - y) // 3
    j = (2 * y - x) // 3
    print(comb_mod(i + j, i, MOD))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

def main():
    X,Y = map(int,input().split())
    MOD = 10**9+7
    K = 2*X-Y
    L = 2*Y-X
    if K>=0 and L>=0 and (K+L)%3 == 0:
        A = K//3 + L//3
        B = min(K//3,L//3)
        num = num_ = 1
        for i in range(1,B+1):
            num = num * (A+1-i) % MOD
            num_ = num_ * i % MOD
        ans = num * pow(num_,MOD-2,MOD) % MOD
        print(ans)

    else:
        print(0)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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


def mod_inverse(a, m):
    x, _, _ = extgcd(a, m)
    return (m + x % m) % m


def mod_comb(n, k, mod):
    mul, div = 1, 1
    for i in range(k):
        mul *= (n-i)
        div *= (i+1)
        mul %= mod
        div %= mod
    return mul * mod_inverse(div, mod) % mod


def main():
    
    x, y = map(int, readline().split())
    if (x+y)%3!=0:
        print(0)
        return
    n = (x+y)//3
    a, b = (2*y-x)//3, (2*x-y)//3
    if a<0 or b<0:
        print(0)
        return
    print(mod_comb(n, min(a, b), (10**9+7)))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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 main():
    
    x, y = map(int, readline().split())
    if (x+y)%3!=0:
        print(0)
        return
    n = (x+y)//3
    a, b = (2*y-x)//3, (2*x-y)//3
    if a<0 or b<0:
        print(0)
        return
    o = cmb(n, a)
    o = o % (10**9+7)
    print(o)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

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

if not ((2 * X - Y) % 3 == 0 and (2 * Y - X) % 3 == 0 and a >= 0 and b >= 0):
    print(0)
    exit()

maxf = a + b + 1
f = [1 for _ in range(maxf)]
invf = [1 for _ in range(maxf)]

for i in range(1, maxf):
    f[i] = (i * f[i - 1]) % MOD
invf[maxf - 1] = pow(f[maxf - 1], MOD - 2, MOD)

for i in range(maxf - 1, 0, -1):
    invf[i - 1] = (i * invf[i]) % MOD


def comb(a, b):
    return (f[a + b] * invf[a] * invf[b]) % MOD


print(comb(a, b))

Submission status: Accepted

Solution code:
def extgcd(a, b):
    if b == 0:
        return [1, 0, a]
    x, y, g = extgcd(b, a % b)
    return [y, x - a//b * y, g]


def mod_inverse(a, m):
    x, y, _ = extgcd(a, m)
    return (m + x % m) % m


def mod_comb(n, k, mod):
    mul, div = 1, 1
    for i in range(k):
        mul *= (n-i)
        div *= (i+1)
        mul %= mod
        div %= mod
    return mul * mod_inverse(div, mod) % mod


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

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

al = (X + Y) // 3
ch = (2 * Y - X) // 3
if ch < 0 or al - ch < 0:
    print(0)
    exit(0)
print(mod_comb(al, ch, int(1e9+7)))