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
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

a = x - 2 * b

MOD = 10 ** 9 + 7
a %= MOD
b %= MOD

MAX = 10 ** 6
fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]

def comInit(mod):
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 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

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

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

Submission status: Runtime Error

Solution code:
import math

I=list(map(int,input().split()))
X=(2*I[1]-I[0])//3
Y=(2*I[0]-I[1])//3
n=X+Y
r=X

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

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)

print(cmb(n, r, p))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


class CmbMod:
    def __init__(self, n, p):
        """
        二項係数nCr(n個の区別できるものからr個のものを選ぶ組み合わせの数)をpで割った余りを求める
        """
        self.n = n
        self.p = p
        self.fact = [1, 1]
        self.factinv = [1, 1]
        self.inv = [0, 1]

    def cmb_mod(self, n, r):
        """
        二項係数nCr(mod p)をO(r)にて計算。nが大きいがrは小さい時に使用。
        """
        numer, denom = 1, 1
        for i in range(r):
            numer = (numer * (n - i)) % self.p
            denom = (denom * (i + 1)) % self.p
        return (numer * pow(denom, self.p - 2, self.p)) % self.p

    def prep(self):
        """
        二項係数nCr(mod p)をO(1)で求める為の前処理をO(N)にて実行。
        """
        for i in range(2, self.n + 1):
            self.fact.append((self.fact[-1] * i) % self.p)
            self.inv.append((-self.inv[self.p % i] * (self.p // i)) % self.p)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % self.p)

    def cmb_mod_with_prep(self, n, r):
        """
        二項係数nCr(mod p)をO(1)で求める。事前にprepを実行する事。
        """
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return self.fact[n] * self.factinv[r] * self.factinv[n - r] % self.p


def resolve():
    X, Y = map(int, input().split())
    if (X + Y) % 3:
        print(0)
        exit()

    cnt = (X + Y) // 3
    for i in range(cnt):
        if (i * 1 + (cnt - i) * 2 == X and i * 2 + (cnt - i) * 1 == Y) or (
                i * 1 + (cnt - i) * 2 == Y and i * 2 + (cnt - i) * 1 == X):
            left = i
            break

    cmb = CmbMod(cnt, mod)
    res = cmb.cmb_mod(cnt, left)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

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

p = 10**9 + 7
N = 10**6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N+1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

x,y=map(int,input().split())
ans=0
x_3=x//3
y_3=y//3
kyo2=min(x_3,y_3)
xx=x-kyo2*3
yy=y-kyo2*3

#print(xx,yy,kyo2)
    
if (xx==0 and yy==0):
  ans=cmb(2*kyo2,kyo2,p)
  print(ans)
elif (xx/yy==2):
  ans=cmb(2*kyo2+yy,kyo2,p)
  print(ans)
elif (yy/xx==2):
  ans=cmb(2*kyo2+xx,kyo2,p)
  print(ans)
else:
  print(0)

Submission status: Runtime Error

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

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

x,y=map(int,input().split())
ans=0
x_3=x//3
y_3=y//3
kyo2=min(x_3,y_3)
xx=x-kyo2*3
yy=y-kyo2*3

#print(xx,yy,kyo2)
    
if (xx==0 and yy==0):
  ans=cmb(2*kyo2,kyo2,p)
  print(ans)
elif (xx/yy==2):
  ans=cmb(2*kyo2+yy,kyo2,p)
  print(ans)
elif (yy/xx==2):
  ans=cmb(2*kyo2+xx,kyo2,p)
  print(ans)
else:
  print(0)

Submission status: Runtime Error

Solution code:
def div_with_mod(x, y, mod):
    # Fermat's little theorem
    return x*pow(y, mod - 2, mod)


def comb(n, r, mod):
    # calculates C(n,r) with mod (assuming mod is prime)
    nc = n
    for rc in range(1, r):
        nc -= 1
        n = n*nc % mod
        r = r*rc % mod

    return div_with_mod(n, r, mod)


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

j = 2*x-y
if j % 3:
    print(0)
    exit()
j //= 3
i = x - 2*j
if i < 0 or j < 0:
    print(0)
    exit()

ans = comb(i+j, i)
print(ans)

Submission status: Runtime Error

Solution code:
X , Y = map(int,input().split())
if (X+Y)%3 != 0 or Y - 2*X >0 or X - 2*Y >0:
  print('0')
else:
  m = int((X+Y)/3)
  t = int((m-abs(X-Y))/2)
  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

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

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

Submission status: Runtime Error

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

if (2*X-Y)%3==0 and (2*Y-X)%3==0:
    a = (2*X-Y)//3
    b = X-2*a
    MOD = 10**9+7
    n = a+b+1
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    
    for i in range(1,n+1):
        fac[i] = i*fac[i-1]%MOD
        rev[i] = pow(fac[i], MOD-2, MOD)
    comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD

    print(comb(a+b, a))
else:
    print(0)

Submission status: Runtime Error

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

if (2*X-Y)%3 or (2*Y-X)%3:
    print(0)
else:
    a, b = (2*X-Y)//3, X-2*a
    MOD = 10**9+7
    n = a+b+1
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    
    for i in range(1,n+1):
        fac[i] = i*fac[i-1]%MOD
        rev[i] = pow(fac[i], MOD-2, MOD)
    comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD

    print(comb(a+b, a))

Submission status: Runtime Error

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

if (2*X-Y)%3:
    print(0)
else:
    a = (2*X-Y)//3
    b = X-2*a

    MOD = 10**9+7
    n = a+b+1
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    
    for i in range(1,n+1):
        fac[i] = i*fac[i-1]%MOD
        rev[i] = pow(fac[i], MOD-2, MOD)
    comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD

    print(comb(a+b, a))

Submission status: Runtime Error

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

dp =[[0]*(X+1) for i in range(Y+1)]
dp[0][0] = 1
mod = 10**9 +7
for x in range(X+1):
    for y in range(Y+1):
        if (x>1 and y>0) or (x>0 and y>1):

            dp[x][y] = (dp[x-1][y-2]+dp[x-2][y-1])%mod

print(dp[X][Y])

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np
X,Y=map(int,input().split())
DP=np.zeros((X+1,Y+1))
DP[0,0]=1
DP[2,1]=1
DP[1,2]=1
q=deque()
q.append([1,2])
q.append([2,1])
while(q):
    pos=q.popleft()
    i=pos[0]
    j=pos[1]
    if i+2<=X and j+1<=Y:
        DP[i+2,j+1]+=DP[i,j]
        q.append([i+2,j+1])
    if i+1<=X and j+2<=Y:
        DP[i+1,j+2]+=DP[i,j]
        q.append([i+1,j+2])
print(int(DP[X][Y])%(10**9+7))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
X, Y = map(int, input().split())
if (X + Y) % 3:
    exit(print(0))
m = (2*X - Y) // 3
n = X - 2*m
if n < 0 or m < 0:
    exit(print(0))

class Factorial:
    def __init__(self, n, mod):
        self.f = f =[0] * (n + 1)
        f[0] = b = 1
        for i in range(1, n + 1):f[i] = b = b * i % mod
        self.inv = inv = [0] * (n + 1)
        inv[n] = b = pow(self.f[n], -1, mod)
        for i in range(n,0,-1):inv[i-1] = b = b * i % mod
        self.mod = mod
    def factorial(self, i):
        return self.f[i]
    def ifactorial(self, i):
        return self.inv[i]
    def comb(self, n, k):
        if n >= k:return self.f[n] * self.inv[n - k] * self.inv[k] % self.mod
        else:return 0

def nCr(n, r, mod = None, limit = None):
    if mod and limit:
        return Factorial(limit, mod).comb(n, r)
    elif mod:
        r = min(r, n - r)
        a = 1
        for i in range(r):
            a = a * (n - i) * pow(i + 1, mod - 2, mod) % mod
        return a
    else:
        from math import factorial as f
        return f(n) // (f(n - r) * f(r))

MOD = 10**9+7
print(nCr(m + n, n, MOD, 2*10**6))

Submission status: Runtime Error

Solution code:
import math
X,Y=list(map(int,input().split()))
X=min(X,Y)
Y=max(X,Y)
N=Y-X
Y=Y-2*N
X=X-N
N2=X//3
ans=1
for i in range(N2,N2*2+1):
    ans=(ans%(10**9+7))*i
ans=ans%(10**9+7)
ans2=math.factorial(N2)
ans2=ans2%(10**9+7)
print(N+ans*ans2**(10**9+7-2))

Submission status: Runtime Error

Solution code:
import math
X,Y=list(map(int,input().split()))
X=min(X,Y)
Y=max(X,Y)
N=Y-X
Y=Y-2*N
X=X-N
N2=X//3
ans=1
for i in range(N2,N2*2+1):
    ans=(ans%(10**9+7))*i
ans=ans%(10**9+7)
ans2=math.factorial(N2)
ans2=ans2%(10**9+7)
print(ans*ans2**(10**9+7-2))

Submission status: Runtime Error

Solution code:

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

def dfs(x,y):
    global ans
    if not (0<=x<=X) or not (0<=y<=Y):
        return
    if x==X and y==Y:
        ans=ans%(10**9+7)+1
        return
    dfs(x+1,y+2)
    dfs(x+2,y+1)
ans=0
dfs(0,0)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

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

def dfs(x,y):
    global ans
    if not (0<=x<=X) or not (0<=y<=Y):
        return
    if x==X and y==Y:
        ans=ans%(10**9+7)+1
        return
    dfs(x+1,y+2)
    dfs(x+2,y+1)
ans=0
dfs(0,0)
print(ans)

Submission status: Runtime Error

Solution code:
a,b = map(int,input().split())
if (a+b)%3 == 0:
  n = (a+b)/3
  import math
  aa = math.factorial(a-n)
  bb = math.factorial(b-n)
  cc = math.factorial(n)
  print((cc/(bb*aa))%(10**9+7))
else:
  print(0)

Submission status: Runtime Error

Solution code:
a,b = map(int,input().split())
if (a+b)%3 == 0:
  n = (a+b)/3
  aa = math.factorial(a-n)
  bb = math.factorial(b-n)
  cc = math.factorial(n)
  print((cc/(bb*aa))%(10**9+7))
else:
  print(0)

Submission status: Runtime Error

Solution code:
a,b = map(int,input().split())
if (a+b)%3 == 0:
  a == a - min(a,b)
  b == b - min(a,b)
  c = a+b
  import math
  aa = math.factorial(a)
  bb = math.factorial(b)
  cc = math.factorial(c)
  print((cc/(bb*aa))%(10**9+7))
else:
  print(0)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys

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

if (2 * X - Y) % 3 != 0:
    # 整数解がない場合
    print(0)
    sys.exit()


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

u = m + n
fact = [1] * (u+1)

for i in range(1, u+1):
    fact[i] = (fact[i-1] * i) % mod

fact_inv1 = pow(fact[n], mod-2, mod)
fact_inv2 = pow(fact[m], mod-2, mod)

res = (((fact[u] * fact_inv1) % mod) * fact_inv2) % mod

print(res)

Submission status: Runtime Error

Solution code:
from math import factorial as fac
X,Y=map(int,input().split())

if (2*Y-X)%3!=0 or (2*X-Y)%3!=0:
    print(0)
else:
    a=(2*Y-X)//3
    b=(2*X-Y)//3
    print((fac(a+b)//fac(a)//fac(b))%(10**9+7))

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit


def initialize_cmb(m, mod=10 ** 9 + 7):
    fac = [1]
    finv = [1]
    inv = [0] * (m + 1)
    if m > 1:
        fac.append(1)
        finv.append(1)
        inv[1] = 1
        pre_fac = 1
        pre_finv = 1
        for i in range(2, m + 1):
            pre_fac = pre_fac * i % mod
            fac.append(pre_fac)
            inv[i] = mod - inv[mod % i] * (mod // i) % mod
            pre_finv = pre_finv * inv[i] % mod
            finv.append(pre_finv)
    return fac, finv


def cmb(n, k, fac, finv, mod=10 ** 9 + 7):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


def main():
    mod = 10 ** 9 + 7
    input = stdin.buffer.readline
    x, y = map(int, input().split())

    if (x + y) % 3 != 0 or 2 * x < y or 2 * y < x:
        print(0)
    else:
        fac, finv = initialize_cmb((x + y) // 3, mod)

        x_min = (x + y) // 3
        y_max = 2 * (x + y) // 3

        print(cmb((x + y) // 3, x - x_min, fac, finv, mod))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Runtime Error

Solution code:
import math
x,y = map(int,input().split())
mod = 10**9+7
reuslt = 0
if (x+y) %3 == 0:

    n = (2*x-y)//3
    m = (2*y-x)//3
    result  =math.factorial(n+m)//math.factorial(n)
    result = result%mod
else :
    result = 0

print(result)

Submission status: Runtime Error

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

dp = [[0]*(x*2+1) for _ in range(x+1)]
dp[2][2] = 0
start = 0
end = 0

for i in range(1,x+1):
    if i%2 == 0:
        start = i//2
        dp[i][start] = 1
    else :
        start = int(math.ceil(i/2+1))
        
    end = i*2
    dp[i][end] = 1
    
    for j in range(start,end+1,3):
        if dp[i][j] == 0:
            dp[i][j] += dp[i-1][j-2] + dp[i-2][j-1]


print(dp[x][y])

Submission status: Runtime Error

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

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def mod_combinations_cont(n, r, mod):
    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:
    print(0)
else:
    n=(x+y)//3
    m=(-x+2*y)/3
    if n<0 or m<0:
        print(0)
        exit()
    else:
        print(mod_combinations_cont(n,m,mod)%mod)

Submission status: Runtime Error

Solution code:
#ABC145D
def main():
    import sys, math
    X, Y = map(int, sys.stdin.readline().split())
    '''
    i +2*j ==X
    2*i +j ==Y
    '''
    if (2*Y-X)%3==0:
        i = (2*Y-X)//3
        j = Y-2*i
    else:
        ans =0
    #print(i, j)
    mod = 10**9+7
    def calc(n):
        ans = 1
        for i in range(n, 1, -1):
            ans *= i
            ans %= mod
        return ans
    
    ans = calc(i+j)
    #print(calc(-1))
    #print(ans)
    
    #calc2(calc(i), mod-2)
    gg1 = pow(calc(i), mod-2, mod)
    gg2 = pow(calc(j), mod-2, mod)
    
    if i<0 or j<0:
        print(0)
    elif i==0 and j==0:
        print(0)
    else:
        print(ans*gg1*gg2%mod)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
from itertools import combinations
x,y=map(int, input().split())

n = 0
m = 0
MOD = 10**9 + 7
if (x+y)%3 != 0:
    print(0)
    exit()
elif x < 3 or y < 3:
    n = min(x,y)
    m = 0
else:
    m = x - int(x/3) - int(y/3)
    n = int((x+y)/3) - m
ans = len(list(combinations(range(n+m),n))) % MOD
print(ans)

Submission status: Runtime Error

Solution code:
import math
x,y = map(int,input().split())
mod = pow(10,9)+7
if (2*x-y)% 3 == 0 and (2*y-x)% 3 == 0:
	n = int((2 * y - x) / 3)
	m = int((2 * x - y) / 3)
	P = [1]*(n + m + 1)
	for i in range(1, n+m+1):
		P[i] = P[i-1]*i
		P[i] %= mod
	print((P[n+m]*pow(P[n],mod-2,mod)*pow(P[m],mod-2,mod)) % mod)
else:
	print(0)

Submission status: Runtime Error

Solution code:
import math
x,y = map(int,input().split())
if (2*x-y)% 3 == 0 and (2*y-x)% 3 == 0:
	n = (2*y-x)/3
	m = (2*x-y)/3
	p = m/n
	print(int(pow(1+p,n)*pow(1+1/p,m)*math.sqrt((n+m)/(n*m))/math.sqrt(2*math.pi))%(pow(10,9)+7))
#	print(int(math.factorial(n+m)/(math.factorial(n)*math.factorial(m)))%(pow(10,9)+7))
else:
	print(0)

Submission status: Runtime Error

Solution code:
import math
x,y = map(int,input().split())
if (2*x-y)% 3 == 0 and (2*y-x)% 3 == 0:
	n = (2*y-x)/3
	m = (2*x-y)/3
	print(int(math.factorial(n+m)/(math.factorial(n)*math.factorial(m)))%(pow(10,9)+7))
else:
	print(0)

Submission status: Runtime Error

Solution code:
from math import factorial

import sys

sys.setrecursionlimit(10000)

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

x,y = nm()

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

mod = 10**9+7

n = (x+y)//3
a,b = x-n,y-n

fab = factorial(a+b)%mod
fa = factorial(a)%mod
fb = factorial(b)%mod

def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p))%p

ans = (fab*power_func(fa,mod-2,mod)*power_func(fb,mod-2,mod))%mod


print(ans)

Submission status: Runtime Error

Solution code:
from math import factorial

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

x,y = nm()

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

mod = 10**9+7

n = (x+y)//3
a,b = x-n,y-n

fab = factorial(a+b)%mod
fa = factorial(a)%mod
fb = factorial(b)%mod

def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

ans = (fab*power_func(fa,mod-2,mod)*power_func(fb,mod-2,mod))%mod


print(ans)

Submission status: Runtime Error

Solution code:
import math

x, y = map(int, input().split())
mod = 10 ** 9 + 7
a = (2 * y - x) / 3
b = (2 * x - y) / 3

if (not a.is_integer()) or (not b.is_integer()):
    print(0)
else:
    a, b = int(a), int(b)
    I = [1] * (a + b + 1)
    for n in range(1, a+b+1):
        I[n] = I[n-1] * n
        I[n] %= mod
    i, j, k = I[a+b], I[a], I[b]
    j = pow(j, mod-2, mod)
    k = pow(k, mod-2, mod)

    ans = i * j * k
    ans %= mod
    print(ans)

Submission status: Runtime Error

Solution code:
X, Y = map(int, input().split())
mod = 10**9+7
b = (2*Y-X)//3
a = Y - 2*b
max_num = a + b + 5
facts = [1 for i in range(max_num)]
invs = [1 for i in range(max_num)]
 
def inv(x):
    return pow(x,mod-2,mod)
 
for i in range(1,max_num):
    facts[i] = facts[i-1]*i%mod
    invs[i] = inv(facts[i])
 
def nCk(n,k):
    return facts[n]*invs[k] * invs[n-k] % mod

if (X+Y)%3 == 0:
    print(nCk(a+b, a))
else:
    print(0)

Submission status: Runtime Error

Solution code:
X, Y = map(int, input().split())
mod = 10**9+7
b = (2*Y-X)//3
a = Y - 2*b
max_num = a + b + 1
facts = [1 for i in range(max_num)]
invs = [1 for i in range(max_num)]
 
def inv(x):
    return pow(x,mod-2,mod)
 
for i in range(1,max_num):
    facts[i] = facts[i-1]*i%mod
    invs[i] = inv(facts[i])
 
def nCk(n,k):
    return facts[n]*invs[k] * invs[n-k] % mod

def nHk(n, k):
  return nCk(n-1+k, n-1)

if (X+Y)%3 == 0:
    print(nCk(a+b, a))
else:
    print(0)

Submission status: Runtime Error

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

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


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)
        return
    a = (X + Y) // 3
    two = X - a
    if two < 0:
        print(0)
    cmb = Combination(a + 1)
    print(cmb(a, two))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

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


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)
        return
    a = (X + Y) // 3
    two = X - a
    one = a - two
    cmb = Combination(a + 1)
    print(cmb(a, two))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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

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


def mod_com(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    if k > n - k:
        k = n - k
    ans = 1
    for i in range(n - k + 1, n + 1):
        ans = ans * i % MOD

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

    return ans


print(mod_com(n, x))

Submission status: Runtime Error

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

from math import factorial 
def main():
    x, y = map(int, readline().split())
    if ((2*y-x)%3) or ((2*x-y)%3):
        print(0)
        return
    a = (2*y-x)//3
    b = (2*x-y)//3
    P = int(1e9)+7
    def c(n, m):
        ch = 1
        for i in range(m):
            ch *= (n-i)
            ch %= P
        b = factorial(m) 
        b = pow(b, P-2, P)
        return ch*b%P
    print(c(a+b, a)) 
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
X,Y = map(int,input().split())
# 何回移動するか
r = (X+Y)//3
# 移動の可能性 rC(x-r)
from functools import reduce
mod = 10**9+7
if (X+Y)%3==0:
    r = (X+Y)//3
    if r != X and r != Y:
        try:
            num = reduce(lambda x,y:x*y%mod,[k+1 for k in range(r)])
            p = reduce(lambda x,y:x*y%mod,[k+1 for k in range(X-r)])
            q = reduce(lambda x,y:x*y%mod,[k+1 for k in range(2*r-X)])
            ans = num*pow(p,mod-2,mod)*pow(q,mod-2,mod)%mod
            print(ans%mod)  
        except:
            num = reduce(lambda x,y:x*y%mod,[k+1 for k in range(r)])
            p = reduce(lambda x,y:x*y%mod,[k+1 for k in range(X-r)])
            ans = num*pow(p,mod-2,mod)%mod
            print(ans%mod)  
    else:
        print(1)
else:
    print(0)

Submission status: Runtime Error

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

N = min(X,Y)
def pow_mod(x, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return pow_mod(x * x % MOD, n // 2) % MOD
    else:
        return x * pow_mod(x * x % MOD, n // 2) % MOD

fact = [1]
for i in range(1,N+1):
    fact.append( (fact[i-1] * i) % MOD )

inv = [1] * (N+1)
inv[N] = pow_mod(fact[N], MOD-2)
for i in range(N, 1, -1):
    inv[i-1] = inv[i] * (i) % MOD

def cmb_mod(n,r):
    return fact[n] * inv[r] * inv[n-r] % MOD


cnt = 0
x,y = X,Y
while x > 0 and y > 0:
    if x == 2*y or y == 2*x:
        break
    x -= 3
    y -= 3
    cnt += 1

ans = 0
if x == 0 and y == 0:
    ans = cmb_mod(cnt*2, cnt)
elif x == 2*y or y == 2*x:
    ans = cmb_mod(cnt+2, cnt) * (cnt+1) % MOD

print(ans)

Submission status: Runtime Error

Solution code:
X,Y = map(int,input().split())
# 何回移動するか
r = (X+Y)//3
# 移動の可能性 rC(x-r)
from functools import reduce
mod = 10**9+7
if (X+Y)%3==0:
    r = (X+Y)//3
    if r != X and r != Y:
        if r != X*0.5 and r != Y*0.5:
            num = reduce(lambda x,y:x*y%mod,[k+1 for k in range(r)])
            p = reduce(lambda x,y:x*y%mod,[k+1 for k in range(X-r)])
            q = reduce(lambda x,y:x*y%mod,[k+1 for k in range(2*r-X)])
            ans = num*pow(p,mod-2,mod)*pow(q,mod-2,mod)%mod
            print(ans%mod)  
        else:
            num = reduce(lambda x,y:x*y%mod,[k+1 for k in range(r)])
            p = reduce(lambda x,y:x*y%mod,[k+1 for k in range(X-r)])
            ans = num*pow(p,mod-2,mod)%mod
            print(ans%mod)  
    else:
        print(1)
else:
    print(0)

Submission status: Runtime Error

Solution code:
X,Y = map(int,input().split())
# 何回移動するか
r = (X+Y)//3
# 移動の可能性 rC(x-r)
from functools import reduce
mod = 10**9+7
if (X+Y)%3==0:
    r = (X+Y)//3
    if r != X and r != Y:
        if r != X*0.5 and r != Y*0.5:
        num = reduce(lambda x,y:x*y%mod,[k+1 for k in range(r)])
        p = reduce(lambda x,y:x*y%mod,[k+1 for k in range(X-r)])
        q = reduce(lambda x,y:x*y%mod,[k+1 for k in range(2*r-X)])
        ans = num*pow(p,mod-2,mod)*pow(q,mod-2,mod)%mod
        print(ans%mod)  
        else:
            num = reduce(lambda x,y:x*y%mod,[k+1 for k in range(r)])
            p = reduce(lambda x,y:x*y%mod,[k+1 for k in range(X-r)])
            ans = num*pow(p,mod-2,mod)%mod
            print(ans%mod)  
    else:
        print(1)
else:
    print(0)

Submission status: Runtime Error

Solution code:
X,Y = map(int,input().split())
# 何回移動するか
r = (X+Y)//3
# 移動の可能性 rC(x-r)
from functools import reduce
mod = 10**9+7
if (X+Y)%3==0:
    r = (X+Y)//3
    if r != X and r != Y and r != X*0.5:
        num = reduce(lambda x,y:x*y%mod,[k+1 for k in range(r)])
        p = reduce(lambda x,y:x*y%mod,[k+1 for k in range(X-r)])
        q = reduce(lambda x,y:x*y%mod,[k+1 for k in range(2*r-X)])
        ans = num*pow(p,mod-2,mod)*pow(q,mod-2,mod)%mod
        print(ans%mod)  
    elif r != X and r != Y and r == X*0.5:
        num = reduce(lambda x,y:x*y%mod,[k+1 for k in range(r)])
        p = reduce(lambda x,y:x*y%mod,[k+1 for k in range(X-r)])
        ans = num*pow(p,mod-2,mod)%mod
        print(ans%mod)  
    else:
        print(1)
else:
    print(0)

Submission status: Runtime Error

Solution code:
X,Y = map(int,input().split())
# 何回移動するか
r = (X+Y)//3
# 移動の可能性 rC(x-r)
from functools import reduce
mod = 10**9+7
if (X+Y)%3==0:
    r = (X+Y)//3
    if r != X and r != Y and X != 2*Y:
        num = reduce(lambda x,y:x*y%mod,[k+1 for k in range(r)])
        p = reduce(lambda x,y:x*y%mod,[k+1 for k in range(X-r)])
        q = reduce(lambda x,y:x*y%mod,[k+1 for k in range(2*r-X)])
        ans = num*pow(p,mod-2,mod)*pow(q,mod-2,mod)%mod
        print(ans%mod)  
    elif r != X and r != Y and X==2*Y:
        num = reduce(lambda x,y:x*y%mod,[k+1 for k in range(r)])
        p = reduce(lambda x,y:x*y%mod,[k+1 for k in range(X-r)])
        ans = num*pow(p,mod-2,mod)%mod
        print(ans%mod)  
    else:
        print(1)
else:
    print(0)

Submission status: Runtime Error

Solution code:
X,Y = map(int,input().split())
# 何回移動するか
r = (X+Y)//3
# 移動の可能性 rC(x-r)
from functools import reduce
mod = 10**9+7
if (X+Y)%3==0:
    r = (X+Y)//3
    if r != X and r != Y:
        num = reduce(lambda x,y:x*y%mod,[k+1 for k in range(r)])
        p = reduce(lambda x,y:x*y%mod,[k+1 for k in range(X-r)])
        q = reduce(lambda x,y:x*y%mod,[k+1 for k in range(2*r-X)])
        ans = num*pow(p,mod-2,mod)*pow(q,mod-2,mod)%mod
        print(ans%mod)  
    else:
        print(1)
else:
    print(0)

Submission status: Runtime Error

Solution code:
X,Y = map(int,input().split())
# 何回移動するか
r = (X+Y)//3
# 移動の可能性 rC(x-r)
from functools import reduce
mod = 10**9+7
if (X+Y)%3==0:
    r = (X+Y)//3
    num = reduce(lambda x,y:x*y%mod,[k+1 for k in range(r)])
    p = reduce(lambda x,y:x*y%mod,[k+1 for k in range(X-r)])
    q = reduce(lambda x,y:x*y%mod,[k+1 for k in range(2*r-X)])
    ans = num*pow(p,mod-2,mod)*pow(q,mod-2,mod)%mod
    print(ans%mod)   
else:
    print(0)

Submission status: Runtime Error

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

if (X + Y) % 3 != 0:
    print(0)
else:
    n2x = (2*X - Y) // 3
    n1x = (2*Y - X) // 3
    n = n2x + n1x

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

    print(combs(n, n2x))