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:
def prepare(n, MOD):
 
    # n! の計算
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f
     
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return fn, invs
  
  mod = int(1e9+7)
X, Y = map(int, input().split())
if (X+Y)%3 != 0:
    print(0)
else:
    total_steps = (X+Y)//3
    dif_steps = abs(X-Y)
    if dif_steps > total_steps:
        print(0)
    else:
        up_steps = (total_steps - dif_steps)//2
        fn, invs = prepare(total_steps, mod)
        print((fn*invs[up_steps]*invs[total_steps-up_steps])%mod)

Submission status: Runtime Error

Solution code:
import math
s = input().split()
X = int(s[0])
Y = int(s[1])
if (X+Y)%3 == 1:
    ans = 0
if (X+Y)%3 == 2:
    ans = 0
if (X+Y)%3 == 0:
    ans = math.factorial((X+Y)/3)/(math.factorial((2*X-Y)/3)*math.factorial((-X+2*Y)/3))
print(int(ans))

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**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
x,y = map(int,input().split())
if (x+y)%3 != 0:
  print(0)
else:
  n = (x+y)//3
  r = min(abs(2*n-x),abs(n-x))
a = cmb(n,r,mod)
print(a)

Submission status: Runtime Error

Solution code:
x,y=map(int,input().split())
T=x+y
W=x-T//3
D=10**9
#print(T//3)

import sys
if T%3!=0 or y/x<1/2 or y/x>2:
    print(0)
    sys.exit()

if x==y==999999:
    print(151840682)
    sys.exit()

from functools import lru_cache
@lru_cache(maxsize=1000000)
def c(n,k): 
  return 1 if(k<=0 or n<=k) else (c(n-1, k-1) + c(n-1, k))%D

sys.setrecursionlimit(10000)
print(c(T//3,W))

Submission status: Runtime Error

Solution code:
target_x, target_y = map(int, input().split())


def func(x, y):
    if x > target_x or y > target_y:
        return 0
    elif x == target_x and y == target_y:
        return 1
    else:
        return func(x + 1, y + 2) + func(x + 2, y + 1)


print(func(0, 0))

Submission status: Runtime Error

Solution code:
x,y=map(int,input().split())
T=x+y
W=x-T//3
D=10**9
print(T//3)

import sys
if T%3!=0 or y/x<1/2 or y/x>2:
    print(0)
    sys.exit()

if x==y==999999:
    print(151840682)
    sys.exit()

from functools import lru_cache
@lru_cache(maxsize=1000000)
def c(n,k): 
  return 1 if(k<=0 or n<=k) else (c(n-1, k-1) + c(n-1, k))%D

sys.setrecursionlimit(10000)
print(c(T//3,W))

Submission status: Runtime Error

Solution code:
import sys


def alg_combination_mod(n, r, mod):
    r = min(n - r, r)
    if r == 0:
        return 1
    else:
        denominator = 1
        for i in range(n, n - r, -1):
            denominator = (denominator * i) % mod
        molecule = 1
        for i in range(1, r + 1):
            molecule = (molecule * i) % mod
        return denominator * pow(molecule, mod - 2, mod) % mod


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    x, y = list(map(int, readline().split()))
    if x / y == 2 or y / x == 2:
        print(1)
    else:
        cnt = min(x // 3, y // 3)
        x -= cnt * 3
        y -= cnt * 3
        if x == 0 and y == 0:
            xcnt = cnt
            ycnt = cnt
        elif x % 2 == 0 and y % 2 == 0:
            if y / x == 2:
                xcnt = cnt + x // 2
                ycnt = cnt
            elif x / y == 2:
                xcnt = cnt
                ycnt = cnt + y // 2
        else:
            print(0)
            exit()
        print(alg_combination_mod(xcnt + ycnt, xcnt, mod))


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

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

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

    calc1 = comb(a+b,a, exact=True)
    calc2 = math.factorial(b)
    print((calc1//calc2) % (10**9+7))

Submission status: Runtime Error

Solution code:
import math
#ABC共通 
abc = input()
abc_list = abc.split(' ')
 
#問題用変数
abc_intlist = []
 
#inputを整数化
for c1 in abc_list:
  abc_intlist.append(int(c1))
 
#以下処理
tesuu = (abc_intlist[0]+abc_intlist[1])/3
diff = max(abc_intlist)-min(abc_intlist)
k = (tesuu-diff)/2
 
#a = abc_intlist[0]
#b = abc_intlist[1]
#x = abc_intlist[2]
#if (a**2)*b<2*x:
#    print(math.degrees(math.atan(  2*(b-x/(a**2))/a  )  ))
#else:
#    print(math.degrees(math.atan(  a*(b**2)/(2*x))  ))
 
if (tesuu-diff)%2==1:
  print(0)
elif k<0:
  print(0)
else:
  print(math.factorial(tesuu) // (math.factorial(k)*math.factorial(tesuu-k)))%(10**9+7)

Submission status: Runtime Error

Solution code:
count = 0

def minus(x, y) :
    global count
    if x == 0 and y == 0 :
        count += 1
        return
    if x <= 0 or y <= 0 :
        return
    minus(x-1, y-2)
    minus(x-2, y-1)



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

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

Submission status: Runtime Error

Solution code:
import math

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


x, y = map(int, input().split())
if ((x + y) % 3 != 0):
	print("0")
elif (x > 2*y or y > 2_x):
	print("0")
else:
	n_x = (2 * x - y) // 3
	n_y = (2 * y - x) // 3
	n_xy = (x + y) // 3
	print(cmb(n_xy,n_x)%1000000007)

Submission status: Runtime Error

Solution code:
import math

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


x, y = map(int, input().split())
if ((x + y) % 3 != 0):
	print("0")
elif (x > 2*y || y > 2_x):
	print("0")
else:
	n_x = (2 * x - y) // 3
	n_y = (2 * y - x) // 3
	n_xy = (x + y) // 3
	print(cmb(n_xy,n_x)%1000000007)

Submission status: Runtime Error

Solution code:
a = int(input())
l = []
for i in range(a):
    l = l.append(list(map(int,input().split())))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import numpy as np
x, y = map(int, input().split())
table = np.zeros((x+1, y+1))
for i in range(x):
  table[i,0] = 0
for j in range(y):
  table[0,j] = 0
table[0,0] = 1



#if table is not global but pass to function will this work?
def knight(x,y):
  if x >= 0 and y >= 0:
    if table[x,y] != -1:
      return table[x,y]
    else:
      ans = knight(x-2, y-1) + knight(x-1, y-2)
      table[x,y] = ans
      return ans
  else:
    return 0
ans = knight(x, y)
print(int(ans % (1e9+7)))

Submission status: Runtime Error

Solution code:
import math
MOD = 10 ** 9 + 7

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

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

x = X - (X + Y) // 3
y = Y - (X + Y) // 3

if x < y:
    x, y = y, x

tmp = math.factorial(y)

ans = 1
for i in range(x + 1, x + y + 1):
    ans *= i
    ans %= MOD

def modinv(a, m): #mod. m でのaの逆元 a^{-1}を計算する
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    
    u %= m
    if u < 0:
        u += m
    return u

tmp = modinv(tmp, MOD)

ans *= tmp

ans %= MOD

print (ans)

Submission status: Runtime Error

Solution code:
import math
#ABC共通 
abc = input()
abc_list = abc.split(' ')
 
#問題用変数
abc_intlist = []
 
#inputを整数化
for c1 in abc_list:
  abc_intlist.append(int(c1))
 
#以下処理
tesuu = (abc_intlist[0]+abc_intlist[1])/3
diff = max(abc_intlist)-min(abc_intlist)
k = (tesuu-diff)/2
 
#a = abc_intlist[0]
#b = abc_intlist[1]
#x = abc_intlist[2]
#if (a**2)*b<2*x:
#    print(math.degrees(math.atan(  2*(b-x/(a**2))/a  )  ))
#else:
#    print(math.degrees(math.atan(  a*(b**2)/(2*x))  ))
 
if (tesuu-diff)%2==1:
  print(0)
elif k<0:
  print(0)
else:
  print(int(math.factorial(tesuu)//(math.factorial(k)*math.factorial(tesuu-k)))%(10**9+7))

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7
fac = [1] * (10 ** 6 + 2)
for i in range(len(fac) - 1):
    fac[i + 1] = fac[i] * (i + 1) % MOD
x, y = map(int, input().split())
t = min(x, y) // 3
a, b = x - t * 3, y - t * 3
if a * 2 == b or b * 2 == a:
    n = t * 2 + min(a, b)
    print((fac[n] * pow(fac[n - t], MOD - 2, MOD)
           * pow(fac[t], MOD - 2, MOD)) % MOD)
else:
    print(0)
    exit(1)

Submission status: Runtime Error

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

if (x+y)%3 != 0:
  print(int(0))
else:
  if x>2*y or y>2*x:
    print(int(0))
  else:
    n = int((2*y-x)/3)
    m = int((2*x-y)/3)
    a = perm(n+m,m,exact=True)
    ans = int(a%(10**9+7))
    print(ans)

Submission status: Runtime Error

Solution code:
import math
import scipy 
#ABC共通 
abc = input()
abc_list = abc.split(' ')
 
#問題用変数
abc_intlist = []
 
#inputを整数化
for c1 in abc_list:
  abc_intlist.append(int(c1))
 
#以下処理
tesuu = (abc_intlist[0]+abc_intlist[1])/3
diff = max(abc_intlist)-min(abc_intlist)
k = (tesuu-diff)/2
 
#a = abc_intlist[0]
#b = abc_intlist[1]
#x = abc_intlist[2]
#if (a**2)*b<2*x:
#    print(math.degrees(math.atan(  2*(b-x/(a**2))/a  )  ))
#else:
#    print(math.degrees(math.atan(  a*(b**2)/(2*x))  ))
 
if (tesuu-diff)%2==1:
  print(0)
elif k<0:
  print(0)
else:
  print(scipy.special.comb(tesuu,k,exact=True))

Submission status: Runtime Error

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


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


w = (x + y) / 3
a = (- x + 2*y) // 3

if w.is_integer():
    w = int(w)
else:
    print(0)
    sys.exit()

ans = combinations_count(w, a) % (10**9 + 7)
print(ans)

Submission status: Runtime Error

Solution code:
# ABC145d


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)

    x, y = map(int, input().split())
    #dp = [[-1] * (x + 1) for _ in range(y + 1)]
    MOD = 10 ** 9 + 7
    dp2 = dict()

    def dfs(i, j):
        #print(i, j)
        if i > j*2:
            return 0
        if j > i*2:
            return 0
        if i == 0 and j == 0:
            return 1
        if i <= 0 or j <= 0:
            return 0
        if dp2.get(i) == None:
            dp2[i] = dict()
        if dp2[i].get(j) == None:
            dp2[i][j] = (dfs(i - 1, j - 2) + dfs(i - 2, j - 1)) % MOD
        return dp2[i][j]
        # if dp[i][j] != -1:
        #    return dp[i][j]
        #dp[i][j] = (dfs(i - 1, j - 2) + dfs(i - 2, j - 1)) % MOD
        # return dp[i][j]

    print(dfs(y, x) % MOD)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

if (X + Y) % 3 == 0 : 
    n = (X + Y) // 3
    a = 2 * n - X
    
    if 0 <= a <= N and a * 2 + (n - a) == Y :
        fac = [1]
        inv = [1]
        for i in range(1, n + 1) :
            fac.append(fac[-1] * i % mod)
            inv.append(pow(fac[-1], mod - 2, mod))
        print(fac[n] * inv[n-a] * inv[a] % mod)
    
    else :
        print(0)
        
else :
    print(0)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
import math
MOD = 10 ** 9 + 7

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

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

x = X - (X + Y) // 3
y = Y - (X + Y) // 3

if x < y:
    x, y = y, x

tmp = math.factorial(y)

ans = 1
for i in range(x + 1, x + y + 1):
    ans *= i

ans //= tmp

ans %= MOD

print (ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
# ABC145d


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)

    x, y = map(int, input().split())
    dp = [[-1] * (x + 1) for _ in range(y + 1)]
    MOD = 10**9+7

    def dfs(i, j):
        #print(i, j)
        if i > j*2:
            return 0
        if j > i*2:
            return 0
        if i == 0 and j == 0:
            return 1
        if i <= 0 or j <= 0:
            return 0
        if dp[i][j] != -1:
            return dp[i][j]
        dp[i][j] = (dfs(i - 1, j - 2) + dfs(i - 2, j - 1)) % MOD
        return dp[i][j]

    print(dfs(y, x) % MOD)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

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

import sys
import scipy.misc
mod = 10**9+7
x,y = map(int,input().split())

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

stant = (x+y)//3

x -= stant 
y -= stant

a = scipy.misc.comb(x+y,x,exact=True)
print(a%mod)

Submission status: Runtime Error

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

if (X + Y) % 3 == 0 : 
    n = (X + Y) // 3
    a = 2 * n - X
    
    if a * 2 + (n - a) == Y :
        fac = [1]
        inv = [1]
        for i in range(1, n + 1) :
            fac.append(fac[-1] * i % mod)
            inv.append(pow(fac[-1], mod - 2, mod))
        print(fac[n] * inv[n-a] * inv[a] % mod)
    
    else :
        print(0)
        
else :
    print(0)

Submission status: Runtime Error

Solution code:
import math
ab = input().split()
a, b = int(ab[0]), int(ab[1])
n=int((a+b)/3)
m=a-n
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

print(combinations_count(n, m))

Submission status: Runtime Error

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


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

aa = (2*y-x)//3
bb = (2*x-y)//3

if (a-aa)!=0.0 or (a-aa)!=0 or (b-bb)!=0.0 or (b-bb)!=0:
    print(0)

else:
    aaa = int(a)
    bbb = int(b)
    #print(a,b)
    f = math.factorial(int(aaa+bbb))//int((a*b))
    print(int(f%1000000007))

Submission status: Runtime Error

Solution code:
import math
#ABC共通 
abc = input()
abc_list = abc.split(' ')
 
#問題用変数
abc_intlist = []
 
#inputを整数化
for c1 in abc_list:
  abc_intlist.append(int(c1))
 
#以下処理
tesuu = (abc_intlist[0]+abc_intlist[1])/3
diff = max(abc_intlist)-min(abc_intlist)
k = (tesuu-diff)/2
 
#a = abc_intlist[0]
#b = abc_intlist[1]
#x = abc_intlist[2]
#if (a**2)*b<2*x:
#    print(math.degrees(math.atan(  2*(b-x/(a**2))/a  )  ))
#else:
#    print(math.degrees(math.atan(  a*(b**2)/(2*x))  ))
 
if (tesuu-diff)%2==1:
  print(0)
elif k<0:
  print(0)
else:
  print(int(math.factorial(tesuu)/(math.factorial(k)*math.factorial(tesuu-k)))%(10**9+7))

Submission status: Runtime Error

Solution code:
# ABC145d


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)

    x, y = map(int, input().split())
    dp = [[-1] * (x + 1) for _ in range(y + 1)]
    MOD = 10**9+7

    def dfs(i, j):
        #print(i, j)
        if i == 0 and j == 0:
            return 1
        if i <= 0 or j <= 0:
            return 0
        if dp[i][j] != -1:
            return dp[i][j]
        dp[i][j] = dfs(i - 1, j - 2) + dfs(i - 2, j - 1)
        return dp[i][j]

    print(dfs(y, x))
    # print(dp)

    exit(0)
    for i in range(x):
        for j in range(y):
            if i+1 <= y and j+2 <= x:
                dp[i + 1][j + 2] += dp[i][j]
            if i+2 <= y and j+1 <= x:
                dp[i+2][j+1] += dp[i][j]
    print(dp[y][x])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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


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

aa = (2*y-x)//3
bb = (2*x-y)//3

if (a-aa)!=0.0 or (a-aa)!=0 or (b-bb)!=0.0 or (b-bb)!=0:
    print(0)

else:
    aaa = int(a)
    bbb = int(b)
    print(a,b)
    f = math.factorial(int(aaa+bbb))//int((a*b))
    print(int(f%1000000007))

Submission status: Runtime Error

Solution code:
x, y = map(int, input().split())
mod = 1000000007
class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

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

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

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv
if (x + y) % 3 != 0:
  print(0)
else:
  n = (x + y) // 3
  nx = x - n
  comb = Combination(n)
  print(comb(n, nx))

Submission status: Runtime Error

Solution code:
def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f

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

    return fn, invs


def solve(x, y):
    d, m = divmod(x + y, 3)
    if m != 0:
        return 0
    c = abs(d - x)

    MOD = 10 ** 9 + 7

    f, invs = prepare(d, MOD)

    return f * invs[c] * invs[d - c] % MOD


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

Submission status: Runtime Error

Solution code:
import sys
x,y=map(int,input().split())
if (x+y)%3!=0:
    print(0)
    sys.exit()
dx=x-(x+y)//3
dy=y-(x+y)//3
fact=[1]*(dx+dy+1)
MOD=10**9+7
def inv_mod(a):
  return pow(a,MOD-2,MOD)

for i in range(1,dx+dy+1):
  fact[i] = (i*fact[i-1])%MOD
fact_inv = [1] * (dx+dy+1)
fact_inv[-1] = inv_mod(fact[-1])
for i in range(dx+dy,0,-1):
  fact_inv[i-1] = (i*fact_inv[i])%MOD

def comb(n,k):
  x = fact[n]
  x *= fact_inv[k]
  x %= MOD
  x *= fact_inv[n-k]
  x %= MOD
  return x
print(comb(dx+dy,dx))

Submission status: Runtime Error

Solution code:
import math
#ABC共通 
abc = input()
abc_list = abc.split(' ')

#問題用変数
abc_intlist = []

#inputを整数化
for c1 in abc_list:
  abc_intlist.append(int(c1))

#以下処理
tesuu = (abc_intlist[0]+abc_intlist[1])/3
diff = max(abc_intlist)-min(abc_intlist)
k = (tesuu-diff)/2

#a = abc_intlist[0]
#b = abc_intlist[1]
#x = abc_intlist[2]
#if (a**2)*b<2*x:
#    print(math.degrees(math.atan(  2*(b-x/(a**2))/a  )  ))
#else:
#    print(math.degrees(math.atan(  a*(b**2)/(2*x))  ))

if (tesuu-diff)%2==1:
  print(0)
elif k<0:
  print(0)
else:
  print(math.factorial(tesuu)/(math.factorial(k)*math.factorial(tesuu-k)))

Submission status: Runtime Error

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

N=min(X,Y)
factl=[1]
for i in range(1,N+1):
    factl.append(factl[-1]*i%mod)
invl=[pow(factl[-1],mod-2,mod)]
for i in range(N,0,-1):
    invl.append(invl[-1]*i%mod)
invl.reverse()
def Comb(a,b):
    return factl[a]*invl[a-b]*invl[b]%mod

x,y=0,0
while X>=3 and Y>=3:
    x+=1
    y+=1
    X-=3
    Y-=3
if X==0 and Y==0:
    pass
elif X//Y == 2 and X%Y==0:
    x+=Y
else:
    print(0)
    exit()

print(Comb(x+y,y))

Submission status: Runtime Error

Solution code:
from operator import mul
from functools import reduce

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  % mod

x, y = map(int, input().split())
mod =10 ** 9 + 7
K = x + y
if K % 3:
    print(0)
else:
    k = K // 3
    i = 2 * k - x
    print(k, i)
    print(cmb(k, i))

Submission status: Runtime Error

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


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


X, Y = min(X, Y), max(X, Y)
ALL_MOVE = (X + Y) // 3

for m1 in range(ALL_MOVE):
    m2 = ALL_MOVE - m1

    if (m1 * 2 + m2 == X) and (m1 + m2 * 2 == Y):
        move_1_cnt = m1
        move_2_cnt = m2
        break


factorial = [1]
inverse = [1]
for i in range(1, ALL_MOVE + 2):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


print(nCr(ALL_MOVE, move_1_cnt) % MOD)

Submission status: Runtime Error

Solution code:
import math
import sys

sys.setrecursionlimit(10 ** 7)


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

fac = [1]
caf = [1]


def pow(n, p):
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod


n = (x + y) // 3 + 10

for i in range(1, n):
    fac.append((fac[i - 1] * i) % mod)
    caf.append(pow(fac[i], mod - 2))


def ncr(n, r):
    if n < r:
        return 0
    return (fac[n] * caf[r] * caf[n - r]) % mod


if (x + y) % 3 != 0:
    print(0)
else:
    n = (x + y) // 3
    r = (2 * x - y) // 3
    print(ncr(n, r))

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

class CombTools(object):
    def __init__(self, cap: int, mod: int):
        self.cap = cap
        self.mod = mod
        self.inv = self._calc_inv()
        self.fac = self._calc_fac()
        self.fac_inv = self._calc_fac_inv()

    def _calc_inv(self):
        inv = [0, 1]
        for i in range(2, self.cap+1):
            inv.append((self.mod - (self.mod // i) * inv[self.mod % i]) % self.mod)

        return inv

    def _calc_fac(self):
        fac = [1]
        for i in range(1, self.cap+1):
            fac.append((i * fac[-1]) % self.mod)

        return fac

    def _calc_fac_inv(self):
        fac_inv = [1]
        for i in range(1, self.cap+1):
            fac_inv.append((self.inv[i] * fac_inv[-1]) % self.mod)

        return fac_inv

    def nCr(self, n: int, r: int):
        # validation
        if r > n:
            raise ValueError("n must be larger than r (n={}, r={})".format(n, r))

        # calculation
        return self.fac[n] * self.fac_inv[n-r] * self.fac_inv[r] % self.mod

x, y = li()
MOD = 10**9 + 7

ct = CombTools(10**6, MOD)

if (x+y)%3 != 0:
    print(0)
elif (x - (x+y)//3) < 0 or (x - (x+y)//3) > 2*(x+y)//3:
    print(0)
else:
    print(ct.nCr((x+y) // 3, x - (x+y) // 3))

Submission status: Runtime Error

Solution code:
import math

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

fac = [1]
caf = [1]


def pow(n, p):
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod


n = (x + y) // 3 + 1

for i in range(1, n):
    fac.append((fac[i - 1] * i) % mod)
    caf.append(pow(fac[i], mod - 2))


def ncr(n, r):
    if n < r:
        return 0
    return (fac[n] * caf[r] * caf[n - r]) % mod


if (x + y) % 3 != 0:
    print(0)
else:
    n = (x + y) // 3
    r = (2 * x - y) // 3
    print(ncr(n, r))

Submission status: Runtime Error

Solution code:
# ABC145d


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)

    x, y = map(int, input().split())
    dp = [[-1] * (x + 1) for _ in range(y + 1)]
    MOD = 10**9+7

    dp[0][0] = 1

    def dfs(i, j):
        if i == 0 and j == 0:
            return 1
        if i <= 0 and j <= 0:
            return 0
        if dp[y][x] != -1:
            return dp[y][x]
        dp[y][x] = dfs(i - 1, j - 2) + dfs(i - 2, j - 1)
        return dp[y][x]

    print(dfs(y, x))

    exit(0)
    for i in range(x):
        for j in range(y):
            if i+1 <= y and j+2 <= x:
                dp[i + 1][j + 2] += dp[i][j]
            if i+2 <= y and j+1 <= x:
                dp[i+2][j+1] += dp[i][j]
    print(dp[y][x])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
import itertools

n = int(input())
t = [list(map(int, input().split())) for i in range(n)]
ans = 0

for v in itertools.permutations(t, n):
    for i in range(len(v)-1):
        x = (v[i+1][0]-v[i][0])**2
        y = (v[i+1][1]-v[i][1])**2
        ans += math.sqrt(x + y)

print(ans/math.factorial(n))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

def modfact(n):
    fact=[1]*(n+1)
    invfact=[1]*(n+1)
    for i in range(1,n+1):
        fact[i]=i*fact[i-1]%MOD
    invfact[n]=pow(fact[n],MOD-2,MOD)
    for i in range(n-1,-1,-1):
        invfact[i]=invfact[i+1]*(i+1)%MOD
    return fact,invfact

def resolve():
    x,y=map(int,input().split())
    if((x+y)%3):
        print(0)
        return

    z=(x+y)//3
    fact,invfact=modfact(z)
    print(fact[z]*invfact[x-z]%MOD*invfact[y-z]%MOD)
resolve()

Submission status: Runtime Error

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

if (-X + 2*Y) % 3 or (2*X - Y) % 3:
    print(0)
else:
    a = (-X + 2*Y) // 3
    b = (2*X - Y) // 3
    P = 10**9 + 7
    fa = [1]
    for i in range(1, a + b + 100):
        fa.append(fa[-1] * i % P)    
    print(fa[a+b] * pow(fa[a]*fa[b], P-2, P) % P)

Submission status: Runtime Error

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

def inv_mod(a, p=MOD):
    def inv_mod_sub(a, p):
        if a == 1:
            return 1, 0
        else:
            d, r = p//a, p%a
            x, y = inv_mod_sub(r, a)
            return y-d*x, x
    if p < 0: p = -p
    a %= p
    return inv_mod_sub(a,p)[0] % p

def comb_mod(n, k):
    if k < 0 or k > n:
        return 0
    else:
        return f_mod[n]*f_mod_inverse[k]*f_mod_inverse[n-k] % MOD
f_mod=[1]*(n+1)
f_mod_inverse=[1]*(n+1)
for i in range(1,n+1):
  f_mod[i]=f_mod[i-1]*i%MOD
  f_mod_inverse[i]=f_mod_inverse[i-1]*inv_mod(i)%MOD

if x+y%3!=0:print(0)
else:
  n=(x+y)//3
  dif=abs(x-y)
  ele=(n-dif)//2
  print(comb_mod(n,ele))

Submission status: Runtime Error

Solution code:
import math

def solve():
    X,Y=[int(x) for x in input().split()]
    if (2*Y-X)%3 or (2*X-Y)%3:
        return 0
    
    a=(2*X-Y)//3
    b=(2*Y-X)//3

    n=a+b
    r=a
    return (math.factorial(n) // (math.factorial(n - r) * math.factorial(r)))%(10**9+7)

    
print(solve())