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

X, Y = map(int, input().split())
if (X + Y)%3 != 0:
    print(0)
else:
    A = np.matrix([
        [2, 1],
        [1, 2]
    ])
    B = np.matrix([
        [X],
        [Y]
    ])

    mov = np.linalg.solve(A,B)
    n = mov[0] + mov[1]
    r = mov[0]
    print((math.factorial(n) // (math.factorial(n - r) * math.factorial(r)))%(10**9+7))

Submission status: Runtime Error

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

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

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

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

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

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

Submission status: Runtime Error

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

if (x+y)%3!=0:print(0)
else:
    n,m=y//3,y//3
    p = 10**9+7
    N = 2*10**6+10  # 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)
    print(cmb(n+m,n,p))

Submission status: Runtime Error

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

if (x+y)%3!=0:print(0)
else:
    n,m=y//3,y//3
    p = 10**9+7
    N = 2+10**6+10  # 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)
    print(cmb(n+m,n,p))

Submission status: Runtime Error

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

if (x+y)%3!=0: print(0)
else:
    n,m=y//3,y//3
    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)
    print(cmb(n+m,n,mod))

Submission status: Runtime Error

Solution code:
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())
m  = 10**9+7
if (x+y)%3 == 0:
    left, right = [[2,1],[1,2]], [x,y]
    nl = solve(left, right)
    a, b = nl[0], nl[1]
    print(int(cmb(a+b, a))%m)
else:
    print(0)

Submission status: Runtime Error

Solution code:
from numpy.linalg import solve
import math

x, y = map(int, input().split())
m  = 10**9+7
if (x+y)%3 == 0:
    left, right = [[2,1],[1,2]], [x,y]
    nl = solve(left, right)
    nl.sort()
    print((math.factorial(sum(nl))//(math.factorial(sum(nl)-nl[0]) * math.factorial(nl[0])))%m)
else:
    print(0)

Submission status: Runtime Error

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

mod = 10**9+7

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



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

X,Y = LI()

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

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

Submission status: Runtime Error

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

def tables(mod, n):
  fac = [1, 1] 
  infac = [1, 1] 
  inverse = [0, 1] 
  for i in range(2, n+1):
    fac.append((fac[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod // i)) % mod)
    infac.append((infac[-1] * inverse[-1]) % mod)
  return fac,infac

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

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

move = X + Y

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

Submission status: Runtime Error

Solution code:
import math
from scipy.special import comb

#def permod(n, r):
  #return (math.factorial(n) // math.factorial(n - r)) % (10 ** 9 + 7)

from operator import mul
from functools import reduce

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

def main():
  X,Y = map(int,input().split())
  
  if (X + Y) % 3 != 0:
    print(0)
    
  else:
    a = Y - (X + Y) // 3
    b = X - (X + Y) // 3
    
    ans = com(a + b,b)
    
    print(ans)
    
main()

Submission status: Runtime Error

Solution code:
from functools import reduce
from operator import mul

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

if (X + Y) % 3 != 0:
  print(0)
  
else:
  a = Y - (X + Y) // 3
  b = X - (X + Y) // 3
  total = a + b
  m = min(a,b)
  nums = [i for i in range(m,total + 1)]
  div = [i for i in range(1,m + 1)]
  M = reduce(mul,div)
  N = reduce(mul,nums) * M
  print((N // M) % (10 ** 9 + 7))

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())
if (x+y)%3 == 0 and x<=2*y and y<=2*x:
	a=int((2*y-x)/3)
	b=int((2*x-y)/3)
	print(cmb(a+b, a, mod))
else:
	print(0)

Submission status: Runtime Error

Solution code:

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


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


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


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

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

Submission status: Runtime Error

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

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

mod=10**9+7

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

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

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

Submission status: Runtime Error

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

"""考え方
・(X+Y)が3の倍数でないなら、行けない。（移動量の合計が3なので）
n+2m=X、2n+m=Yという連立方程式が成り立ち、(n+m)C(n)を求めれば良い。
  m = Y-2n。n=X-2m。
  n=X-2(Y-2n)
  n=X-2Y+4n
  3n=2Y-X
  n=(2Y-X)/3
  
  m=Y-2n
  =Y-(4Y-2X)/3
  =(2X-Y)/3
"""

n = (2*Y-X)//3
m = (2*X-Y)//3
mod = 10**9+7

## 組み合わせ数を計算する
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
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


if (X+Y)%3 != 0:
  ans = 0
elif n >= 0 and m >= 0:
  ans = comb(n+m, n, mod)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math

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

if (2 * x - y) % 3 != 0 or (2 * y - x) % 3 != 0:
    print(0)
    sys.exit()

k = (2 * x - y) // 3
l = (2 * y - x) // 3

ans = math.factorial(k + l) // (math.factorial(k) * math.factorial(l))

print(ans % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
from scipy.special import comb

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()[:-1]
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 LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	X,Y = MI()
	N3 = (2*Y-X)
	M3 = (2*X-Y)
	if(N3%3!=0 or M3%3!=0 or N3 < 0 or M3<0):
		print(0)
	else:
		N=N3//3
		M=M3//3

		K = min(N,M)

		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 #出力の制限
		L = 10**6
		g1 = [1, 1] # 元テーブル
		g2 = [1, 1] #逆元テーブル
		inverse = [0, 1] #逆元テーブル計算用テーブル

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

		print(cmb(N+M,K,mod))


main()

Submission status: Runtime Error

Solution code:
from decimal import * 
import math
a,b,x = map(int,input().split())
X = x/a
P = X /(a*b)
if P >= 0.5 :
    print(math.degrees(math.atan((2*b*(1-P)/a))))
else:
    print(math.degrees(math.atan((a*b**2/(2*x)))))

Submission status: Runtime Error

Solution code:
import math

nCr = {}
def cmb(big, small):
    def kaijo(big,small):
        a = math.factorial(small)
        b = math.factorial(big)
        c = math.factorial(big+small)
        return a,b,c
    a,b,c = kaijo(big,small)
    return c//(a*b)
    

x,y = map(int,input().split())
#x=2a+b,y=2b+aの方程式を解く
a=(2*x-y)//3
b=(2*y-x)//3
ans = 0
if (2*x-y)%3==0:
    if (2*y-x)%3==0:
#コンビネーションで全通りを求める
        ans = cmb(a,b)
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
from math import factorial
from scipy.special import comb
x,y = map(int, input().split())

mod = 10**9+7
def inv(x):
        return pow(x, mod-2, mod)
def fact(x):
        f = 1 
        for i in range(1, x + 1): 
                f *= i
                f %= mod    
        return f
def comb(n, r): 
        return (fact(n) * inv(fact(n-r)) * inv(fact(r))) % mod 

if (x + y) % 3 != 0:
    print(0)
else:
    n = (2*y-x)//3
    m = (2*x-y)//3
    res = comb(n+m, m)
    print(res % (10**9+7))

Submission status: Runtime Error

Solution code:
from math import factorial
from scipy.special import comb
x,y = map(int, input().split())

if (x + y) % 3 != 0:
    print(0)
else:
    n = (2*y-x)//3
    m = (2*x-y)//3
    c = comb(n+m, n, exact=True)
    print(c % (10**9+7))

Submission status: Runtime Error

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


dp =[[0] * (y+1) for i in range(x+1)]
dp[0][0] = 0
dp[1][2] = 1
dp[2][1] = 1

for i in range(2,x+1):
    for j in range(2,y+1):
        dp[i][j] = dp[i-1][j-2] % (10**9+7) + dp[i-2][j-1] % (10**9+7)

print(dp[x][y] % (10**9+7))

Submission status: Runtime Error

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

def nCm_mod(A, B, mod):
    mul_one = 1
    mul_two = 1

    for i in range(B):
        mul_one *= A - i
        mul_two *= i + 1
        mul_one %= mod
        mul_two %= mod
    
    return (mul_one * pow(mul_two, mod-2, mod)) % mod

if (x + y) % 3 != 0 or n<0 or n>m:
    print(0)
else:
    n = (2 * y - x) // 3
    m = (2 * x - y) // 3

    comb_num = nCm_mod(n+m, min(n,m), mod)
    print(comb_num)

Submission status: Runtime Error

Solution code:

mod = 10 ** 9 + 7
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inverse = [0, 1] # 逆元テーブル計算用テーブル

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

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

def solve(x, y):
    if (x + y) % 3 != 0:
        return 0
    n = (x + y) // 3
    r = min((2 * y - x) // 3, (2 * x - y) // 3)
    return cmb(n, r, mod)

_x, _y = map(int, input().split())
print(solve(_x, _y))

Submission status: Runtime Error

Solution code:
import sys
import itertools
import math
from operator import mul
from functools import reduce

def propare():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    
    tokens = iterate_tokens()
    X = int(next(tokens))
    Y = int(next(tokens))

    solve(X, Y)

def solve(X: int, Y: int):
    divi_num = 10**9 + 7
    # x  + 2y = X
    # 2x + y  = Y
    if ((X + Y) % 3) == 0:
        y = int((2*X - Y)/3)
        x = int((-1*X +2*Y)/3)
        answer = nCr(x+y, x)
        print(answer%divi_num)
    else:
        print(0)

    return

nCr = {}
def nCr(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)]

if __name__ == "__main__":
    propare()

Submission status: Runtime Error

Solution code:
import sys
import itertools
import math

def propare():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    
    tokens = iterate_tokens()
    X = int(next(tokens))
    Y = int(next(tokens))

    solve(X, Y)

def solve(X: int, Y: int):
    divi_num = 10**9 + 7
    # x represents the number of moves to the x-axis.
    # y represents the number of moves to the y-axis.
    # x + y is the number of moves.
    # 
    # x  + 2y = X
    # 2x + y  = Y
    if ((X + Y) % 3) == 0:
        y = int((2*X - Y)/3)
        x = int((-1*X +2*Y)/3)
        answer = nCr(x+y, x)
        print(answer % divi_num)
    else:
        print(0)

    return

def nCr(n: int, y:int):
    numerator = math.factorial(n)
    denominator = math.factorial(n - y)
    return numerator // denominator

if __name__ == "__main__":
    propare()

Submission status: Runtime Error

Solution code:
import math
x,y = list(map(int, input().split()))
mod = 7 + (10**9)
ans = 0
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
#a/b = a*(b`)となるb`を求める
def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod
if (2 * x - y) % 3 != 0 or (2 * y - x) % 3 != 0:
    print(0)
    exit()
else:
    m = (2*x - y)//3
    n = (2*y - x)//3
    #m+n C m を計算
    #(m+n)! / n! * m!を計算したいが、mod上で割り算できない。
    #逆元を使う
    factorial = [1]*(m+n+1)
    for i in range(1,m+n+1):
        factorial[i] = (factorial[i - 1] * i) % mod
    ans = factorial[m+n] * mod_inv(factorial[m], mod)
    ans %= mod
    ans *= mod_inv(factorial[n], mod)
    ans %= mod
    print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Jan 24 18:55:49 2020
abc145d
@author: manakamura
"""
import sys
import math

tmp = input().split()
x,y = list(map(lambda a: int(a), tmp))

if((x+y)%3!=0):
    print(0)
    sys.exit()
n=(x+y)//3
#r=n+abs(x-y)
r=abs(n-x)
#print(n,r)
print(math.factorial(n) // (math.factorial(n - r) * math.factorial(r)))

Submission status: Runtime Error

Solution code:
import numpy as np
from numpy import linalg as LA

N = int(input())
li = [[1,N]]

for i in range(2,int(np.sqrt(N))+1):
    if N%i == 0:
        li.append([i,N//i])

ans = 10**12
for i in li:
    x,y = i
    tmp = LA.norm([x-1,y-1],1)
    if ans > tmp:
        ans = tmp

print(ans)

Submission status: Runtime Error

Solution code:
X,Y=map(int,input().split())
dp=[[0 for i in range(X+1)] for j in range(Y+1)]
dp[0][0]=1
for x in range(X):
    for y in range(Y):
        if x+1<=X and y+2<=Y:
            dp[x+1][y+2]+=dp[x][y]
        if x+2<=X and y+1<=Y:
            dp[x+2][y+1]+=dp[x][y]
print(dp[X][Y]%(10**9+7))

Submission status: Runtime Error

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

if (x + y) % 3 != 0:
    print(0)
else:
    time = (x + y) // 3
    if time > x or time > y:
        print(0)
    else:
        move_time = sorted([x - time, y - time])
        
        ans = 1
        for i in range(2, time+1):
            ans *= i
            ans %= mod
        
        const = 1
        for i in range(1, move_time[1]+1):
            const *= i
            const %= mod
            
            if i == move_time[0]:
                inv0 = pow(const, mod-2, mod)
            
        inv1 = pow(const, mod-2, mod)
    
        print((ans * inv0 * inv1) % mod)

Submission status: Runtime Error

Solution code:
from scipy.special import comb

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

if not (x + y)%3 == 0:
    print(0)
else :
    if x == 2*y or y == 2*x :
        print(1)
    elif x < 2*y < 4*x :
        m = (x+y)//3
        i = x - m
        c = comb(m,i,exact=True)
        print(  c % (10**9+7) )
    else :
        print(0)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
X, Y = map(int, input().split())
mod = 10 ** 9 + 7
for t in range(X + Y + 1):
  if t == X + Y:
    print(0)
    exit(0)
  if X + Y - 2 * t == t:
    X -= t
    Y -= t
    break
class Factorial:
  def __init__(self, n, mod):
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod
f = Factorial(X + Y, mod)
#print(X, Y)
print(f.combi(X + Y, X))

Submission status: Runtime Error

Solution code:
import math

X, Y = [int(x) for x in input().split(" ")]

N = (X + Y) / 3
i = (2 * X - Y) / 3
if N < 0 or N != int(N):
    print(0)
if i < 0 or i != int(i):
    print(0)

N = int(N)
i = int(i)

ans = math.factorial(N) / (math.factorial(i) * math.factorial(N-i))
print(ans)

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


X, Y = map(int, input().split())
if (X + Y) % 3 == 0:
    p = (2 * Y - X) // 3
    q = (2 * X - Y) // 3
    n = p + q
    r = min(p, q)
    modFacts, invs = prepare(n)
    ans = (modFacts[n] * invs[n - r] * invs[r]) % MOD
else:
    ans = 0

print(ans)

Submission status: Runtime Error

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

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

ab=a+b
ue=[1]*(ab+1)
for i in range(1, ab+1):
  ue[i]=ue[i-1]*i%p
  
out=ue[-1]*pow(ue[a], p-2, p)%p
out=out*pow(ue[b], p-2, p)%p

print(out)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <sstream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <assert.h>
#include <deque>
using namespace std;

typedef unsigned long long UL;
typedef long long LL;
typedef long double LD;
#define LP(i, a, b) for (LL i = int(a); i < int(b); i++)
#define LPE(i, a, b) for (LL i = int(a); i <= int(b); i++)
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<vector<PII> > WAL;
typedef vector<vector<int> > SAL;
#define Ep 1e-8
#define INF 1e9
#define LINF 1e18

LL const MOD = 1e9+7;
LL const MaxSize = 1e6 + 5;
//LL const MOD = 998244353;

/*

#https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d
D - Lucky PIN

Easy problem, but python version gives TLE in the last two cases
 */


LL X, Y;
string S;

//NOTE WORKS ONLY WHEN MOD IS PRIME
LL f[MaxSize], invF[MaxSize], r[MaxSize];

void preCalc() {
        r[1] = 1;
        f[1] = 1;
        invF[1] = 1;
        LL m = MOD;

        for (LL i = 2; i < MaxSize; ++i) {
                r[i] = (m - (m / i) * r[m % i] % m) % m;

                f[i] = (i * f[i - 1]) % MOD;
                invF[i] = (r[i] * invF[i - 1]) % MOD;
        }
}

LL choose(LL top, LL bottom) {
        if (top < bottom || top < 0 || bottom < 0)
                return 0;
        if (top == bottom || bottom == 0)
                return 1;

        LL bfs = (invF[bottom] * invF[top - bottom]) % MOD;

        //      cout << "ftop:" << top << " " << f[top] << endl;

        return (f[top] * bfs) % MOD;
}

int main() {
        ios_base::sync_with_stdio(false);
        //freopen("/Users/georgeli/A_1.in", "r", stdin);

        cin >> X >> Y;

        if ((X + Y) % 3){
        	cout << 0;
        	return 0;
        }

        LL ts  = (X + Y) / 3;
        LL delta = abs(X - Y);
        LL upSteps = (ts + delta)/ 2;

        preCalc();
        cout << choose(ts, upSteps);


        return 0;
}

Submission status: Runtime Error

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


def num_combinations_mod(n, r, mod, num_max=10**6):
    # if this functions is called twice or more, init process should be placed before calling this function to
    # save time.
    f_mod, f_mod_inv = num_combinations_mod_init(num_max, mod)
    return f_mod[n] * (f_mod_inv[r] * f_mod_inv[n-r] % mod) % mod


def num_combinations_mod_init(num_max, mod):
    factorials_mod = dict()
    factorials_mod_inv = dict()
    factorials_mod[0] = 1
    factorials_mod[1] = 1
    factorials_mod_inv[0] = 1
    factorials_mod_inv[1] = 1
    mod_inv = dict()
    mod_inv[1] = 1
    for i in range(2, num_max):
        factorials_mod[i] = factorials_mod[i - 1] * i % mod
        mod_inv[i] = mod - mod_inv[mod % i] * (mod // i) % mod
        factorials_mod_inv[i] = factorials_mod_inv[i - 1] * mod_inv[i] % mod
    return factorials_mod, factorials_mod_inv


def get(num1, num2):
    if num1 > num2:
        num = num2
    else:
        num = num1
    return num_combinations_mod(num1+num2, num, 10**9+7)


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

total = (X + Y) // 3
n_moveB = (2 * X - Y) // 3
n_moveA = total - n_moveB
answer = get(n_moveA, n_moveB)

print(answer)

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7


def comb(n, k):
    N = n + k + 1
    fact = [1] * (N + 1)
    rfact = [1] * (N + 1)
    r = 1
    for i in range(1, N + 1):
        fact[i] = r = r * i % MOD

    rfact[N] = r = pow(fact[N], MOD - 2, MOD)
    for i in range(N, 0, -1):
        rfact[i - 1] = r = r * i % MOD
    return fact[n] * rfact[k] * rfact[n - k] % MOD


X, Y = map(int, input().split())
x = 2 * X - Y
y = 2 * Y - X

if x % 3 and y % 3:
    print(0)
else:
    xx = x // 3
    yy = y // 3
    print(comb(xx + yy, xx))

Submission status: Runtime Error

Solution code:
m = 10**9 + 7
X, Y = map(int, input().split())
t = [[0] * (X + 2) for i in range(Y + 2)]
for i in range(Y):
    for j in range(X):
        t[i + 1][j + 2] += t[i][j] + 1
        t[i + 2][j + 1] += t[i][j] + 1
        t[i + 1][j + 2] %= m
        t[i + 2][j + 1] %= m

print(t[Y - 1][X - 1])

Submission status: Runtime Error

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

MOD = int(1.0e+9 + 7)
DP_max = 3333334

DP = []
if(2 * y - x) % 3 != 0 or (2 * x - y) % 3 != 0:
    print(0)

if(2 * y - x) < 0 or (2 * x - y) < 0:
    print(0)

X = int((2 * y - x) / 3)
Y = int((2 * x - y) / 3)

for i in range(X + 1):
    DP.append([1])

for i in range(Y + 1):
    DP[0].append(1)


for i in range(1, X + 1):
    for j in range(1, Y + 1):
        DP[i].append((DP[i][j - 1] + DP[i - 1][j]) % MOD)

print(DP[X][Y])

Submission status: Runtime Error

Solution code:
x,y=list(map(int, input().split()))
k=pow(10,9)+7
def solve(x,y):
  if x<0 or y<0:
    return 0
  elif x==0 and y==0:
    return 1
  else:
    return solve(x-1,y-2)+solve(x-2,y-1)
print(solve(x,y)%k)

Submission status: Runtime Error

Solution code:
import math

[X, Y] = list(map(int, input().split()))
if (X + Y) % 3 == 0:
  #(i+1, i+2)に行く回数をa、(i+2, i+1)に行く回数をbとすると
  a = (2 * Y - X) / 3
  b = (2 * X - Y) / 3
  if a > 0 and b > 0:
    path = a + b
    num = math.factorial(path) // math.factorial(a)
    ans = int(num % (10 ** 9 + 7))
else:
  ans == 0
print(ans)

Submission status: Runtime Error

Solution code:
import math

[X, Y] = list(map(int, input().split()))
if (X + Y) % 3 == 0:
  #(i+1, i+2)に行く回数をa、(i+2, i+1)に行く回数をbとすると
  a = (2 * Y - X) / 3
  b = (2 * X - Y) / 3
  if a > 0 and b > 0:
    path = a + b
    num = math.factorial(path) / math.factorial(a)
    ans = int(num % (10 ** 9 + 7))
else:
  ans == 0
print(ans)

Submission status: Runtime Error

Solution code:
import math

[X, Y] = list(map(int, input().split()))
#(i+1, i+2)に行く回数をa、(i+2, i+1)に行く回数をbとすると
#a = (2 * Y - X) / 3
#b = (2 * X - Y) / 3

a = 2 * Y - X
b = 2 * X - Y

if a % 3 == 0 and b % 3 == 0:
  path = (a + b) / 3
  a_path = a / 3
  num = math.factorial(path) / math.factorial(a_path)
  ans = int(num % (10 ** 9 + 7))
else:
  ans == 0
print(ans)

Submission status: Runtime Error

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


count = 0

def dfs(x,y):
    global count
    if x==X and y==Y:
        count = count + 1
        return
    if x<0 or y<0 or x>=X or y>=Y:
        return
    
    dfs(x+1, y+2)
    dfs(x+2, y+1)

    return

dfs(0,0)
print(count%(10**9+7))

Submission status: Runtime Error

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


count = 0

def dfs(x,y):
    global count
    if x==X and y==Y:
        count = count + 1
        return
    if x<0 or y<0 or x>=X or y>=Y:
        return
    
    dfs(x+1, y+2)
    dfs(x+2, y+1)

    return

dfs(0,0)
print(count)

Submission status: Runtime Error

Solution code:
X, Y = map(int,input().split())
def combination(n,r,mod=10**9+7):
    n1 = n+1
    r = min(r,n-r)
    numer = denom = 1
    for i in range(1,r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom,mod-2,mod) % mod

#y=2x以下かつy=(1/2)x以上の位置にいなくてはいけない
if (X+Y) % 3 != 0 or not (X<=2*y and Y <=2*X):
    ans = 0
else:
    N = (X+Y)//3
    r = Y - N
    ans = combination(N,r)
print(ans)

Submission status: Runtime Error

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

ax = []
while n != 0:
    ax = [n % 2] + ax[:]
    n //= 2
S = 0
if (2 * X - Y) % 3 != 0 or (-X + 2 * Y) % 3 != 0:
    S = 0
else:
    A = [1]
    for i in range(x+y):
        A.append(((i + 1) * A[i]) % mod)
    inv = [1, 1]
    for i in range(len(ax)):
        if ax[i] == 1:
            inv[0] *= A[x]
            inv[1] *= A[y]
            inv[0] %= mod
            inv[1] %= mod
        if i != len(ax) - 1:
            inv[0] *= inv[0] % mod
            inv[0] %= mod
            inv[1] *= inv[1] % mod
            inv[1] %= mod
    S = (inv[0] * inv[1] * A[x+y]) % mod
print(S)

Submission status: Runtime Error

Solution code:
import sys
import itertools
import bisect
import math
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

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

Submission status: Runtime Error

Solution code:
import math
X, Y = map(int,input().split())
n = (2*Y-X)//3
m = (2*X-Y)//3
if n < 0 or m < 0:
  print(0)
else:
  print((math.factorial(n+m)/(math.factorial(n)*math.factorial(m)))%(10**9+7))

Submission status: Runtime Error

Solution code:
import math
a = input().split()
x = int(a[0])
y = int(a[1])

ans = 0
m = (2*x-y)/3
n = (2*y-x)/3
if (x+y)%3 != 0:
    ans = 0
elif m<0 or n<0:
    ans = 0
else:
    ans = (math.factorial(m+n)/math.factorial(m)/math.factorial(n)) % (pow(10,9)+7)
print(int(ans))

Submission status: Runtime Error

Solution code:
from functools import reduce
X, Y = map(int, input().split())
if (2*X-Y) < 0 or (2*Y-X) < 0:
    print(0)
    exit()
if (2*X-Y)%3 != 0 or (2*Y-X)%3 != 0:
    print(0)
    exit()
a = int((2*X-Y)/3)
b = int((2*Y-X)/3)
total = a+b
def Fac(n,m):
    mul = lambda a, b: a*b
    if n == 1 or n == 0:
        return 1
    else:
        return reduce(mul,range(n-m+1,n+1))
x = min(a,b)
route = Fac(total,x)/Fac(x,x)
print(int(route)%(10**9+7))

Submission status: Runtime Error

Solution code:
from functools import reduce
X, Y = map(int, input().split())
if (2*X-Y) < 0 or (2*Y-X) < 0:
    print(0)
    exit()
if (2*X-Y)%3 != 0 or (2*Y-X)%3 != 0:
    print(0)
    exit()
a = int((2*X-Y)/3)
b = int((2*Y-X)/3)
total = a+b
def Fac(n,m):
    mul = lambda a, b: a*b
    if n == 1 or n == 0:
        return 1
    else:
        return reduce(mul,range(n-m+1,n+1))
route = Fac(total,a)/Fac(a,a)
print(int(route)%(10**9+7))

Submission status: Runtime Error

Solution code:
INF = float("inf") #const
MOD = 10**9+7 #const
MAX = 510000 #const

def repeat(n,p):
    if p == 0:
        return 1
    if p%2==0:
        t = repeat(n,p//2)
        return t * t % MOD
    return n * repeat(n,p-1) % MOD


def com(n,r):
    if n < r or n < 0:
        return 0
    if n == 0 and r == 0:
        return 1
    fact = [0] * (n+1)
    fact[0] = 1
    for i in range(n):
        fact[i+1] = fact[i] * (i+1) % MOD #階乗計算
    f_inv = repeat(fact[r],MOD-2)
    f = repeat(fact[n-r],MOD-2)

    return fact[n] * f_inv * f % MOD


def main():
    x,y = map(int,input().split())
    if (x+y)%3 != 0:
        print(0)
        return
    n = (2*y - x)//3
    m = (2*x - y)//3
    print(com(n+m,n))


if __name__ == "__main__":
    main()