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:
x,y = map(int,input().split())
di = 10**9+7

def pow_k(xx, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K = (K*xx)%di
        xx = (xx*xx)%di
        n //= 2

    return (K * xx)%di

if (2*y-x)%3>0 and (2*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:
        lis = [i for i in range(a+b+1)]
        lis[0]=1
        for i in range(1,a+b+1):
            lis[i] = (lis[i-1]*lis[i])%di
        lisr = [pow_k(i,di-2) for i in range(max(a,b)+1)]
        lisr[0]=1
        #print(lis,lisr)
        for i in range(1,max(a,b)+1):
            lisr[i] = (lisr[i-1]*lisr[i])%di
        tmp = (lis[a+b]*lisr[a])%di
        print((tmp*lisr[b])%di)

Submission status: Accepted

Solution code:

class ModOperator:
    def __init__(self, MOD: int = 10 ** 9 + 7):
        self.MOD = MOD

    # x^n % MOD
    def mod_pow(self, x: int, n: int):
        bi = str(format(n, "b"))
        res = 1
        a = x
        for i in range(len(bi)):
            if n >> i & 1:
                res = (res * a) % self.MOD
            a = (a * a) % self.MOD
        return res
    
    # x! % MOD
    def mod_fact(self, x: int):
        res = 1
        for i in range(1, x + 1):
            res = res * i % self.MOD
        return res % self.MOD

    # x * (x - 1) * ... * (x - y + 1) % MOD
    def mod_partial_fact(self, x: int, y: int):
        res = 1
        for i in range(x - y + 1, x + 1):
            res = res * i % self.MOD
        return res % self.MOD

    # inverse of a number
    def mod_inv(self, x: int):
        return self.mod_pow(x, self.MOD - 2)
    
    # conmination nCk
    def mod_comb(self, n: int, k: int):
        numerator = self.mod_partial_fact(n, k)
        denomintator = self.mod_fact(k)
        return numerator * self.mod_inv(denomintator) % self.MOD


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

    p = (X + Y) // 3
    q = (X + Y) % 3
    if q == 0 and p <= X <= 2 * p and p <= Y <= 2 * p:
        op = ModOperator()
        res = op.mod_comb(p, X - p)
    else:
        res = 0
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

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

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

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

def comb(n, r):
    #mod入り二項係数
    mod = 10**9+7
    N = 10**6 # 調整
    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]
    for i in range(2, N + 1):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

print(comb(n+m,n))

Submission status: Accepted

Solution code:
mod = 10**9 + 7

def ncr(n, r):
    r = min(r, n-r)
    x, y = 1, 1
    for i in range(r):
        x = (x * (n-i)) % mod
        y = (y * (i+1)) % mod
    
    return x * pow(y, mod-2, mod) % mod


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


if 2*Y - X < 0 or 2*X - Y < 0 or (2*Y - X) % 3 != 0 or (2*X - Y) % 3 != 0:
    print("0")
else:
    M = (2*Y - X) // 3
    N = (2*X - Y) // 3
    print(ncr(M+N,N))

Submission status: Accepted

Solution code:
mod = 10**9 + 7

class Combination:
    def __init__(self, n):
        self.facts = [1 for i in range(n+1)]
        self.invs = [1 for i in range(n+1)]
        
        for i in range(1, n+1):
            self.facts[i] = self.facts[i-1] * i % mod
            self.invs[i] = pow(self.facts[i], mod-2, mod)

    def ncr(self, n, r):
        return self.facts[n] * self.invs[r] * self.invs[n-r] % mod

    def nhr(self, n, r): 
        return self.ncr(n+r-1, n-1)

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

comb = Combination(max(X, Y))

if 2*Y - X < 0 or 2*X - Y < 0 or (2*Y - X) % 3 != 0 or (2*X - Y) % 3 != 0:
    print("0")
else:
    M = (2*Y - X) // 3
    N = (2*X - Y) // 3
    print(comb.ncr(M+N,M))

Submission status: Accepted

Solution code:
# a + 2b = X
# 2a + b = Y
# 3b = 2X-Y
# b = (2X-Y)/3 ①
# 6a + (2X-Y) = 3Y
# 6a = 4Y-2X
# a = (2Y-X)/3 ②

# X=3,Y=3 の時
# b = 1, a = 1


def nCr(n, r, mod):
    if n < 0 or r < 0:
        return 0
    r = min(r, n - r)
    x = y = 1
    for i in range(r):
        x = (x * (n - i)) % mod
        y = (y * (i + 1)) % mod

    return (x * pow(y, mod - 2, mod)) % mod


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

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

a = (2 * X - Y) // 3
b = (2 * Y - X) // 3
if a < 0 or b < 0:
    print(0)
else:
    print(nCr(a + b, a, 10**9 + 7))

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]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

X,Y = map(int,input().split())
if (X+Y)%3 == 0:
  a = (X+Y)//3
  X -= a
  Y -= a
  if X >= 0 and Y >= 0:
    n = X+Y
    r = X
    print(cmb(n, r, p))
    exit()

print(0)

Submission status: Accepted

Solution code:
P = 10**9 + 7
X, Y = map(int, input().split())
if (X + Y) % 3 > 0:
    print(0)
    exit()
n = (X + Y) // 3
x = X - n
y = Y - n
if 0 > x or 0 > y:
    print(0)
    exit()
fact = [0] * (x + y + 1)
inv = [0] * (x + y + 1)
fact_inv = [0] * (x + y + 1)
fact[0], fact[1] = 1, 1
inv[0], inv[1] = 0, 1
fact_inv[0], fact_inv[1] = 1, 1
for i in range(2, x + y + 1):
    fact[i] = (fact[i - 1] * i) % P
print((fact[x + y] * pow(fact[x], P - 2, P) * pow(fact[y], P - 2, P)) % P)

Submission status: Accepted

Solution code:
import math

P = 10**9 + 7
X, Y = map(int, input().split())
if (X + Y) % 3 > 0:
    print(0)
    exit()
n = (X + Y) // 3
x = X - n
y = Y - n
if 0 > x or 0 > y:
    print(0)
    exit()
fact = [0] * (x + y + 1)
inv = [0] * (x + y + 1)
fact_inv = [0] * (x + y + 1)
fact[0], fact[1] = 1, 1
inv[0], inv[1] = 0, 1
fact_inv[0], fact_inv[1] = 1, 1
for i in range(2, x + y + 1):
    fact[i] = (fact[i - 1] * i) % P
    inv[i] = (-inv[P % i] * (P // i)) % P
    fact_inv[i] = (fact_inv[i - 1] * inv[i]) % P
print((fact[x + y] * fact_inv[x] * fact_inv[y]) % P)

Submission status: Accepted

Solution code:
X, Y = map(int, input().split())
n, mod = divmod(X + Y, 3)


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


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


if mod != 0 or not (X <= 2 * Y and Y <= 2 * X):
    print(0)
else:
    r = Y - n
    print(combination(n, r))

Submission status: Accepted

Solution code:
X, Y = map(int, input().split())
n, mod = divmod(X + Y, 3)


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


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


if mod != 0 or not (X <= 2 * Y and Y <= 2 * X):
    print(0)
else:
    r = Y - n
    print(combination(n, r))

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
s = x+y
if s%3 !=0:
    print(0)
    exit()
kai = s // 3
p = x - kai
q = y - kai

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

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

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

a = cmb(kai,p,mod)

print(a)

Submission status: Accepted

Solution code:
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:
    n2x = (2*X - Y) // 3
    n1x = (2*Y - X) // 3
    n = n2x + n1x

    # nCn2xを求める
    def combs(n,n2x,mod):
        facs = [1] * (n+1)
        # invs = [1] * (n+1)
        nfac = 1
        for i in range(1, n+1):
            nfac = nfac * i % mod
            facs[i] = nfac
            # invs[i] = pow(nfac, mod-2, mod)
        return nfac * (pow(facs[n2x], mod-2, mod) * pow(facs[n-n2x], mod-2, mod)) % mod

    print(combs(n, n2x, mod))

Submission status: Accepted

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

import math

mod = 10**9+7

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

# dp = [[0]*(y+1) for _ in range(x+1)]
# dp[0][0] = 1
# for x_tmp in range(1, x+1):
#     for y_tmp in range(1, y+1):
#         print(x_tmp, y_tmp)

#         if x_tmp-2 >= 0 and y_tmp-1 >= 0:
#             dp[x_tmp][y_tmp] += dp[x_tmp-2][y_tmp-1] % mod
#         if x_tmp-1 >= 0 and y_tmp-2 >= 0:
#             dp[x_tmp][y_tmp] += dp[x_tmp-1][y_tmp-2] % mod

# print(dp[-1][-1] % mod)


def comb(n, r):
    X = Y = 1
    if r < 0 or n < r:
        return 0
    if r == 0:
        return 1
    if n-r < r:
        r = n-r
    for i in range(1, r+1):
        Y = Y*i % mod
        X = X*(n-i+1) % mod
    Y = pow(Y, mod-2, mod)
    return X*Y


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

num = min(x, y)-(x+y)//3
if num < 0:
    print(0)
    exit()

# print((x+y)//3, num)
print(comb((x+y)//3, num) % mod)

Submission status: Accepted

Solution code:
def modinv(a,m):
    b, u, v = m, 1, 0
    while b:
        t = a//b
        a -= t*b
        a,b = b,a
        u -= t * v
        u,v = v,u
    u %= m
    return u


N_MAX = 10**6
MOD = 10**9 + 7
fac, finv, inv = [0]*N_MAX, [0]*N_MAX, [0]*N_MAX
def com_init():
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, N_MAX):
        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():
    x, y = map(int, input().split()) 
    com_init()

    a3 = -x+2*y
    b3 = 2*x-y

    if a3%3 != 0 or b3%3 != 0:
        print(0) 
        return

    a = a3//3
    b = b3//3

    print(com(a+b, min(a,b)))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial#, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def mod_cmb(n: int, k: int, p: int) -> int:
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if (k > n - k):
        return mod_cmb(n, n - k, p)
    c = d = 1
    for i in range(k):
        c *= (n - i)
        d *= (k - i)
        c %= p
        d %= p
    return c * pow(d, p - 2, p) % p

def main():
    x, y = i_map()

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

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import factorial
MOD = 10**9+7

def com(n, r):
    X = Y = 1
    if r < 0 or n < r:
        return 0
    if n-r < r:
        r = n-r
    for i in range(1, r+1):
        Y = Y*i % MOD
        X = X*(n-i+1) % MOD
    Y = pow(Y, MOD-2, MOD)
    return X*Y

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

dif = max(x, y) - min(x, y)
small = min(x, y)
tie = small-dif
res = tie % 3
num = tie / 3  

if res != 0:
  print(0)
else:
  print(com(int(num*2+dif), int(num))%MOD)

Submission status: Accepted

Solution code:
# D - Knight

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

n, r1 = divmod(2 * y - x, 3)
m, r2 = divmod(2 * x - y, 3)

def com(n, r):
    X = Y = 1
    if r < 0 or n < r:
        return 0
    if n - r < r:
        r = n - r
    for i in range(1, r + 1):
        Y = Y * i % MOD
        X = X * (n - i + 1) % MOD
    Y = pow(Y, MOD - 2, MOD)
    return X * Y

if r1 != 0 or r2 != 0:
    print(0)
else:
    print(com(n + m, n) % MOD)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10 ** 7)

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

class Combination:
    def __init__(self, max_n=100007, mod=mod):
        self.mod = mod
        self.fac = [0] * max_n
        self.finv = [0] * max_n
        self.inv = [0] * max_n

        self.fac[0] = 1
        self.fac[1] = 1
        self.finv[0] = 1
        self.finv[1] = 1
        self.inv[1] = 1
        for i in range(2, max_n):
            self.fac[i] = self.fac[i - 1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i - 1] * self.inv[i] % self.mod
    
    def choose(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return self.fac[n] * (self.finv[k] * self.finv[n - k] % self.mod) % self.mod


x, y = na()

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

n, m = -1, -1
for i in range(10 ** 6 + 7):
    if (x - i) // 2 + 2 * i == y:
        n = i
        m = (x - i) // 2
        break

if n < 0 or m < 0:
    print(0)
    exit()
c = Combination(10 ** 6 + 7)
print(c.choose(n + m, n) % 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
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
 
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
 
 
if (X+Y)%3 !=0:
  print(0)
  
else:
  n=(X+Y)//3
  r=(-2*X+Y)//(-3)
  ans=cmb(n,r,mod)
  print(ans)

Submission status: Accepted

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

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

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

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


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

Submission status: Accepted

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

def nCk(n,k):
  MAX_N=n+5
  fac = [1,1] + [0]*MAX_N
  finv = [1,1] + [0]*MAX_N
  inv = [0,1] + [0]*MAX_N
  for i in range(2,MAX_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
  
  if n<k:
    return 0
  if n<0 or k<0:
    return 0
  return fac[n] * (finv[k] * finv[n-k] % mod) % mod

n=(y-0.5*x)/1.5
if int(n)!=n:
    print(0)
else:
    m=(y+x)//3
    l=int(n)
    print(nCk(m,l))

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

A = (2 * Y - X) // 3
B = (2 * X - Y) // 3

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

Submission status: Accepted

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

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

class Mint(object):
    def cmb(self, n, r, mod: int = 10 ** 9 + 7):
        if (r < 0) or (r > n):
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n - r] % mod

    def cmb_prep(self, N: int, mod: int = 10 ** 9 + 7):
        self.g1 = [1, 1]  # 元テーブル
        self.g2 = [1, 1]  # 逆元テーブル
        inverse = [0, 1]  # 逆元テーブル計算用テーブル

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

    def cmb_(n, r):
        """ 普通にnCrを求める
        >>> p = Mint()
        >>> p.cmb_(10, 2)
        45
        """
        from operator import mul
        from functools import reduce

        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


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

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

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

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

mint = Mint()
mint.cmb_prep(n + m, mod)

print(mint.cmb(n+m, n, mod))

Submission status: Accepted

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

def nCr(n,r,p):
    r=min(r,n-r)
    if r==0:
        return 1
    x,y=1,1
    for i in range(r):
        x=x*(n-i)%p
        y=y*(i+1)%p
    return x*pow(y,p-2,p)%p

if (x + y) % 3 != 0:
    print(0)
else:
    ans = 0
    n = (x + y)//3
    for i in range(n+1):
        a = n - i
        b = i
        if a + 2 * b == x and 2 * a + b == y:
            ans += nCr(n, min(a, b), 10**9 + 7)
            ans = ans % (10**9 + 7)
    print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7
x, y = map(int, input().split())
n, r1 = divmod(2*y-x, 3)
m, r2 = divmod(2*x-y, 3)


def com(n, r):
    X = Y = 1
    if r < 0 or n < r:
        return 0
    if n-r < r:
        r = n-r
    for i in range(1, r+1):
        Y = Y*i % MOD
        X = X*(n-i+1) % MOD
    Y = pow(Y, MOD-2, MOD)
    return X*Y


if r1 or r2:
    print(0)
else:
    print(com(n+m, n) % MOD)

Submission status: Accepted

Solution code:
MOD = 10**9+7
X, Y = map(int, input().split())
x, y = X, Y
while 0 <= y:
    if x == 2*y:
        break
    x += 1
    y -= 1
else:
    print(0)
    exit()


def com(n, r):
    X = Y = 1
    if r < 0 or n < r:
        return 0
    if n-r < r:
        r = n-r
    for i in range(1, r+1):
        Y = Y*i % MOD
        X = X*(n-i+1) % MOD
    Y = pow(Y, MOD-2, MOD)
    return X*Y


print(com(x//2, x-X) % 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
x,y=map(int,input().split())
g1=[1,1]
g2=[1,1]
inverse=[0,1]

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

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

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from functools import reduce
def mod_comb4(n,r,mod=10**9+7):
    if r==1:return n
    elif r==0:return 1
    else:
        num=reduce(lambda x,y:x*y%mod,range(n,n-r,-1))
        den=reduce(lambda x,y:x*y%mod,range(1,r+1))
        return num*pow(den,mod-2,mod)%mod
def main():
    x,y=map(int,input().split())
    mod=10**9+7
    n=2*x-y
    m=2*y-x
    if n%3==0 and m%3==0 and n>=0 and m>=0:
        print(mod_comb4(n//3+m//3,n//3,mod))
    else:
        print(0)


if __name__=='__main__':
    main()

Submission status: Accepted

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

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

    return result % mod

a=(-x+2*y)/3
b=(2*x-y)/3
if a<0 or b<0 : print(0) ; exit()
if a%1!=0 or b%1!=0:
    print(0) 
    exit()
a=int(a) ; b=int(b)
print(C(a+b,a))

Submission status: Accepted

Solution code:
from scipy.misc import comb
def modpow(a, n, p):
  if n == 1:
    return a % p 
  elif n % 2 == 1:
    return a * modpow(a, n-1, p) % p
  else:
    return modpow(a, n//2, p) **2 % p
x, y = map(int, input().split())
t = (2*y-x)/3
s = (2*x-y)/3
if not t.is_integer() or t<0 or not s.is_integer() or s<0:
  print(0)
else:
  t = int(t)
  s = int(s)
  bunsi = 1
  for i in range(s+t-s+1, s+t+1):
    bunsi = bunsi * i % 1000000007
  bunbo = 1
  for i in range(1, s+1):
    bunbo = bunbo * i % 1000000007
  ans = bunsi * modpow(bunbo, 1000000007-2, 1000000007) % 1000000007
  print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
large_p = 10**9 + 7

def comb_mod(n, r, large_p):
    a, b = 1, 1
    r = min(r, n - r)
    for i in range(r):
        a = a * (n - i) % large_p
        b = b * (r - i) % large_p
    return a * pow(b, large_p - 2, large_p) % large_p

def main():
    x, y = map(int, input().split())
    if (x + y) % 3 != 0:
        print(0)
        sys.exit()
    p1, p2 = 0, 0
    for i1 in range(0, x + 1):
        if x - i1 == (y - i1 * 2) * 2:
            p1 = i1
            p2 = y - i1 * 2
            break
    if p1 < 0 or p2 < 0 or (p1 == 0 and p2 == 0):
        print(0)
        sys.exit()

    r = comb_mod(p1 + p2, p1, large_p)
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
def cmb(n, r, mod):
    r = min(r, n - r)
    x = 1
    y = 1
    for i in range(r):
        x = x * (n - i) % mod
        y = y * (i + 1) % mod
    y = pow(y, mod-2, mod)
    return x * y % mod
"""
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
"""
X1, Y1 = map(int, input().split())

if X1 >= Y1:
  X = X1
  Y = Y1
  pass
else:
  X = Y1
  Y = X1
if X > 2 * Y:
  print(0)
  exit()
else:
  pass

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

if (2 * X - Y) % 3 != 0 or (2 * Y - X) % 3 != 0:
  print(0)
  exit()
else:
  ans = cmb(m + n, n, 10 ** 9 + 7)
print(ans)

Submission status: Accepted

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

def modpow(a, n):
    ret = 1
    while n > 0:
        if n & 1:
            ret = ret * a % MOD
        a = a * a % MOD
        n >>= 1
    return ret

def modinv(a):
    return modpow(a, MOD - 2)

def modfac(x):
    ret = 1
    for i in range(2, x + 1):
        ret *= i
        ret %= MOD
    return ret

ans = 0
if (X + Y) % 3 == 0:
    a = (2 * X - Y) // 3
    b = (2 * Y - X) // 3
    if a >= 0 and b >= 0:
        n = a + b
        r = a
        ans = modfac(n)
        ans *= modinv(modfac(n - r) * modfac(r))
        ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
a,b = map(int,input().split())
def fac(n):
    p = 1
    for i in range(1,n+1):
        p = (p*i) % (10**9+7)
    return p
if (2*a-b) % 3 == 0 and (-a+2*b) % 3 == 0 and 2*a-b>=0 and -a+2*b >= 0:
    x = (2*a-b) // 3
    y = (-a+2*b) // 3
    print((fac(x+y)*pow(fac(x),10**9+5,10**9+7)*pow(fac(y),10**9+5,10**9+7))%(10**9+7))
else:
    print(0)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc145/tasks/abc145_d

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


# 2項係数
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

# 階乗の配列 i番目の項目はi!
fact = [1, 1]

# 逆元の配列 i番目の項目は(i!)^(-1)
factinv = [1, 1]

# 逆元計算用の配列 i番目の項目は
# mod pを法とし、iの逆元((i)^(-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)

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

Submission status: Accepted

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


def main():
    X, Y = map(int, input().split())
    if (X + Y) % 3 != 0:
        print(0)
        exit()
    n = (X+Y) // 3
    if X < n or Y < n:
        print(0)
        exit()
    r = X - n

    # nCrを計算する
    a = [None] * (n+1)
    inva = [None] * (n+1)
    a[0] = 1
    inva[0] = 1
    p = 10**9 + 7

    for i in range(1, n+1):
        a[i] = i * a[i-1] % p
        inva[i] = pow(i, p-2, p) * inva[i-1] % p

    ans = (a[n] * inva[r] % p) * inva[n-r] % p
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
x, y  = map(int, input().split())
import itertools
mod = 10**9 + 7
def comb(a,b):
    x,y = 1,1
    for i in range(a):
        x *= (a+b-i)
        y *= (i+1)
        x %= mod 
        y %= mod
    gyakugen = pow(y,mod-2,mod)
    return x*gyakugen %mod
if (2*y-x) % 3 !=  0 or (2*x-y) % 3 != 0 or (2*y -x) < 0 or (2*x - y)<0:
    print(0)
else:
    a = int((2*y - x)/3)
    b = int((2*x - y)/3)
    print(int(comb(a,b)))

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

X,Y = inputIL()

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

x = n*2-Y
y = n-x

print(nCr(x+y,x))

Submission status: Accepted

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

MOD = 1000000007
if (2*X-Y)%3!=0:
    print(0)
    sys.exit()

A = int((2*X-Y)/3)
B = int(X-2*A)

if A<0 or B<0:
    print(0)
    sys.exit()

ans = 1
inv = 1
for i in range(B):
    ans = ans * (A+B-i) %MOD
    inv = inv * (i+1) %MOD

ans = ans * pow(inv, MOD-2, MOD) %MOD
print(ans)

Submission status: Accepted

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

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

if m.is_integer() == False or n.is_integer() == False:
  print(0)
  exit()
if m < 0 or n < 0:
  print(0)
  exit()

def comb(n, k):
  if k > n - k:
    return comb(n, n - k)
  mul, div = 1, 1
  for i in range(k):
    mul = mul * (n - i) % mod
    div = div * (k - i) % mod
  return mul * pow(div, mod-2, mod) % mod

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

Submission status: Accepted

Solution code:
import math

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

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