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

if (X+Y)%3:
    ans=0
else:
    N=(X+Y)//3
    if N<=X<=2*N and N<=Y<=2*N:
        ans=cmb(N,X-N,p)
    else:
        ans=0

print(ans)

Submission status: Accepted

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

if (x + y) % 3 or (x > y * 2) or (x * 2 < y):
  print(0)
else:
  MOD = 10 ** 9 + 7
  MAX = 10 ** 6

  fac = [1] * MAX
  inv = [1] * MAX
  finv = [1] * MAX
  for i in range(2, MAX):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = (- inv[MOD % i] * (MOD // i)) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD

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

  a = (x + y) // 3
  b = (a - abs(x - y)) // 2
  print(com(a, b))

Submission status: Accepted

Solution code:
mod=10**9+7
N,K=list(map(int,input().split()))
if (N+K)%3==0 and N*2>=K and K*2>=N:
   A=max(N,K)-min(N,K)
   low=(min(N,K)-A)//3
   all_pt=low*2+A
else:
   print(0)
   exit()
up,down=1,1
for i in range(low):
   up=up*(all_pt-i)%mod
   down=down*(i+1)%mod
base=pow(down,mod-2,mod)
print(up*base%mod)

Submission status: Accepted

Solution code:
X, Y = [int(_) for _ in input().split()]

p = 10 ** 9 + 7
N = 670000

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((p - inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
    
def combination(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

def solve(X, Y):
    if (X + Y) % 3 != 0:
        return 0
    Z = (X + Y) // 3
    x = (Z + X - Y) // 2
    return combination(Z, x, p)

print(solve(X, Y))

Submission status: Accepted

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


def cmb(n, r, mod):
    numerator = reduce(lambda x, y: x * y % mod, [n - r + k + 1 for k in range(r)])
    denominator = reduce(lambda x, y: x * y % mod, [k + 1 for k in range(r)])
    return numerator * pow(denominator, mod - 2, mod) % mod


x, y = map(int, input().split())
mod = 1000000007
cnt = (x + y) // 3
if (x + y) % 3 != 0:
    print(0)
    exit()
m = min(x, y)
num_2 = m - cnt
num_1 = cnt - num_2
ans = cmb(cnt, num_1, mod)
print(ans)

Submission status: Accepted

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


def cmb(n, r, mod):
    numerator = reduce(lambda x, y: x * y % mod, [n - r + k + 1 for k in range(r)])
    denominator = reduce(lambda x, y: x * y % mod, [k + 1 for k in range(r)])
    return numerator * pow(denominator, mod - 2, mod) % mod


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def my_factorial(n, mod):
    if n == 1:
        return 1
    return (n * my_factorial(n-1, mod)) % mod


@lru_cache(maxsize=None)
def for_factorial(n):
    val = 1
    for i in range(2, n + 1):
        val = (val * i)
    return val



x, y = map(int, input().split())
mod = 1000000007
cnt = (x + y) // 3
if (x + y) % 3 != 0:
    print(0)
    exit()
m = min(x, y)
num_2 = m - cnt
num_1 = cnt - num_2
ans = cmb(cnt, num_1, mod)
print(ans)

Submission status: Accepted

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

def conbi(n,r,mod):
    ue=1
    for i in range(n-r+1,n+1):
        ue*=i
        ue%=mod
 
    sita=1
 
    for i in range(1,r+1):
        sita*=i
        sita%=mod
 
    sita=pow(sita,mod-2,mod)
 
    return (ue*sita)%mod

for a in range(x+1):
    b=(x-a)/2
    if b-int(b)==0:
        b=int(b)
        if y==2*a+b:
            ans+=conbi(a+b,a,10**9+7)

print(ans)

Submission status: Accepted

Solution code:
MAX = 10**6+100
MOD = 10**9+7
fact = [0]*MAX #fact[i]: i!
inv = [0]*MAX #inv[i]: iの逆元
finv = [0]*MAX #finv[i]: i!の逆元
fact[0] = 1
fact[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
    
for i in range(2, MAX):
    fact[i] = fact[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD

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

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

for i in range(X+1):
    if (X-i)%2==0 and (X-i)//2==Y-2*i:
        ans += C(Y-i, i)

print(ans)

Submission status: Accepted

Solution code:
X, Y = map(int, input().split())
mod = 10 ** 9 + 7
m = mod - 2
bin_m = []
while m:
  bin_m.append(m % 2)
  m >>= 1
p = 2 * X - Y
q = -X + 2 * Y
if p >= 0 and q >= 0 and p % 3 == 0:
  a = p // 3
  b = q // 3
  n = a + b
  ANS = 1
  for i in range(1, a+1):
    ANS = (ANS * (n+1-i)) % mod
    inv = 1
    for j in reversed(bin_m):
      inv = (inv * inv) % mod
      if j == 1:
        inv = (inv * i) % mod
    ANS = (ANS * inv) % mod
  print(ANS)
else:
  print(0)

Submission status: Accepted

Solution code:
class Factorial:
    def __init__(self, max_fact, mod):
        #mod should be prime number
        #using homogeneous_product(n,r), max_fact ≧ max(n+r-1)
        f = [1] * (max_fact + 1)
        for idx in range(2, max_fact + 1):
            f[idx] = f[idx - 1] * idx
            f[idx] %= mod
        if mod > max_fact:
            fi = [pow(f[-1], mod - 2, mod)]
            for idx in range(max_fact, 0, -1):
                fi += [fi[-1] * idx % mod]
            fi = fi[::-1]
        else:
            fi = [pow(n, mod - 2, mod) for n in f]
        self.mod = mod
        self.f = f
        self.fi = fi

    def factorial(self, n):
        return self.f[n]

    def factorial_inverse(self, n):
        return self.fi[n]

    def combination(self, n, r):
        f = self.f
        fi = self.fi
        return f[n] * fi[r] * fi[n - r] % self.mod

    def permutation(self, n, r):
        return self.f[n] * self.fi[n - r] % self.mod

    def homogeneous_product(self, n, r):
        f = self.f
        fi = self.fi
        return f[n + r - 1] * fi[r] * fi[n - 1] % self.mod


max_fact = 10**6
mod = 10**9 + 7
fact_instance = Factorial(max_fact, mod)
comb = fact_instance.combination
perm = fact_instance.permutation
combrep = fact_instance.homogeneous_product

X, Y = [int(_) for _ in input().split()]
i = X - (X + Y) // 3
j = Y - (X + Y) // 3
if (X + Y) % 3 or i < 0 or j < 0:
    ans = 0
else:
    ans = comb(i + j, i)
print(ans)

Submission status: Accepted

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

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

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

# ans = math.factorial(a+b)/math.factorial(a)
# ans=1
# for i in range(a+1,a+b+1):
#     ans*=i%(10**9+7)

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)

ans = cmb(a+b,a,p)

print(ans)

Submission status: Accepted

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

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

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

if a < 0 or b < 0:
    # (x,y) = (1,5)とかは無理
    print(0)
    exit()
    
MOD = 10**9+7
def fact(x):
    f = 1
    for i in range(2, x+1):
        f *= i
        f %= MOD
    return f

def fact_inv(x):
    return pow(fact(x), MOD-2, MOD)

ans = fact(a+b) * fact_inv(a) * fact_inv(b) % MOD

print(ans)

Submission status: Accepted

Solution code:
# 逆元を利用した組み合わせの計算
#############################################################


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


# 問題に応じて変える、素数の時しか動作しない
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())

# X+Yが3の倍数のマスしか通りえない
if (X + Y) % 3 == 0:
    # (1,2)移動をn回、(2,1)移動をm回したとする
    # n+2m = X, 2n+m = Y
    # n,mについて解く
    n = (2 * Y - X) // 3
    m = (2 * X - Y) // 3

    if n >= 0 and m >= 0:
        print(cmb(n + m, n, mod))
    else:
        print(0)

# X+Yが3の倍数でない場合
else:
    print(0)

Submission status: Accepted

Solution code:
p = 10 ** 9 + 7
N = 10**6  #Nの取りうる最大
R = 10**6  #Rの取りうる最大

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)
  
for i in range(2, R + 1):
  inv.append((-inv[p % i] * (p // i)) % p)
  factinv.append((factinv[-1] * inv[-1]) % p)

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


a,b=map(int,input().split())
if (a+b)%3==0:
  T=int((a+b)/3)
  K=a-T
  print(comb(T,K,p))
else:
  print(0)

Submission status: Accepted

Solution code:
#(i,j)→（i+1,j+2）をx回、(i,j)→（i+2,j+1）がy回あるとすると
#x=(2Y-X)//3,y=(2X-Y)//3、となる
#これが整数or非負なら(x+y)Cxを求めればいい

X,Y=list(map(int,input().split()))
import sys
if (2*Y-X)%3!=0 or (2*X-Y)%3!=0:
  print(0)
  sys.exit()
if (2*Y-X)<0 or (2*X-Y)<0:
  print(0)
  sys.exit()

  
#それ以外なら存在する
x=(2*Y-X)//3
y=(2*X-Y)//3
#(x+y)Cxを求める

fac=[0 for i in range(x+y+1)]
inv=[0 for i in range(x+y+1)]
finv=[0 for i in range(x+y+1)]
#初期条件
fac[0]=fac[1]=1
inv[1]=1
finv[0]=finv[1]=1
p=1000000007
for i in range(2,x+y+1):
  fac[i]=(fac[i-1]*i)%p
  #p=(p//a)*a+(p%a) pの世界で　a^(-1)=-(p//a)*inv[p%a]
  inv[i]=(-(p//i)*inv[p%i])%p
  finv[i]=(finv[i-1]*inv[i])%p

print((fac[x+y]*finv[x]%p)*finv[y]%p)

Submission status: Accepted

Solution code:
mod=10**9+7

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

x-=z
y-=z

n=x+y
r=x

if x==0 or y==0:
  print(1)
  exit()
  

lst=[0]+[1]
for i in range(2,n+10):
  lst.append((lst[-1]*i)%mod)


xxx=lst[n]
xxx*=pow(lst[n-r],10**9+5,mod)
xxx%=mod
xxx*=pow(lst[r],10**9+5,mod)
xxx%=mod

print(xxx)

Submission status: Accepted

Solution code:
fact = [None]*1000001
inv = [0,1]
finv = [1,1]

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

if total%3 == 0 and max(x,y) <= min(x,y)*2:
    fact[1] = 1
    for i in range(2,1000001):
        fact[i] = fact[i-1]*i%MOD
        inv.append((-inv[MOD%i] * (MOD//i)) % MOD)
        finv.append(finv[-1] * inv[-1] % MOD)
    step = int(total/3)
    sa = abs(x-y)
    a = int((step-sa)/2)
    b = int((step+sa)/2)
    ans = fact[step] * finv[a] * finv[b] % MOD
print(ans)

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
mod = 10**9+7
def comb(N,x):
    numerator = 1
    for i in range(N-x+1,N+1):
        numerator = numerator * i % mod
    denominator = 1
    for j in range(1,x+1):
        denominator = denominator * j % mod
    d = pow(denominator,mod-2,mod)
    return numerator * d % mod

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

    if a >= 0 and b >= 0:
        print(comb(a+b,a))
        exit()
print(0)

Submission status: Accepted

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

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

z=x+y
if z%3!=0 or x-(z//3)<0 or y-(z//3)<0:
    print(0)
else:
    z//=3
    # print(z)
    # print(min(x,y)-z)
    print(nCr(z,min(x,y)-z))

Submission status: Accepted

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

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


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


n=X+Y
k=max(X,Y)
g1=[1,n]
g2=[1,1]
inverse=[0,1]

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

print(cmb(n,k,mod))

Submission status: Accepted

Solution code:
def inv(a,p):
    if a==1:
        return 1
    elif a==0:
        return 0
    return p-(inv(p%a,p)*(p//a))%p
x,y=map(int,input().split())
if (x+y)%3!=0:
    print("0")
    exit()
if x==0 and y>0:
    print("0")
    exit()
if y/x>2 or y/x<0.5:
    print("0")
    exit()
n=(x+y)//3
r=(2*x-y)//3
p=10**9+7
def fact(n,p):
    a=[[] for _ in range(n+1)]
    a[0]=1
    for i in range(n):
        a[i+1]=(a[i]*(i+1))%p
    return a
f=fact(n,p)
c=f[-1]
d=f[r]
e=f[n-r]
dd=inv(d,p)
ee=inv(e,p)
ans=(c*dd*ee)%p
print(ans)

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
if (x+y)%3!=0:print(0);exit()
mod = 10**9+7
n = (x+y)//3
m = min(x-n,y-n)
frac = [1]*(n+1)
finv = [1]*(n+1)
for i in range(n):
    frac[i+1] = (i+1)*frac[i]%mod
finv[-1] = pow(frac[-1],mod-2,mod)
for i in range(1,n+1):
    finv[n-i] = finv[n-i+1]*(n-i+1)%mod
def nCr(n,r):
    if n<0 or r<0 or n<r: return 0
    r = min(r,n-r)
    return frac[n]*finv[n-r]*finv[r]%mod
print(nCr(n,m)%mod)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

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

N = (X + Y) // 3
M = X - N

if X < N or Y < N:
    print(0)
    sys.exit()

# C,Pを求める前処理
m = 10**6
mod = 10**9 + 7


fact = [0]*(m+5)
fact_inv = [0]*(m+5)
inv = [0]*(m+5)

fact[0] = fact[1] = 1
fact_inv[0] = fact_inv[1] = 1
inv[1] = 1

for i in range(2,m+5):
    fact[i] = fact[i-1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod

# nCkをmod（素数）で割った余りを求める．ただしn<10**7
# 前処理はm=n+5まで
def cmb(n,k,mod):
    return fact[n] * (fact_inv[k] * fact_inv[n-k] % mod) % mod

print(cmb(N,M,mod))

Submission status: Accepted

Solution code:
X,Y=list(map(int, input().split()))
a=(2*X-Y)//3
b=(2*Y-X)//3
if not (2*a+b==X and a+2*b==Y and a>=0 and b>=0):
    print(0)
    exit()

C=10**9+7
A=1
B=1
D=1
for i in range(a):
    A*=i+1
    A=A%C
for j in range(b):
    B*=j+1
    B=B%C
for k in range(a+b):
    D*=k+1
    D=D%C

D*=pow(A,C-2,C)
D*=pow(B,C-2,C)
print(D%C)

Submission status: Accepted

Solution code:
class Modulo():
    def __init__(self,a,n):
        self.a=a%n
        self.n=n

    def __str__(self):
        return "{} (mod {})".format(self.a,self.n)

    #+,-
    def __pos__(self):
        return self

    def __neg__(self):
        return  Modulo(-self.a,self.n)

    #等号,不等号
    def __eq__(self,other):
        if isinstance(other,Modulo):
            return (self.a==other.a) and (self.n==other.n)
        elif isinstance(other,int):
            return (self-other).a==0

    def __neq__(self,other):
        return not(self==other)

    #加法
    def __add__(self,other):
        if isinstance(other,Modulo):
            if self.n!=other.n:
                raise Modulo_Error("異なる法同士の演算です.")
            return Modulo(self.a+other.a,self.n)
        elif isinstance(other,int):
            return Modulo(self.a+other,self.n)

    def __radd__(self,other):
        if isinstance(other,int):
            return Modulo(self.a+other,self.n)

    #減法
    def __sub__(self,other):
        return self+(-other)

    def __rsub__(self,other):
        if isinstance(other,int):
            return -self+other

    #乗法
    def __mul__(self,other):
        if isinstance(other,Modulo):
            if self.n!=other.n:
                raise Modulo_Error("異なる法同士の演算です.")
            return Modulo(self.a*other.a,self.n)
        elif isinstance(other,int):
            return Modulo(self.a*other,self.n)

    def __rmul__(self,other):
        if isinstance(other,int):
            return Modulo(self.a*other,self.n)

    #Modulo逆数
    def Modulo_Inverse(self):
        x0, y0, x1, y1 = 1, 0, 0, 1
        a,b=self.a,self.n
        while b != 0:
            q, a, b = a // b, b, a % b
            x0, x1 = x1, x0 - q * x1
            y0, y1 = y1, y0 - q * y1

        if a!=1:
            raise Modulo_Error("{}の逆数が存在しません".format(self))
        else:
            return Modulo(x0,self.n)

    #除法
    def __truediv__(self,other):
        return self*(other.Modulo_Inverse())

    def __rtruediv__(self,other):
        return other*(self.Modulo_Inverse())

    #累乗
    def __pow__(self,m):
        u=abs(m)

        r=Modulo(1,self.n)

        while u>0:
            if u%2==1:
                r*=self
            self*=self
            u=u>>1

        if m>=0:
            return r
        else:
            return r.Modulo_Inverse()

    #根号
    def sqrt(self):
        if self==0:
            return self
        elif self.n==2:
            return self
        elif self.n%4==3:
            return self**((self.n+1)//4)
        else:
            p=self.n
            u=2
            s=1
            while (p-1)%(2*u)==0:
                u*=2
                s+=1

            z=Modulo(2,p)
            while z**((p-1)//2)!=-1:
                z+=1

            q=(p-1)//u
            m=s
            c=z**q
            t=self**q
            r=self**((q+1)//2)

            while m>1:
                k=1
                d=t*t

                while d!=1:
                    k+=1
                    d*=d
                    print(m,k)
                b=Modulo(2,p)**(2**(m-k-1))
                c,t,r,m=b*b,t*b*b,r*b,k
            return r

#階乗の剰余のリスト
def Factorial_Modulo_List(N,M,Inverse=False):
    X=[0]*(N+1)
    X[0]=Modulo(1,M)

    for i in range(1,N+1):
        X[i]=X[i-1]*i

    if Inverse:
        Y=[0]*(N+1)
        Y[-1]=1/X[-1]

        for j in range(N-1,-1,-1):
            Y[j]=Y[j+1]*(j+1)
        return X,Y
    else:
        return X
#================================================
import sys
X,Y=map(int,input().split())
M=10**9+7

J,K=-X+2*Y,2*X-Y

if not(J>=0 and J%3==0 and K>=0 and K%3==0):
    print(0)
    sys.exit()

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

F,G=Factorial_Modulo_List(A+B,M,True)
print((F[A+B]*G[A]*G[B]).a)

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
a=max(x,y)
b=min(x,y)
s=a-b
A=a-s-s
if A>=0 and A%3==0:
    t=A//3
    p=t+s
    q=t
    ans=1
    for i in range(q):
        ans=ans*(p+q-i)*pow((i+1),10**9+5,10**9+7)
        ans=ans%(10**9+7)
    print(ans)
else:
    print(0)

Submission status: Accepted

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

total = (X+Y)/3
k = (2*X-Y)//3

if (total == int(total)) and (k>=0):
    total = (X+Y)//3

    mod = 10 ** 9 + 7

    modinv_table = [-1] * (k + 1)
    for i in range(1, k + 1):
        modinv_table[i] = pow(i, -1, mod)


    def binomial_coefficients(n, k):
        ans = 1
        for i in range(k):
            ans *= n - i
            ans *= modinv_table[i + 1]
            ans %= mod
        return ans

    print(binomial_coefficients(total,k))
else:
    print(0)

Submission status: Accepted

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

if (2*x-y)%3==0:
  a=(2*x-y)//3
else:
  flflag=False
if (2*y-x)%3==0:
  b=(2*y-x)//3
else:
  flflag=False

def kaijou(n):
  ans = 1
  for i in range(1,n+1):
    ans*=i%mod
    ans%=mod  
  return ans
if flflag:
  N=a+b
  R=min(a,b)
ans=0
if flflag==True and a>=0 and b>=0:
  ans=kaijou(N)
  ans1= (kaijou(N-R)*kaijou(R))%mod
  print((ans*pow(ans1,mod-2,mod))%mod)
else:
  print(0)

Submission status: Accepted

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

import sys
if (2*Y-X)%3!=0 or (2*X-Y)%3!=0:
  print(0)
  sys.exit()
if (2*Y-X)<0 or (2*X-Y)<0:
  print(0)
  sys.exit()
x=(2*Y-X)//3
y=(2*X-Y)//3
#(x+y)Cxを求める
fac=[0 for i in range(x+y+1)]
inv=[0 for i in range(x+y+1)]
finv=[0 for i in range(x+y+1)]
#初期条件
p=1000000007
fac[0]=fac[1]=1
inv[1]=1
finv[0]=finv[1]=1
#テーブルの作成
for i in range(2,x+y+1):
  fac[i]=fac[i-1]*i%p
  #p=(p//a)*a+(p%a) a^(-1)=-(p//a)*(p%a)^(-1)
  inv[i]=(-(p//i)*inv[p%i])%p
  finv[i]=finv[i-1]*inv[i]%p
#求める

print((fac[x+y]*finv[x]%p)*finv[y]%p)

Submission status: Accepted

Solution code:
mod = 10**9 + 7
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()

m = min(a, b)

ifact = 1
for i in range(2, m+1):
    ifact = (ifact * i) % mod
ifact = pow(ifact, mod-2, mod)
fact = 1
for i in range(a+b, a+b-m, -1):
    fact = (fact * i) % mod

print(fact*ifact % mod)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
MAX = 10**6
X, Y = map(int, input().split())
m, n = 2*Y-X, 2*X-Y
if (X+Y) % 3 != 0 or m%3!=0 or n%3!=0 or m<0 or n<0:
    print(0)
    exit()

m //= 3
n //= 3

fac, inv = [0]*MAX, [0]*MAX
fac[0] = 1
for i in range(1, MAX):
    fac[i] = fac[i-1] * i % MOD
inv[-1] = pow(fac[-1], MOD-2, MOD)
for i in range(MAX-2, 0, -1):
    inv[i] = inv[i+1] * (i+1) % MOD

def com(n, k):
    if n<k:return 0
    if n<0 or k<0:return 0
    if n==k or k==0:return 1
    return int(fac[n] * (inv[k]*inv[n-k]%MOD) % MOD)

print(com(n=m+n,k=n))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from functools import reduce

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

mod = 10**9 + 7


def cmb(n, r, m):
    def mul(a, b):
        return a * b % m

    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 * pow(under, m - 2, m))%m


r = abs(x - y)
l = (min(x, y) - r) // 3
r += l
if (x+y)%3 < 1 and l >= 0:
    print(cmb(r + l, l, mod))
else:
    print(0)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from functools import reduce

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

mod = 10**9 + 7


def cmb(n, r, m):
    def mul(a, b):
        return a * b % m

    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 * pow(under, m - 2, m))%m


r = abs(x - y)
l = (min(x, y) - r) // 3
r += l
if l*2+r*1 in (x,y) and l >= 0:
    print(cmb(r + l, l, mod))
else:
    print(0)

Submission status: Accepted

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


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

    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

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

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

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


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    X, Y = MI()

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

    ttl = int((X+Y)/3)
    a = X - ttl

    if (ttl < a or a < 0):
        print(0)
        return

    comb = Combination(ttl)

    tmp = comb(ttl, a)
    print(tmp)


main()

Submission status: Accepted

Solution code:
def factorial(n, mod):
    fac = [0] * (n + 1)
    inv = [0] * (n + 1)
    fac[0], inv[0] = 1, 1
    for i in range(1, n + 1):
        fac[i] = fac[i-1] * i % mod
        inv[i] = inverse(fac[i], mod)
    return fac, inv

def inverse(a, mod):
    a %= mod # 除数が正なら正になる
    p = mod
    x, y = 0, 1
    while a > 0:
        n = p // a
        p, a = a, p % a, 
        x, y = y, x - n * y
    return x % mod # 除数が正なら正になる

mod = 10 ** 9 + 7
x, y = map(int, input().split())
if (x + y) % 3 != 0:
    print(0)
    quit()
n = (x + y) // 3
if x < n or y < n:
    print(0)
    quit()

m = min(x, y) - n
fac, inv = factorial(n, mod)
print(fac[n] * inv[n-m] * inv[m] % mod) # nCm

Submission status: Accepted

Solution code:
MOD = 10**9+7
MAX = 1000010
finv = [0] * MAX
inv = [0] * MAX
def COMinit():
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        inv[i] = MOD - inv[MOD%i] * (MOD//i) % MOD
        finv[i] = finv[i-1] * inv[i] % MOD
def COM(n, k):
    res = 1
    for i in range(k):
        res = res * (n-i) % MOD
    return res * finv[k] % MOD

x, y = map(int, input().split())
if (x+y)%3 != 0:
    ans = 0
else:
    s, t = (-x+2*y)//3, (2*x-y)//3
    if s < 0 or t < 0:
        ans = 0
    else:
        COMinit()
        ans = COM((s+t), s)

print(ans)

Submission status: Accepted

Solution code:
MAX = 1000010
finv = [0] * MAX
inv = [0] * MAX
def COMinit():
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        inv[i] = MOD - inv[MOD%i] * (MOD//i) % MOD
        finv[i] = finv[i-1] * inv[i] % MOD

def COM(n, k):
    res = 1
    for i in range(k):
        res = res * (n-i) % MOD
    return res * finv[k] % MOD

MOD = 10**9+7
x, y = map(int, input().split())
s, t = (-x+2*y)/3, (2*x-y)/3

if s < 0 or t < 0:
    ans = 0
elif not (s.is_integer() and t.is_integer()):
    ans = 0
else:
    s, t = int(s), int(t)
    COMinit()
    ans = COM((s+t), s)

print(ans)

Submission status: Accepted

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

@lru_cache(maxsize=None)
def inv(n):
    return pow(n,-1,MOD)

if summ%3 == 0 and summ//3 <= x and summ//3 <= y:
    mn = min(x,y)
    n = mn - summ//3
    a = summ//3
    b = 1
    ans = 1
    for i in range(n):
        ans *= a
        ans *= inv(b)
        ans %= MOD
        a -= 1
        b += 1
    print(ans)
else:
    print(0)

Submission status: Accepted

Solution code:
def ex_euclid(a, b):
  x0, x1 = 1, 0
  y0, y1 = 0, 1
  z0, z1 = a, b
  
  while z1 != 0:
    q = z0 // z1
    z0, z1 = z1, z0 % z1
    x0, x1 = x1, x0 - q * x1
    y0, y1 = y1, y0 - q * y1
  
  return z0, x0, y0

def mod_inv(a, n):
  g, x, _ = ex_euclid(a, n)
  if g != 1:
    print("modular inverse does not exist")
  else:
    return x % n

def mod_factorial(x, modulo):
  ans = 1
  for i in range(1, x+1):
    ans *= i
    ans %= modulo
  return ans

X, Y = map(int, input().split())
M = 10 ** 9 + 7
a, b = (2*X-Y)/3, (2*Y-X)/3
if a < 0 or b < 0:
  print(0)
elif a == 0 and b == 0:
  print(0)
elif a%1 != 0 or b%1!= 0:
  print(0)
else:
  a, b = int(a), int(b)
  answer = 1
  answer *= mod_factorial(a+b, M)
  answer *= mod_inv(mod_factorial(a, M), M)
  answer %= M
  answer *= mod_inv(mod_factorial(b, M), M)
  answer %= M
  print(answer)

Submission status: Accepted

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

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

# ①nCrの各項のmod(10^9+7)を事前計算
p = 10 ** 9 + 7
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, t + 1):
  fact.append((fact[-1] * i) % p)
  inv.append((-inv[p % i] * (p // i)) % p)
  factinv.append((factinv[-1] * inv[-1]) % p)

# ②事前計算した項を掛け合わせ
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

print(cmb(t, X-t, p))

Submission status: Accepted

Solution code:
x, y = map(int, input().split())
diff = abs(x - y)
ref = (min(x, y) - diff)//3
total = ref*2 + diff
mod = 10**9 + 7
ans = 1
ie = 1

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


for i in range(min(ref, total - ref)):
    ans = ans*(total - i)%mod
    ie = ie*(i + 1)%mod

ie = pow(ie, mod - 2, mod)
ans = ans*ie%mod
print(ans)

Submission status: Accepted

Solution code:
x, y = map(int, input().split())
diff = abs(x - y)
ref = (min(x, y) - diff)//3
total = ref*2 + diff
mod = 10**9 + 7
ans = 1

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


for i in range(min(ref, total - ref)):
    ans = ans*(total - i)%mod
    ie = pow((i + 1), (mod - 2), mod)
    ans = ans*ie%mod

print(ans)

Submission status: Accepted

Solution code:

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

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

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

elif n<0 or m<0:
    print(0)

else:
    MAXN = (10**6)+10
    MOD = 10**9 + 7
    f = [1]
    for i in range(MAXN):
        f.append(f[-1] * (i+1) % MOD)
    def nCr(n, r, mod=MOD):
        return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod


    print(nCr(n+m,n,10**9 + 7))

Submission status: Accepted

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

MAXN = 2*(10**6)+10
p = 10**9+7
f = [1]
for i in range(MAXN):
    f.append(f[-1] * (i+1) % p)
def nCr(n, r, mod=p):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod


Z = (X+Y)//3
if Z*3!=X+Y:
    print(0)
else:
    P,Q = X-Z, Y-Z
    if P<0 or Q<0:
        print(0)
    else:
        print(nCr(Z,P))

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
#xをベースに
r = 0 #→2 ↑1
u = x #→1 ↑2

while y != r + u*2:
    u -= 2
    r += 1
    if u < 0: #到達する方法がない
        print(0)
        exit()

#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

mod = 10**9 + 7
N = u+r+1 #必要な数
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

print(cmb(u+r,r,mod))