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

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

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

if n < 0 or m < 0:
	print(0)
	exit()

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 )

a = cmb(n+m,n,mod)

print(a)

Submission status: Runtime Error

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

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

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

if n < 0 or m < 0:
	print(0)
	exit()
from math import factorial
ans = factorial(n+m) / factorial(n) / factorial(m)

print(ans)

Submission status: Runtime Error

Solution code:
def cal(big,small):
  ans = 1
  div = big - small
  for t in range(div):
    ans = ans*(big-t-1)
    ans = ans / (t+1)

x = input()
y = input()
if x <= 2y and y <= 2x:
  if x > y:
    cal(x,y)
  else:
    cal(y,x)

Submission status: Runtime Error

Solution code:
X,Y=map(int,input().split())
if (X+Y)%3!=0:
  print("No")
else:
  n=(2*X-Y)//3
  m=(2*Y-X)//3
  if n<0 or m<0:
    print("No")
  else:
    def kaijou(n):
      if n==1:
        return 1
      else:
        return n*kaijou(n-1)
    x=1
    for j in range(m+1,n+m+1):
      x=x*j
    print((x//kaijou(n))%(10**9+7))

Submission status: Runtime Error

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

MOD = 10**9+7  # type: int

def combi_count(n, r):
    x = 1
    y = 1
    for i in range(1, r+1):
        x *= (n-i) % MOD
        y *= i % MOD

    # nCr = n!/((n-r)!*r!) = (n!/(n-r)!) / r! 
    #     :=                 (    x    ) / y

    # x / y            % MOD
    # x * y^(-1)       % MOD
    # x * y**(MOD - 2) % MOD (from フェルマー定理)

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

def solve(X: int, Y: int):
    a = int((2*Y - X)/3)
    b = int((2*X - Y)/3)
    if ((2*Y - X)%3 != 0) and ((2*X - Y)%3 != 0):
        ans = 0
    else:
        if (a<0) or (b<0):
            ans = 0
        else:
            ans = combi_count(a+b, min(a, b))
    print(int(ans%MOD))

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

if __name__ == '__main__':
    main()
atcoder-tools: The pre-rendered templates are not found.

Submission status: Runtime Error

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

MOD = 10**9+7  # type: int

def combi_count(n, r):
    x = 1
    y = 1
    for i in range(1, r+1):
        x *= (n-i) % MOD
        y *= i % MOD

    # nCr = n!/((n-r)!*r!) = (n!/(n-r)!) / r! 
    #     :=                 (    x    ) / y
    
    # x / y            % MOD
    # x * y^(-1)       % MOD
    # x * y**(MOD - 2) % MOD (from フェルマー定理)

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

def solve(X: int, Y: int):
    a = (2*Y - X)/3
    b = (2*X - Y)/3
    if ((2*Y - X)%3 != 0) and ((2*X - Y)%3 != 0):
        ans = 0
    else:
        if (a<0) or (b<0):
            ans = 0
        else:
            ans = combi_count(a+b, min(a, b))
    print(int(ans%MOD))

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
atcoder-tools: The pre-rendered templates are not found.

Submission status: Runtime Error

Solution code:

if __name__ == "__main__":
  law = 10 ** 9 + 7
  
  dest_x, dest_y = sorted(map(int, input().split()), reverse=True)
  W = H = dest_x + 1
  
  num_pattern = [[0] * W for j in range(H)]
  
  num_pattern[0][0] = 1
  
  stack = [(0, 0, 0, 0)]
  moves = [(1, 2), (2, 1)]
  
  while(stack):
    x, y, or_x, or_y = stack.pop(0)
    
    for dx, dy in moves:
      if x + dx != or_x and y + dy != or_y and 0 <= x + dx < W and 0 <= y + dy < H and x + dx >= y + dy:
        num_pattern[x + dx][y + dy] += num_pattern[x][y]
        stack.append((x + dx, y + dy, x, y))
      
  print(num_pattern[dest_x][dest_y] * 2 % law)
  pass

Submission status: Runtime Error

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

MOD = 10**9+7  # type: int

def solve(X: int, Y: int):
    a = (2*Y - X)/3
    b = (2*X - Y)/3
    if ((2*Y - X)%3 != 0) and ((2*X - Y)%3 != 0):
        ans = 0
    else:
        if a<0 or b<0:
            ans = 0
        else:
            factorial_ab = math.factorial(int(min(a, b)))
            ans = math.factorial(int(a+b)) / factorial_ab
    print(int(ans%MOD))

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

MOD = 10**9+7  # type: int

def solve(X: int, Y: int):
    a = (2*Y - X)/3
    b = (2*X - Y)/3
    if ((2*Y - X)%3 != 0) and ((2*X - Y)%3 != 0):
        ans = 0
    else:
        if (a<0) or (b<0):
            ans = 0
        else:
            factorial_ab = math.factorial(int(min(a, b)))
            ans = math.factorial(int(a+b)) / factorial_ab
    print(int(ans%MOD))

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

MOD = 1000000007  # type: int

def solve(X: int, Y: int):
    a = (2*Y - X)/3
    b = (2*X - Y)/3
    if ((2*Y - X)%3 != 0) and ((2*X - Y)%3 != 0):
        ans = 0
    else:
        if (a<0) or (b<0):
            ans = 0
        else:
            factorial_ab = math.factorial(int(min(a, b)))
            ans = math.factorial(int(a+b)) / factorial_ab
    print(int(ans%MOD))

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

MOD = 1000000007  # type: int

def solve(X: int, Y: int):
    a = (2*Y - X)/3
    b = (2*X - Y)/3
    if ((2*Y - X)%3 != 0) and ((2*X - Y)%3 != 0):
        ans = 0
    else:
        if (a<0) or (b<0):
            ans = 0
        else:
            f_a = math.factorial(int(a))
            if a==b:
                ans = math.factorial(int(a+b)) / f_a / f_a
            else:
                ans = math.factorial(int(a+b)) / f_a / math.factorial(int(b))
    print(int(ans%MOD))

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(X, Y)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
X,Y=map(int, input().split())
if (X+Y)%3!=0:
  print(0)
  exit()
n=(X+Y)//3
for i in range(n+1):
  if 2*i +(n-i) == X:
    right=i
    up=n-i
    if 2*(n-i)+i !=Y:
      print(0)
      exit()
    break
  elif 2*(n-i)+i == X:
    up=i
    right=n-i
    if 2*i +(n-i) == Y:
      print(0)
      exit()
    break

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 #出力の制限
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(n,right,mod)
print(a)

Submission status: Runtime Error

Solution code:
import math
X,Y=map(int, input().split())
if (X+Y)%3!=0:
  print(0)
  exit()
n=(X+Y)//3
for i in range(n+1):
  if 2*i +(n-i) == X:
    right=i
    up=n-i
    break
  elif 2*(n-i)+i == X:
    up=i
    right=n-i
    break

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 #出力の制限
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(n,right,mod)
print(a)

Submission status: Runtime Error

Solution code:
import math

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

else:
    print(0)

Submission status: Runtime Error

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

for i in range(data[0]//2):
  if (data[1]-i)%2==0 and (data[1]-i)//2==data[0]-2*i:
    a=i
    b=data[0]-2*i

import math
def C(n, r):
  return P(n, r)//math.factorial(r)

print( C(a+b,b)%(10**9+7) )

Submission status: Runtime Error

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

for i in range(data[0]//2):
  if (data[1]-i)%2==0 and (data[1]-i)//2==data[0]-2*i:
    a=i
    b=data[0]-2*i
import math
def conbination(n, r):
  return int(math.factorial(n) / math.factorial(n - r)*math.factorial(r))*(10**9+7)
print(conbination(a,b))

Submission status: Runtime Error

Solution code:
import sys
import math
x,y=map(int,input().split())
if (x+y)%3!=0:
  print(0)
  sys.exit()
n=(x+y)//3
print(math.factorial(n)//math.factorial(x-n)//math.factorial(y-n))

Submission status: Runtime Error

Solution code:
import sys
import math
x,y=map(int,input().split())
if (x+y)%3!=0:
  print(0)
  sys.exit()
n=(x+y)//3
print(math_factorial(n)//math_factorial(x-n)//math_factorial(y-n))

Submission status: Runtime Error

Solution code:
import sys
x,y=map(int,input().split())
if (x+y)%3!=0:
  print(0)
  sys.exit()
n=(x+y)//3
fac=[1 for i in range(n+1)]#fac[i]=i!. fac[0]=1
for i in range(n+1):
  fac[i]=fac[i-1]*i

print(fac[n]//fac[x-n]//fac[y-n])

Submission status: Runtime Error

Solution code:
inport sys
x,y=map(int,input().split())
if (x+y)%3!=0:
  print(0)
  sys.exit()
n=(x+y)//3
fac=[1 for i in range(n+1)]#fac[i]=i!. fac[0]=1
for i in range(n+1):
  fac[i]=fac[i-1]*i

print(fac[n]//fac[x-n]//fac[y-n])

Submission status: Runtime Error

Solution code:
inport sys
fac=[1 for i in range(n+1)]#fac[i]=i!. fac[0]=1
for i in range(n+1):
  fac[i]=fac[i-1]*i

def comb(n,k):
  return fac[n]//fac[k]//fac[n-k]

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

Submission status: Runtime Error

Solution code:
"""def factorial(x):
  a = 1
  for i in range(1, x+1):
    a *= i
  return a           #階乗の計算"""
mod = 10**7 + 9
import math
X, Y = map(int, input().split())
if (2*X - Y)%3 == 0 and (2*Y - X)%3 == 0:
  a = math.factorial((2*X-Y)//3)
  b = math.factorial((2*Y-X)//3)
  c = math.factorial((2*X-Y)//3 + (2*Y-X)//3)
  print((c//(a*b))%mod)
else:
  print(0)

Submission status: Runtime Error

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

def f(x, p):
    a = 1
    for i in range(1, x + 1):
        a *= i
        a %= p
    return a
def nCr(a, b, p):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= f(a, p)
    c *= pow(f(b, p), p - 2, p)
    c *= pow(f(a - b, p), p - 2, p)
    return c % p

if (2*X-Y)%3 != 0 or (2*Y-X)%3 != 0 or Y > X*2 or X > Y*2:
  print(0)
else:
  m = (2*X-Y)//3
  n = (2*Y-X)//3
  print(nCr(m+n, n))

Submission status: Runtime Error

Solution code:
import sys
from math import factorial
from scipy.special import comb
 
def ncr(n, r, p): 
    return comb(n,r,exact=True) % p 

def check(x, y):
    if x < y:
        tmp = x
        x = y
        y = tmp
 
    n = x - y
    x -= 2 * n
 
    if (x + y) % 3 == 0:
        return True
    else:
        return False
    
 
# Read
line = sys.stdin.readlines()[0]
X, Y = map(int,line.split(' '))
 
# if not check(X, Y):
#     print(0)
#     exit(0)
 
m = int(1/3 * (2*Y - X))
n = int(Y - 2 * m)
 
if n < 0 or m < 0:
    print(0)
else:
    p = m if m < n else n
    print(ncr(n+m, p))

Submission status: Runtime Error

Solution code:
def make_tables(m):
    fac=[1,1]
    finv=[1,1]
    inv=[0,1]
    for i in range(2,m+1):
        fac.append((fac[-1]*i)%mod)
        inv.append((-inv[mod%i]*(mod//i))%mod)
        finv.append(finv[i-1]*inv[i]%mod)
    return fac,finv
 calc_nCk(n,k,fac,finv):
    if n<k or (n<0 or k<0):
        return 0
    k=min(k,n-k)
    return fac[n]*(finv[k]*finv[n-k]%mod)%mod

x,y=map(int,input().split())
mod=10**9+7
n=(y-0.5*x)/1.5
if int(n)!=n:
    print(0)
else:
    m=(y+x)//3
    l=int(n)
    fac,finv=make_tables(m)
    ans = calc_nCk(m,l,fac,finv)
    print(ans)

Submission status: Runtime Error

Solution code:
def app1(n):
    s=1

    for i in range(1,n+1):
        s=s*i

    return s

def app2(n1,n2):
    s=1

    for i in range(n1+1,n2+1):

        s=s*i

    return s

X,Y=input().split()

X=int(X)

Y=int(Y)

A=2*X-Y

B=2*Y-X

if (A%3==0)and (B%3==0):
    A=A/3

    B=B/3

    if A==0 and B==0:
        print("0")

    elif(A!=0 and B==0) or (A==0 and B!=0):

        print("1")
    else:
        Max=max(A,B)

        Min=min(A,B)

        Max=int(Max)

        Min=int(Min)

        n1=app1(Max+1-Min)

        n2=app2(Min,Max+1)

        ans=int(n2/n1)

        print(ans)

else:

    print("0")

Submission status: Runtime Error

Solution code:
import logging
import math

logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.disable(logging.CRITICAL)


def combination(n, m, mod = 10 ** 9 + 7):
    return (math.factorial(n + m) // (math.factorial(n) * math.factorial(m))) % mod

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

    if (X + Y) % 3 != 0:
        print(0)
    else:
        m = (2 * X - Y) // 3
        n = (2 * Y - X) // 3
    
        print(combination(n, m))
    
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
mod=10**9+7
x,y=map(int,input().split())
a=[0]*101
b=[0]*101
a[1]=1
if (x+y)%3!=0:
    print(0)
    exit()
#move cnt
m=(x+y)//3

if x>m*2 or y>m*2:
    print(0)
    exit()
print(a[200])
exit()

Submission status: Runtime Error

Solution code:
import sys
from math import factorial

def ncr(n, r, p): 
    # initialize numerator 
    # and denominator 
    num = den = 1 
    for i in range(r): 
        num = (num * (n - i)) % p 
        den = (den * (i + 1)) % p 
    return (num * pow(den,  
            p - 2, p)) % p 

def check(x, y):
    if x < y:
        tmp = x
        x = y
        y = tmp

    n = x - y
    x -= 2 * n

    if (x + y) % 3 == 0:
        return True
    else:
        return False
    

# Read
line = sys.stdin.readlines()[0]
X, Y = map(int,line.split(' '))

# if not check(X, Y):
#     print(0)
#     exit(0)

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

if n < 0 or m < 0:
    print(0)
else:
    p = m if m < n else n
    print(ncr(n+m, p))

Submission status: Runtime Error

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

def my_pow(x, n, mod): # 2分累乗法
    if n == 0:
        return 1
    elif n % 2 == 0:
        return my_pow((x * x) % mod, n // 2, mod)
    else:
        return (x * my_pow(x, n - 1, mod)) % mod

if (X + Y) % 3 != 0:
    ans = 0
else:
    mod = 10 ** 9 + 7
    n = int((-1/3) * X + (2/3) * Y) 
    m = int((2/3) * X + (-1/3) * Y)
    if n < 0 or m < 0:
        ans = 0
    print(n, m)

    a = math.factorial(n)
    b = math.factorial(m)
    f = math.factorial(n+m)

    inv_a = my_pow(a, mod-2, mod)
    inv_b = my_pow(b, mod-2, mod)
    ans = f * (inv_a * inv_b % mod) % mod 

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dt
def factorization(NUM,DICT):
    temp = NUM
    for i in range(2, int(-(-NUM**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //=i
            DICT[i] += cnt
    
    if temp != 1:
        DICT[temp] += 1
    return DICT
    
def nCr(n,r,mod):
    multiple_list = [i for i in range(n,n-r,-1)]
    devide_list = [i for i in range(r,0,-1)]
    
    multiple_dict = dt(int)
    devide_dict = dt(int)
    
    for multiple in multiple_list:
        multiple_dict = factorization(multiple,multiple_dict)
    for devide in devide_list:
        devide_dict = factorization(devide,devide_dict)
    
    for key in devide_dict:
        multiple_dict[key] -= devide_dict[key]
    
    ncr = 1
    
    for key in multiple_dict:
        ncr *= key ** multiple_dict[key]
        ncr %= mod
    
    return ncr
    
X,Y = [int(i) for i in input().split()]
def check(x,y):
    if x/2 == y:
        return 0
    elif x/2 < y:
        return 1
    else:
        return 9
cnt = 0
possible = True
MOD = 10**9 + 7

while True:
    check_num =  check(X,Y)
    if check_num == 0:
        break
    elif check_num == 1:
        X += 1
        Y -= 1
        cnt += 1
    else:
        possible = False
        break
if possible == True:
    n = X // 2 
    r = cnt
    print(nCr(n,r,MOD))
else:
    print(0)

Submission status: Runtime Error

Solution code:
import sys
from math import factorial

def check(x, y):
    if x < y:
        tmp = x
        x = y
        y = tmp

    n = x - y
    x -= 2 * n

    if (x + y) % 3 == 0:
        return True
    else:
        return False
    

# Read
line = sys.stdin.readlines()[0]
X, Y = map(int,line.split(' '))

if not check(x, y):
    print(0)

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

ans = factorial(n+m) / factorial(n)

Submission status: Runtime Error

Solution code:
import sys
from math import factorial

def check(x, y):
    if x < y:
        tmp = x
        x = y
        y = tmp

    n = x - y
    x -= 2 * n

    if x + y % 3 == 0:
        return True
    else:
        return False
    

# Read
line = sys.stdin.readlines()[0]
X, Y = map(int,line.split(' '))

if not check(x, y):
    print(0)
    exit(0)

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

ans = factorial(n+m) / factorial(n)

Submission status: Runtime Error

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


MOD = 10**9 + 7

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

pascal_depth = int((X + Y) / 3)  # パスカルの三角形に当たるn
x, y = int((X + Y) * 2 / 3), (X + Y) / 3
pascal_k = x - X  # 端からいくつずれているか

if pascal_k > pascal_depth / 2:
    pascal_k = pascal_depth - pascal_k


# 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 = pascal_depth
# 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)

import sys
sys.setrecursionlimit(2**16)


def mod_combination(n, k, mod):
    # nCk (mod m)
    def mod_permutation(n, k, mod):
        if n <= k:
            return 1
        else:
            return (n * mod_permutation(n - 1, k, mod)) % mod

    def mod_inv_permutation(k, mod):
        k, mod = int(k), int(mod)
        if k <= 1:
            return 1
        else:
            return (pow(k, mod - 2, mod) * mod_inv_permutation(k - 1, mod)) % mod

    return (mod_permutation(n, n - k, mod) * mod_inv_permutation(k, mod)) % mod


a = mod_combination(pascal_depth, pascal_k, MOD)
print(a)

Submission status: Runtime Error

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


MOD = 10**9 + 7

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

pascal_depth = int((X + Y) / 3)  # パスカルの三角形に当たるn
x, y = int((X + Y) * 2 / 3), (X + Y) / 3
pascal_k = x - X  # 端からいくつずれているか

if pascal_k > pascal_depth / 2:
    pascal_k = pascal_depth - pascal_k


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 = pascal_depth
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

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


def mod_combination(n, k, mod):
    # nCk (mod m)
    def mod_permutation(n, k, mod):
        if n <= k:
            return 1
        else:
            return (n * mod_permutation(n - 1, k, mod)) % mod

    def mod_inv_permutation(k, mod):
        k, mod = int(k), int(mod)
        if k <= 1:
            return 1
        else:
            return (pow(k, mod - 2, mod) * mod_inv_permutation(k - 1, mod)) % mod

    return (mod_permutation(n, n - k, mod) * mod_inv_permutation(k, mod)) % mod


a = mod_combination(pascal_depth, pascal_k, MOD)
print(a)

Submission status: Runtime Error

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

if (X + Y) % 3 != 0:
    ans = 0
else:
    mod = 10 ** 9 + 7
    m = (X + Y) // 3 #動かした回数
    d = X - m # m回とも1進むことにすると，あぶれた回数が2進む回数と一致する

    def my_pow(x, n, mod): # 2分累乗法
        if n == 0:
            return 1
        elif n % 2 == 0:
            return my_pow((x * x) % mod, n // 2, mod)
        else:
            return (x * my_pow(x, n - 1, mod)) % mod
    
    a = math.factorial(m-d) % mod
    b = math.factorial(d) % mod
    n = math.factorial(m)
    p = my_pow(a, mod-2, mod)
    q = my_pow(b, mod-2, mod)
    pq = (p * q) % mod
    ans = (n * pq) % mod

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
from operator import mul
from functools import reduce
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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**5
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= (int(_) for _ in input().split()) 
if (x+y)%3!=0:
    print(0)
    sys.exit()
else:
    n=(x+y)/3
    n=int(n)
    if x<n or y<n:
         print(0)
         sys.exit()
    else:
        x=x-n
        y=y-n
        ans=int(cmb(x+y, x,mod))
        print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import sys
import math
from operator import mul
from functools import reduce
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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= (int(_) for _ in input().split()) 
if (x+y)%3!=0:
    print(0)
    sys.exit()
else:
    n=(x+y)/3
    n=int(n)
    if x<n or y<n:
         print(0)
         sys.exit()
    else:
        x=x-n
        y=y-n
        ans=int(cmb(x+y, x,mod))
        print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import sys
import math
from operator import mul
from functools import reduce
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

x,y= (int(_) for _ in input().split()) 
if (x+y)%3!=0:
    print(0)
    sys.exit()
else:
    n=(x+y)/3
    n=int(n)
    if x<n or y<n:
         print(0)
         sys.exit()
    else:
        x=x-n
        y=y-n
        ans=int(cmb(x+y, xy))
        print(ans%1000000007)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

x,y= (int(_) for _ in input().split()) 
if (x+y)%3!=0:
    print(0)
    sys.exit()
else:
    n=(x+y)/3
    n=int(n)
    if x<n or y<n:
         print(0)
         sys.exit()
    else:
        x=x-n
        y=y-n
        ans=int(combinations_count(x+y, min[x,y]))
        print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import sys
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

x,y= (int(_) for _ in input().split()) 
if (x+y)%3!=0:
    print(0)
    sys.exit()
else:
    n=(x+y)/3
    n=int(n)
    if x<n or y<n:
         print(0)
         sys.exit()
    else:
        x=x-n
        y=y-n
        ans=int(combinations_count(x+y, min[x,y])
        print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import subprocess
import os
import time


import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

input = sys.stdin.readline


mod = 10**9+7
N = 10**6
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]


def find_n(x, y):
    moves = int((x+y)/3)
    for n in range(moves+1):
        if n + (moves-n)*2 == x and n*2 + (moves-n) == y:
            return n % mod, (moves-n) % mod


# def cmb(n, r):
#     return math.factorial(n) % mod // ((math.factorial(r) % mod) * (math.factorial(n-r) % mod))


def cmb(n, r):
    if r < 0 or r > n:
        return 0
    r = min(r, n-r)

    return g1[n] * g2[r] * g2[n-r] % mod


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

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

    if (x+y) % 3:
        print(0)
        sys.exit()

    n, m = find_n(x, y)

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

    ans = cmb(n+m, n)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import subprocess
import os
import time


import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

input = sys.stdin.readline


mod = 10**9+7
N = 10**6 + 500000
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]


# def find_n(x, y):
#     moves = int((x+y)/3)
#     for n in range(moves+1):
#         if n + (moves-n)*2 == x and n*2 + (moves-n) == y:
#             return n % mod, (moves-n) % mod


# def cmb(n, r):
#     return math.factorial(n) % mod // ((math.factorial(r) % mod) * (math.factorial(n-r) % mod))


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


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

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

    if (x+y) % 3:
        print(0)
        sys.exit()

    # n, m = find_n(x, y)

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

    ans = cmb(n+m, n)

    print(ans)


if __name__ == '__main__':
    main()