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
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

x,y=mii()

if (x+y) %3!=0:
    print(0)
    exit()
if max(x,y)/min(x,y)>2:
    print(0)
    exit()

def nCk(n, k, mod=10 ** 9 + 7):
    if n < k:
        return 0
    k = min(k, n - k)
    numer = 1
    for x in range(n - k + 1, n + 1):
        numer = (numer * x) % mod
    denom = 1
    for x in range(1, k + 1):
        denom = (denom * x) % mod
    return numer * pow(denom, mod - 2, mod) % mod

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

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

Submission status: Accepted

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

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 (X+Y)%3==0 and (X+Y)//3>=abs(X-Y):
    ans=combination((X+Y)//3,( (X+Y)//3 - abs(X-Y) )//2)
    print(ans%1000000007)
else:
    print(0)

Submission status: Accepted

Solution code:
from functools import reduce
x, y = map(int, input().split())
mod = pow(10,9)+7

min_value = min(x, y)
max_value = max(x, y)
#print(min_value, max_value)
dif_value = max_value - min_value
#print(dif_value)
a_value   = min_value - dif_value
a_num     = int(a_value*2*(1/3))
#print(a_value, a_num)
n = dif_value + a_num
r = int(a_num*0.5)
#print(n, r)

def nCr(n,r,DIV):
  if r<n-r:
    r=n-r
  if r==0:
    return 1
  f=lambda x,y:x*y%DIV
  X=reduce(f,range(n-r+1,n+1))
  Y=reduce(f,range(1,r+1))
  return X*pow(Y,DIV-2,DIV)%DIV

if a_value % 3 == 0:
    print(nCr(n, r, mod))
else:
    print(0)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
from itertools import permutations, combinations, accumulate
from collections import deque
from heapq import heappush, heappop, heapify
from collections import deque

input = sys.stdin.readline
sys.setrecursionlimit(10**6)

MOD = 10**9 + 7

def cmbmod(n, r, k):
    #nCr mod kを求める（kは素数）
    p, q = 1, 1
    for i in range(r):
        p = p * (n-i) % k
        q = q * (r-i) % k
    return p * pow(q, k-2, k) % k

def main():
    x, y = tuple(map(int,input().split()))
    ok = 0
    ng = x + 1
    ans = 0

    if 2*y - x >= 0 and 2 * x - y >= 0:
        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            if 2*y - x >= 3*mid:
                ok = mid
            else:
                ng = mid

        a = ok
        b = y - 2 * ok
        if a + 2*b == x and 2*a + b == y:
            ans = cmbmod(a + b, a, MOD)


    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
X,Y = map(int,input().split())
mod = pow(10,9)+7
n,m = -1,-1
for i in range(X+1):
    if (X-i)==2*(Y-2*i):
        n,m = i,Y-2*i
if n==-1:print(0)
else:
    a,b,m = 1,1,n+m
    for i in range(1,n+1):
        a=(a*m)%mod
        b=(b*i)%mod
        m-=1
    b = pow(b,mod-2,mod)
    print((a*b)%mod)

Submission status: Accepted

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

n = (-X+2*Y)//3
m = (2*X-Y)//3
MOD = 10**9+7
    
def comb(n,r,MOD):
    x = n+1
    y = min(r,n-r)
    
    numer = 1
    denom = 1
    
    for i in range(1,r+1):
        numer = numer*(x-i)%MOD
        denom = denom*(i)%MOD
    
    return numer * pow(denom,MOD-2,MOD) % MOD
  
import sys

if n < 0 or m < 0:
    print(0)
    sys.exit()
if (X+Y)%3 != 0:
    print(0)
    sys.exit()
    
print(comb(n+m,n,MOD))

Submission status: Accepted

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

mod = 10 ** 9 + 7


def choose(n, r):
    cx = 1
    cy = 1
    for i in range(r):
        cx = cx * (n - i) % mod
        cy = cy * (i + 1) % mod
    cy = pow(cy, mod - 2, mod)
    return cx * cy % mod


if (x + y) % 3 != 0:
    print(0)
    exit()
else:
    n = (x + y) // 3
    x -= n
    y -= n
    if x < 0 or y < 0:
        print(0)
        exit()
    print(choose(x + y, x))

Submission status: Accepted

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

Submission status: Accepted

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

mod = 10 ** 9 + 7


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


ans = 0

if (X + Y) % 3 == 0:
    n = (2 * Y - X) // 3
    m = (2 * X - Y) // 3
    if min(n, m) >= 0:
        ans = choose(n + m, n)


print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

if 2 * y < x:
	print(0)
elif y > 2 * x:
	print(0)
elif (x + y) % 3 != 0:
	print(0)
else:
	p = 10**9 + 7
	s = int((2 * x - y) / 3)
	t = int((2 * y - x) / 3)
	u = min(s, t)
	v = s + t
	
	inv = [0] * (u + 1)
	inv[0] = 0
	ans = 1
	for i in range(1, u + 1):
		inv[i] = pow(i, p - 2, p)
		ans = (ans * (v - i + 1) * inv[i]) % p
	
	print(ans)

Submission status: Accepted

Solution code:
X,Y=map(int,input().split())
if (X+Y)%3!=0:
  print(0)
  exit()
A=int((X+Y)/3)
B=int((2*Y-X)/3)
if A<0 or B<0:
  print(0)
  exit()
MOD=10**9+7
def comb(n,k):
  tmp=1
  for i in range(n-k+1,n+1):
    tmp*=i
    tmp%=MOD
  for i in range(1,k+1):
    tmp*=pow(i,MOD-2,MOD)
    tmp%=MOD
  return tmp
ans = comb(A,B)
print(ans%MOD)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7


def mod_pow(a, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        half_p = p // 2
        half = mod_pow(a, half_p)
        return half * half % mod
    else:
        return a * mod_pow(a, p - 1) % mod


def calc_comb(a, b):
    if b > a - b:
        return calc_comb(a, a - b)

    ans_mul = 1
    ans_div = 1
    for i in range(b):
        ans_mul *= (a - i)
        ans_div *= (i + 1)
        ans_mul %= mod
        ans_div %= mod

    ans = ans_mul * mod_pow(ans_div, mod - 2) % mod
    return ans


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

Submission status: Accepted

Solution code:
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
x,y = map(int,input().split())
sum = 0
if x%2 == 1:
  for k in range((x+1)//2):
    k = 2*k +1
    l = (x-k)//2
    if l+2*k == y:
      sum += cmb(k+l,l,mod)
      sum = sum%mod
  print(sum)
if x%2 == 0:
  for k in range(x//2):
    k = 2*k
    l = (x-k)//2
    if l+2*k == y:
      sum += cmb(k+l,l,mod)
      sum = sum%mod
  print(sum)

Submission status: Accepted

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

mod = 1000000007  # type: int


def comb_mod(n, k, mod):
    numerator = 1
    denominator = 1
    for i in range(k):
        numerator = (numerator * (n - i)) % mod
        denominator = (denominator * (i + 1)) % mod

    return (numerator * pow(denominator, mod - 2, mod)) % mod


def solve(X: int, Y: int):
    n = (2 * Y - X) / 3
    m = (2 * X - Y) / 3

    if n < 0 or m < 0 or (X + Y) % 3 != 0:
        print(0)
    else:
        result = comb_mod(int(n + m), int(n), mod)
        print(result)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(X, Y)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#python3
from math import factorial
from math import floor
MOD = int(1e9+7)

def comb(n, m, mod):
    comb_a = 1
    for i in range(m): 
        comb_a *= (n-i)
        comb_a %= mod
    comb_tmp = factorial(m) 
    comb_b = pow(comb_tmp, mod-2, mod)
    return (comb_a * comb_b)%mod
def main():
    x, y = map(int, input().split())
    k = (2*x-y)/3
    l = (2*y-x)/3

    if floor(k) - k != 0:
        print(0)
        return
    if floor(l) - l != 0:
        print(0)
        return 
    if k<0:
        print(0)
        return
    if l<0:
        print(0)
        return
    k = int(k)
    l = int(l)
    print(comb(k+l, k, MOD)%MOD) 

main()

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

x, y = MAP()


def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % mod
    elif y % 2 == 0:
        return power(x, int(y/2)) ** 2 % mod
    else:
        return power(x, int((y-1)/2)) ** 2 * x % mod
# nCaとしたときのaのmaxがa_max
a_max = 10 ** 6
# a, bの最大値+2
fact = [1] * (a_max + 2)
# 逆元
for i in range(1, a_max + 1):
    fact[i] = (fact[i-1] * i) % mod
# combination
def C(n, a):
    tmp = 1
    for i in range(n, n-a, -1):
        tmp = (tmp * i) % mod
    return tmp * power(fact[a], mod - 2)


if (x + y) % 3 != 0:
    print(0)
else:
    A =  (2 * x - y) // 3
    B = (-x + 2 * y) // 3
    # ここも必要
    if A < 0 or B < 0:
        print(0)
    else:
        N = A + B
        print(C(N, A) % mod)

Submission status: Accepted

Solution code:
def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0

    fac = [0] * (n + 1)
    fac[0] = 1
    for i in range(n):
        fac[i + 1] = fac[i] * (i + 1) % p
    return fac[n] * pow(fac[n - k], p - 2, p) * pow(fac[k], p - 2, p) % p


p = 1000000007

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

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

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

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

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

Submission status: Accepted

Solution code:
class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        if n < r:
            return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

def main():
    X, Y = map(int, input().split())
    if (X + Y) % 3 != 0:
        print(0)
        exit()
    if (2 * X - Y) < 0 or (2 * Y - X) < 0:
        print(0)
        exit()
    
    M = (2 * X - Y) // 3
    N = (2 * Y - X) // 3
    comb = Combination(10 ** 6)

    ans = comb(M + N, M)
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
mod=10**9+7
def nCr_mod(n,r,mod):
  x=1
  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
if (x+y)%3!=0:
  print(0)
else:
  m=int((2*x-y)/3)
  n=int(x-2*m)
  if m<0 or n<0:
    print(0)
  else:
    print(nCr_mod(m+n,n,mod))

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7  # mod素数
def nCr(n, r, mod):
  ret = [1]*(r+1)
  for i in range(1, r+1):
    ret[i] = (ret[i-1] * (n-i+1) * pow(i,mod-2,mod)) % mod
  return ret
    
X,Y=map(int,input().split())
x,y = 2*X-Y, 2*Y-X
if x<0 or y<0 or x%3!=0 or y%3!=0:
  ret=0
else:
  x,y=x//3,y//3
  nCrl = nCr(x+y, min(x,y), mod)
  ret=nCrl[min(x,y)]
print(ret)

Submission status: Accepted

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

def c(n, r):
    p, q = 1, 1
    for i in range(r):
        p = p*(n-i)%mod
        q = q*(i+1)%mod
    return p * pow(q, mod-2,mod)%mod

if (x+y)%3 !=0 or m*n < 0:
    print(0)
else:
    print(c(m+n,n))

Submission status: Accepted

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

# (i+1,j+2)の移動をa回
# (i+2,j+1)の移動をb回
# X=a+2b
# Y=2a+b
# となるa,bが存在するか？
# b=(2X-Y)/3が整数となればOK

b=(2*X-Y)/3
if not float.is_integer(b):
  print(0)
  exit(0)
  
b=int(b)
a=X-2*b

# aとbの回数が決まったので、a+bCmin(a,b)をやればいい

DIV=10**9+7
from functools import reduce
def nCr(n,r,DIV):
  if r<n-r:
    r=n-r
  if r==0:
    return 1
  f=lambda x,y:x*y%DIV
  X=reduce(f,range(n-r+1,n+1))
  Y=reduce(f,range(1,r+1))
  return X*pow(Y,DIV-2,DIV)%DIV

print(nCr(a+b,b,DIV))

Submission status: Accepted

Solution code:
def com(N,K,mod):
    n=N
    K=min(K,N-K)
    k=K
    X=1  #分子
    Y=1  #分母
    for _ in range(K):
        X*=n
        X%=mod
        n-=1
    for _ in range(K):
        Y*=k
        Y%=mod
        k-=1
    Y=loop_pow(Y,mod-2,mod)  #Y**(mod-2) mod(mod)
    return X*Y%mod  #nCk mod(mod)

def loop_pow(x,n,mod):
    if n==0:
        return 1
    if n%2==0:
        t=loop_pow(x,n//2,mod)
        return (t*t)%mod
    return x*loop_pow(x,n-1,mod)%mod

def main():
    X,Y=map(int,input().split())
    if (X+Y)%3!=0:
        print(0)
    else:
        n=(2*Y-X)//3
        m=(2*X-Y)//3
        if n<0 or m<0:
            print(0)
        else:
            mod=10**9+7
            print(com(n+m,n,mod))

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from heapq import heapify, heappop, heappush
from random import randint
from collections import defaultdict
from itertools import accumulate
from fractions import gcd
from collections import defaultdict
import sys
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

MOD = 10**9 + 7
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
 
size = 10**6 + 1
g1, g2, inverse = [0]*size, [0]*size, [0]*size
 
g1[:2] = [1, 1] # 元テーブル
g2[:2] = [1, 1] #逆元テーブル
inverse[:2] = [0, 1] #逆元テーブル計算用テーブル
 
for i in range(2, size):
    g1[i] =  ( g1[i-1] * i ) % MOD 
    inverse[i] = (-inverse[MOD % i] * (MOD//i) ) % MOD 
    g2[i] =  (g2[i-1] * inverse[i]) % MOD

X, Y = inpl()
if (X > Y):
    X, Y = Y, X

if (min(X, Y) < abs(Y - X) or (X+Y)%3 != 0):
    print(0)
else:
    a, b = 0, 0
    Z = Y-X
    a = (X-Z)//3
    b = (X-Z)//3 + Z
    print(cmb(a+b, a, MOD)%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())

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

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


print(cmb(a+b,a,mod))

Submission status: Accepted

Solution code:
X,Y = map(int, input().split())
m = (-X+2*Y)//3
n = (2*X-Y)//3

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 m*n<0:
  print(0)
else:
  print(combination(m+n,n))

Submission status: Accepted

Solution code:
#combination
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())
X, Y = max(X, Y), min(X, Y)
mod = 10 ** 9 + 7
if (2 * Y - X) % 3 != 0:
    ans = 0
elif 2 * Y < X:
    ans = 0
else:
    a = (X + Y)//3
    b = min((2 * X - Y)//3, (2 * Y - X)//3)
    ans =cmb(a, b)
print(ans%mod)

Submission status: Accepted

Solution code:
def cmb(n, r, p):
    if r<0 or n<r:
        return 0
    r=min(r, n-r)
    return fact[n]*factinv[r]*factinv[n-r]%p

mod=10**9+7
MAXN=2*10**6+10
fact=[1, 1]
factinv=[1, 1]
inv=[0, 1]

for i in range(2, MAXN+1):
    fact.append((fact[-1]*i)%mod)
    inv.append(-inv[mod%i]*(mod//i)%mod)
    factinv.append((factinv[-1]*inv[-1])%mod)

x,y=map(int, input().split())
res=0
if (x+y)%3==0:
    m=(2*x-y)//3
    n=(2*y-x)//3
    res=cmb(m+n,m,mod)
print(res)

Submission status: Accepted

Solution code:
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


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

if (X + Y) % 3 == 0:
    if X <= 2*Y and 2*X >= Y:
        n = (X+Y) // 3
        r = n // 2 - abs(X-Y) // 2
        print(cmb(n, r, p))

    else:
        print(0)
else:
    print(0)

Submission status: Accepted

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

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

print(nCr(int(f),int(n)))

Submission status: Accepted

Solution code:
mod=10**9+7
x,y=map(int,input().split())
if y>=x:
  x,y=y,x
mods=[1]
rmods=[1]
for i in range(1,x+1):
  tmp=i*mods[-1]
  tmp%=mod
  mods.append(tmp)
for i in range(1,x+1):
  tmp=pow(i,mod-2,mod)*rmods[-1]
  tmp%=mod
  rmods.append(tmp)
ans=0
for i in range(x+1):
  n=i
  if (x-i)%2==1:
    continue
  m=(x-i)//2
  if 2*n+m!=y:
    continue
  else:
    tmp=mods[n+m]*rmods[n]*rmods[m]
    tmp%=mod
    ans+=tmp
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
def mod(n,p):
    return n % p
#ある数をAで割ったとき，その数をpで割ったときの余りを求めるのにかけるべき数を返す
def bunbo(A, p): 
    # p-2を2進数にする
    pp = p-2
    pb = list(str(format(pp, 'b')))
    # ひっくりかえす
    pb.reverse()
    # pbの要素の数lとして，A^1, A^2, A^4, A^8, ..., A^(2^l)をpで割った余りを求める
    lpp = [mod(A,p)]
    for _ in range(len(pb)-1):
        lpp.append(mod((lpp[-1] ** 2), p))
    # 必要なやつだけ足して，x=(A^(p-2)をpで割った余り)を求める
    x = 1
    for i in range(len(pb)):
        if pb[i] == '1':
            x *= lpp[i]
    return mod(x, p)

def nckp(n, k, p):
    # 0!, 1!, 2!, 3!, ..., n!をリストに入れる
    nk = [1]
    for i in range(1,n+1):
        nk.append(mod((nk[-1] * i), p))
    return mod((nk[n] * bunbo(nk[k], p) * bunbo(nk[n-k], p)),p)

X, Y = map(int,input().split())
if (2*X-Y) % 3 != 0 or (2*Y-X) % 3 != 0:
    print(0)
elif 2*X-Y < 0 or 2*Y-X < 0:
    print(0)
else:
    a = (2*Y-X) // 3
    b = (2*X-Y) // 3
    n = a + b
    k = a
    p = 1000000007
    print(nckp(n, k, p))

Submission status: Accepted

Solution code:
import math
import numpy as np

def cmb(n, r, mod):
  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:

  A = np.array([[1, 2],[2, 1]])
  b = np.array([x, y])
  N = np.linalg.solve(A, b)
  if N[0].is_integer() == True and N[1].is_integer() == True and N[0] >=0 and N[1] >=0:
      print(cmb(int(N[0]+N[1]),int(N[0]),mod))
  else:
      print(0)
else:
  print(0)

Submission status: Accepted

Solution code:
import numpy as np
MOD = 10 ** 9 + 7

def pow_mod(value, exp):
    r = 1
    while exp:
        if exp % 2:
            r *= value
            r %= MOD
        value *= value
        value %= MOD
        exp //= 2
    return r

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

x, y = map(int, input().split())
if (x + y) % 3 or x > y * 2 or y > x * 2:
    print('0')
    exit()

a, b = map(int, np.linalg.solve([[2, 1], [1, 2]], [x, y]))
ans = fact[a + b] % MOD
ans *= pow_mod(fact[a], MOD-2)
ans %= MOD

ans *= pow_mod(fact[b], MOD-2)
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7

#modに対応して高速なコンビネーションが求められる
# 階乗 & 逆元計算



d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

X,Y = LI()

if (X + Y) % 3 != 0:
    ans = 0
else:
    n = 10 ** 6
    factorial = [1]
    inverse = [1]
    for i in range(1, n+2):
        factorial.append(factorial[-1] * i % mod)
        inverse.append(pow(factorial[-1], mod-2, mod))

    def combinations_count(n,r):
        if n-r < 0:
            return 0
        return factorial[n]*inverse[r]*inverse[n-r]%mod
    m = int(X * 2 / 3 - Y / 3)
    n = int(Y * 2 / 3 - X / 3)
    if (X+Y) / 3 > X or (X + Y) / 3 > Y or m < 0 or n < 0:
        ans = 0
    else:
        ans = combinations_count((X + Y)//3, n)
print(ans)

Submission status: Accepted

Solution code:
def cmb(n, k, mod, fac, infac):
  k = min(k,n-k)
  return fac[n] * infac[k] * infac[n-k] % mod

def tables(mod, n):
  fac = [1, 1] 
  infac = [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)
    infac.append((infac[-1] * inverse[-1]) % mod)
  return fac,infac

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

if X > Y:
  X, Y = Y, X

move = X + Y

if move % 3 != 0:
  print(0)
else:
  total = move // 3
  n = X - total
  
  if n < 0:
    print(0)
    
  else:
    MOD = 10 ** 9 + 7
    fac, infac = tables(MOD, total)
    ans = cmb(total, n, MOD, fac, infac)
    
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

MAX = 10**9 + 7

def pow_mod_p(n, k, p):
  x = 1
  while k:
    if k % 2 == 1:
      x *= n
      x %= p
    n **= 2
    n %= p
    k >>= 1
  return x

def comb_mod_p(n, k, p):
  x = 1
  for ik in range(k):
    x *= ((n-ik) * pow_mod_p(ik+1, p-2, p))
    x %= p
  return x

def main():
  x, y = map(int, input().strip().split())
  m = (2*x -   y)/3
  k = ( -x + 2*y)/3
  if m - int(m) != 0 or k - int(k) != 0 \
     or m < 0 or k < 0 :
    print(0)
    return 
  m, k = map(int, [m, k])
  if m < k:
    m, k = k, m
  print(comb_mod_p((m+k), k, MAX))
  
  
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:

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


def prime_mod(n, m):
    S = 1
    for i in range(1, n+1):
        S *= i
        S %= m
    return S


def prime_inv_mod(n, m):
    invs = [0] * (n + 1)
    invs[1] = 1
    for i in range(2, n + 1):
        invs[i] = m - invs[m % i] * (m//i) % m
    return invs


a = 2 * Y - X
b = 2 * X - Y
if a % 3 != 0 or b % 3 != 0 or a < 0 or b < 0:
    print(0)
else:
    a //= 3
    b //= 3
    upper = prime_mod(a+b, mod)
    mod_inv = prime_inv_mod(max(a, b), mod)

    lower1 = 1
    lower2 = 1
    for i in range(1, a + 1):
        lower1 *= mod_inv[i]
        lower1 %= mod
    for i in range(1, b + 1):
        lower2 *= mod_inv[i]
        lower2 %= mod

    print((upper*lower1*lower2) % mod)

Submission status: Accepted

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

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

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

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

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
    
if (-X+2*Y)%3 == 0 and (2*X-Y)%3 == 0:
    print(cmb(n+m,n,mod))
else:
    print(0)

Submission status: Accepted

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

if (X + Y) % 3 != 0:
    print(0)
    exit()
if abs(X - Y) > (X + Y) // 3:
    print(0)
    exit()
    
n = (X + Y) // 3 + 1
k = ((X - Y) + n + 1) // 2
SIZE = max(n, k)

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

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

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

print(comb(n - 1, k - 1, MOD))

Submission status: Accepted

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

if (X + Y) % 3 != 0:
    print(0)
    exit()
if abs(X - Y) > (X + Y) // 3:
    print(0)
    exit()
    
n = (X + Y) // 3 + 1
k = ((X - Y) + n + 1) // 2


SIZE = max(n, k)

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

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

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

print(comb(n - 1, k - 1, MOD))

Submission status: Accepted

Solution code:
M=10**9+7
x,y=map(int,input().split())
ans=0
if (x+y)%3==0:
  a=(2*y-x)//3
  b=(2*x-y)//3
  if a>=0 and b>=0:
    f1,f2=1,1
    for i in range(a+1,a+b+1):
      f1*=i
      f1%=M
    for i in range(1,b+1):
      f2*=i
      f2%=M
    ans=f1*pow(f2,M-2,M)

print(ans%M)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

inv = [0] * 1000000
inv[1] = 1
for i in range(2, 1000000):
    inv[i] = (MOD - (MOD // i) * inv[MOD % i] % MOD) % MOD

fact = [0] * 1000000
finv = [0] * 1000000
fact[0] = 1
finv[0] = 1
for i in range(1, 1000000):
    fact[i] = (i * fact[i - 1]) % MOD
    finv[i] = (inv[i] * finv[i - 1]) % MOD


def modcomb(n, r):
    if n < r or r < 0:
        return 0
    return fact[n] * finv[r] % MOD * finv[n - r] % MOD


x, y = map(int, input().split())
if (2 * x - y) % 3 != 0 or (2 * y - x) % 3 != 0:
    print(0)
    exit()

a, b = (2 * x - y) // 3, (2 * y - x) // 3
print(modcomb(a + b, a))

Submission status: Accepted

Solution code:
X,Y=map(int, input().split())
a=0
MAX_NUM = 7*10**5
pr = 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]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % pr
    inv[i] = pr - inv[pr%i] * (pr // i) % pr
    finv[i] = finv[i-1] * inv[i] % pr
def c(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % pr) % pr
if (X+Y)%3==0:
    a=c((X+Y)//3,(X-Y+(X+Y)//3)//2)
print(a)

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 )

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

    X_,Y_ = (2*X-Y)//3, (2*Y-X)//3
    if (X+Y) % 3 != 0 or X_ < 0 or Y_ < 0: 
        print(0)
        return
    
    print(cmb(X_+Y_,Y_, mod))
    
solve()

Submission status: Accepted

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

if (x+y)%3!=0:
    print(0)
    exit()
    
a=(2*y-x)//3
b=(2*x-y)//3

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

mod=10**9+7

F=[1]
for i in range(1,a+b+1):
    tmp=F[-1]*i
    F.append(tmp%mod)

Ia=pow(F[a],mod-2,mod)
Ib=pow(F[b],mod-2,mod)

ans=F[a+b]*Ia*Ib%mod
print(ans)