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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

X, Y = map(int,input().split())
a=(-X+2*Y)/3
b=(2*X-Y)/3
if a.is_integer()==False or b.is_integer()==False:
    print(0)
else:
    print(cmb(int(a+b),int(b))%(pow(10,9)+7))

Submission status: Runtime Error

Solution code:
from functools import reduce

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

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

r = min(a,b)

if r == 0:
  print("1")
else:
  numerator = reduce(lambda x, y: x * y % mod, [a + b - r + k + 1 for k in range(r)])
  denominator = reduce(lambda x, y: x * y % mod, [k + 1 for k in range(r)])
  print(numerator * pow(denominator, mod - 2, mod) % mod)

Submission status: Runtime Error

Solution code:
from functools import reduce

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

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

r = min(a,b)

numerator = reduce(lambda x, y: x * y % mod, [a + b - r + k + 1 for k in range(r)])
denominator = reduce(lambda x, y: x * y % mod, [k + 1 for k in range(r)])
print(numerator * pow(denominator, mod - 2, mod) % mod)

Submission status: Runtime Error

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**4
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=(-X+2*Y)/3
b=(2*X-Y)/3
if a.is_integer()==False or b.is_integer()==False:
    print(0)
else:
    print(cmb(int(a+b),int(b),mod))

Submission status: Runtime Error

Solution code:
import math
from scipy.special import comb
X, Y = map(int,input().split())
a=(-X+2*Y)/3
b=(2*X-Y)/3
if a.is_integer()==False or b.is_integer()==False:
    print(0)
else:
    print(comb((int(a+b),int(a))))

Submission status: Runtime Error

Solution code:
import math
X, Y = map(int,input().split())
a=(-X+2*Y)/3
b=(2*X-Y)/3
if a.is_integer()==False or b.is_integer()==False:
    print(0)
else:
    print(math.factorial(int(a+b)) // (math.factorial(int(a)) * math.factorial(int(b))))

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7


x,y=map(int,input().split())
n=(2*y-x)//3
m=(2*x-y)//3
k=n
  
if (x+y)%3!=0:
  print(0)
else:
  modinv_table = [-1] * (k+1)
  modinv_table[1] = 1
  for i in range(2, k+1):
    modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod

  def c(n, k):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i + 1]
        ans %= mod
    return ans
  
  if n<0 and m<0:
    print(0)
  else:
    print(c(n+m,n)%(10**9+7))

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7


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

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

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

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

Submission status: Runtime Error

Solution code:
class Combination:
    def __init__(self, mod, max_n):
        self.MOD = mod
        self.MAX_N = max_n

        self.f = self.factorial(self.MAX_N)
        self.f_inv = [self.inv(x) for x in self.f]

    def inv(self,x):
        return pow(x, self.MOD-2, self.MOD)
    
    def factorial(self, n):
        res = [1]
        for i in range(1,n+1):
            res.append(res[-1] * i % self.MOD)
        return res
    
    def comb(self, n, r):
        return (self.f[n] * self.f_inv[r] % self.MOD) * self.f_inv[n-r] % self.MOD


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

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

k, l = (2*Y-X)//3, (2*X-Y)//3
CB = Combination(10**9+7, k+l)
print(CB.comb(k+l,k))

Submission status: Runtime Error

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

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



if a!=(2*x-y)/3 or b!=(2*y-x)/3:
    print(0)
else:
    max=a+b+10
    fac=[0]*max
    finv=[0]*max
    inv=[0]*max

    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,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

    ans=fac[a+b]*(finv[a]*finv[b]%mod)%mod
    print(ans)

Submission status: Runtime Error

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

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



if a!=(2*x-y)/3 or b!=(2*y-x)/3:
    print(0)
else:
    max=a+b+1
    fac=[0]*max
    finv=[0]*max
    inv=[0]*max

    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,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

    ans=fac[a+b]*(finv[a]*finv[b]%mod)%mod
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
r=sys.stdin.readline
X,Y=map(int,r().split())
#a=X-2b, b=Y-2a
sys.setrecursionlimit(10**6)
if (X+Y)%3!=0:
    print(0)
    exit(0)   
a=(2*Y-X)//3
b=(2*X-Y)//3
MOD=10**9+7
N=10**6
#permutation with repetition
#ex) ab, ba --> a+bCa
def pow(a,b):
    ans=1
    while b:
        if b&1:
            ans=(ans*a)%MOD
        a=(a**2)%MOD
        b=b//2
    return ans 
N=a+b
K=a
fac=[1 for _ in range(N+1)]
for i in range(2,N+1):
    fac[i]=(fac[i-1]*i)%MOD
A=fac[N]
B=(fac[N-K]*fac[K])%MOD
print((A%MOD)*pow(B,MOD-2)%MOD)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
r=sys.stdin.readline
X,Y=map(int,r().split())
#a=X-2b, b=Y-2a
sys.setrecursionlimit(10**6)
if (2*Y-X)%3!=0 or (2*X-Y)%3!=0:
    print(0)
    exit(0)   
a=(2*Y-X)//3
b=(2*X-Y)//3
MOD=10**9+7
N=10**6
#permutation with repetition
#ex) ab, ba --> a+bCa
def pow(a,b):
    ans=1
    while b:
        if b&1:
            ans=(ans*a)%MOD
        a=(a**2)%MOD
        b=b//2
    return ans 
N=a+b
K=a
fac=[1 for _ in range(N+1)]
for i in range(2,N+1):
    fac[i]=(fac[i-1]*i)%MOD
A=fac[N]
B=(fac[N-K]*fac[K])%MOD
print((A%MOD)*pow(B,MOD-2)%MOD)

Submission status: Runtime Error

Solution code:
X,Y=sorted(list(map(int,input().split())))
#移動方法を(i+1,j),(i,j+1)となるようにどうにかする
if (X-abs(Y-X))%3!=0:
  print(0)
  exit(0)
n=(X-abs(Y-X))//3
X=n+abs(Y-X)
Y=n

  
mod=10**9+7
a=1
for i in range(1,X+Y+1):
  a*=i
  a%=mod
b=1
for i in range(1,X+1):
  b*=i
  b%=mod
c=1
for i in range(1,Y+1):
  c*=i
  c%=mod
print(a*pow(b,-1,mod)*pow(c,-1,mod)%mod)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!

x,y=map(int,input().split())
mod=10**9+7
dp = [[0]*(x+1) for _ in range(y+1)]
dp[0][0]=1
for i in range(y+1):
    for j in range(x+1):
        if i-1>=0 and j-2>=0:
            dp[i][j]+=dp[i-1][j-2]
        if i-2>=0 and j-1>=0:
            dp[i][j]+=dp[i-2][j-1]
print(dp[y][x]%mod)

Submission status: Runtime Error

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    X,Y=MI()
    N3=X+Y
    
    if N3%3!=0:
        print(0)
        exit()
        
    N=N3//3
    a=0
    b=0
    for i in range(N3):
        if 2*i + (N-i) == X:
            a=i
            b=N-i
            break

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

    for i in range(2, N + 1):
        fact.append((fact[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv.append((factinv[-1] * inv[-1]) % mod)
        
    ans=fact[N]*factinv[a]*factinv[b]
    print(ans%mod)
    

main()

Submission status: Runtime Error

Solution code:
import math
X, Y = map(int, input().split())
if X > Y:
  X, Y = Y, X

if ((2*X-Y) % 3 != 0) or (2*X-3 < 0):
  print(0)
  exit()
A = (2*X-Y)//3
B = Y-X+A
N = A+B
nu = 1
de = 1

for i in range(B+1, N+1):
  nu = (nu * i) % (10 ** 9 + 7)
for i in range(1, A+1):
  de = (de * i) % (10 ** 9 + 7)
print((nu * pow(de, -1, 10 ** 9 + 7) ) % (10 ** 9 + 7))

Submission status: Runtime Error

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

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

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

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)
print(fact[n+m]*factinv[n]*factinv[m]%P)

Submission status: Runtime Error

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
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: Runtime Error

Solution code:
mod=10**9+7

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

x-=z
y-=z

n=x+y
r=x


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: Runtime Error

Solution code:
mod=10**9+7

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

x-=z
y-=z

n=x+y
r=x

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: Runtime Error

Solution code:
import numpy as np
from numba import jit

@jit
def main():
    X, Y = map(int, input().split())
    dp = np.zeros((Y+3, X+3), dtype=np.int)
    mod = 10**9 + 7
    dp[0][0] = 1
    dp[1][2] = 1
    dp[2][1] = 1

    for i in range(2, Y+1):
        end = min(X+1, i*2+1)
        for j in range(i-1, end):
            if i-2 > 0 and j-2 > 0:
                dp[i][j] = (dp[i-1][j-2] + dp[i-2][j-1]) % mod
    return dp[Y][X]

print(main())

Submission status: Runtime Error

Solution code:
x,y = map(int,input().split())
mod = 10**9+7
dp = [[0]*(x+1) for _ in range(y+1)]

dp[0][0] = 1
for i in range(y+1):
    for j in range(x+1):
        if i-2 >= 0 and j-1 >= 0:
            dp[i][j] += dp[i-2][j-1]
        if i-1 >= 0 and j-2 >= 0:
            dp[i][j] += dp[i-1][j-2]
    dp[i][j] %= mod
print(dp[y][x])

Submission status: Runtime Error

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 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
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: Runtime Error

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()
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)
if len(f)<=r:
    print("0")
    exit()
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: Runtime Error

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()
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)
if len(f)>=r:
    print("0")
    exit()
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: Runtime Error

Solution code:
def inv(a,p):
    if a==1:
        return 1
    elif a==0:
        return 0
    else:
        return p-(inv(p%a,p)*(p//a))%p
x,y=map(int,input().split())
if (x+y)%3!=0:
    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: Runtime Error

Solution code:
def inv(a,p):
    if a==1:
        return 1
    else:
        return p-(inv(p%a,p)*(p//a))%p
x,y=map(int,input().split())
if (x+y)%3!=0:
    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: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import math
def combination(n,r):
    return math.factorial(n)//(math.factorial(n-r) * math.factorial(r))
X,Y=[int(i) for i in input().split()]
count=0
if (X+Y)%3!=0:    
    print(0)
else:
    ans=combination((X+Y)//3,((X+Y)//3)/2)
    print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
import math
def combination(n,r):
    return math.factorial(n)//(math.factorial(n-r) * math.factorial(r))
X,Y=[int(i) for i in input().split()]
count=0
if (X+Y)%3==0:    
    for i in range((X+Y)//3):
        count+=1
    ans=combination(count,count/2)
    print(ans%(10**9+7))

else:
    print(0)

Submission status: Runtime Error

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

if not((-X+2*Y)%3==0 and (2*X-Y)%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: Runtime Error

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

N=a+b
R=min(a,b)
ans=0
if a>=0 and b>=0 and flflag==True:
  ans=kaijou(N)
  ans1= (kaijou(N-R)*kaijou(R))%mod
  print((ans*pow(ans1,mod-2,mod))%mod)
else:
  print(0)

Submission status: Runtime Error

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

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: Runtime Error

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

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(x+y)
print(x)
print(y)

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

Submission status: Runtime Error

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)%3<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(x+y)
print(x)
print(y)

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

Submission status: Runtime Error

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()
  
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: Runtime Error

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()
  
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[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: Runtime Error

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()
  
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[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-(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: Runtime Error

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()
  
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[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-(p//i)*inv[p%i])%p
  finv[i]=finv[i-1]*inv[i]%p
#求める
print(fac[x+y]*finv[x]*finv[y]%p)

Submission status: Runtime Error

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):
    print(cmb(r + l, r, mod))
else:
    print(0)

Submission status: Runtime Error

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):
        print(0)
        return

    comb = Combination(ttl)

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


main()

Submission status: Runtime Error

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)

    if (ttl == 1):
        print(1)
        return
    a = X - ttl

    comb = Combination(ttl)

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


main()

Submission status: Runtime Error

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

    comb = Combination(ttl)

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


main()

Submission status: Runtime Error

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
m = min(x, y) - n

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

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import math  # gcdもあるよ
from collections import deque
from collections import defaultdict
from copy import deepcopy
from itertools import accumulate #リストを与えると累積和を返す
def input(): return sys.stdin.readline().rstrip()
from functools import lru_cache #メモ化
from operator import mul
from functools import reduce
def cmb(n,r,mod):
    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
mod = 10**9 + 7

def main():
    x, y = list(map(int,input().split()))
    t = x + y
    if t % 3 != 0: 
        print('0')
        return 0 #いる？
    min_xy = t//3 * 2
    max_xy = t - min_xy
    if not min_xy <= x and x <= max_xy and min_xy <= y and y <= max_xy:
        print('0')
        return 0
    C_left = t // 3
    C_right = abs(x - min_xy)
    ans = cmb(C_left, C_right, mod)
    print(ans)
    return 0

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

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

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

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

#コンビネーションを何回も計算する問題で使える関数
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: Runtime Error

Solution code:
x,y=map(int,input().split())
a=-1
p=10**9+7
for i in range(x//2+1):
  if i+2*(x-2*i)==y:
    a=i
    break
if a==-1:
  print(0)
  exit()
elif a==0:
  print(1)
else:
  gyaku=[0,1]
  for i in range(2,a+1):
    gyaku.append(((p//i)*-gyaku[p%i])%p)
  com=[1]
  for i in range(1,a+1):
    com.append(com[-1]*gyaku[i]*(x-a+1-i)%p)
　　print(com[a])

Submission status: Runtime Error

Solution code:
x,y=map(int,input().split())
a=-1
p=10**9+7
for i in range(x//2+1):
  if i+2*(x-2*i)==y:
    a=i
    break
if a==-1:
  print(0)
  exit()
elif a==0:
  print(1)
else:
  gyaku=[0,1]
  for i in range(2,a+1):
    gyaku.append(((p//i)*-gyaku[p%i])%p)
  com=[1]
  for i in range(1,a+1):
    com.append(com[-1]*gyaku[i]*(x-a+1-i)%p)
print(com[a])