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())
mod = 10**9 + 7

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

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

Submission status: Runtime Error

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def mod_cmb(n: int, k: int, p: int) -> int:
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if (k > n - k):
        return mod_cmb(n, n - k, p)
    c = d = 1
    for i in range(k):
        c *= (n - i)
        d *= (k - i)
        c %= p
        d %= p
    return c * pow(d, p - 2, p) % p

def main():
    x, y = i_map()

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

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

    if a < 0 or b < 0:
        print(0)
        exit()

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from functools import reduce
def mod_comb4(n,r,mod=10**9+7):
    if r==1:return n
    elif r==0:return 1
    else:
        num=reduce(lambda x,y:x*y%mod,range(n,n-r,-1))
        den=reduce(lambda x,y:x*y%mod,range(1,r+1))
        return num*pow(den,mod-2,mod)%mod
def main():
    x,y=map(int,input().split())
    mod=10**9+7
    if (2*x-y)%3>0 or (2*y-x)%3>0:
        print(0)
    else:
        n=(2*x-y)//3
        m=(2*y-x)//3
        print(mod_comb4(n+m,n,mod)%mod)


if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from functools import reduce
def mod_comb4(n,r,mod=10**9+7):
    num=reduce(lambda x,y:x*y%mod,range(n,n-r,-1))
    den=reduce(lambda x,y:x*y%mod,range(1,r+1))
    return num*pow(den,mod-2,mod)%mod
def main():
    x,y=map(int,input().split())
    mod=10**9+7
    if (2*x-y)%3>0 or (2*y-x)%3>0:
        print(0)
    else:
        n=(2*x-y)//3
        m=(2*y-x)//3
        print(mod_comb4(n+m,n,mod)%mod)


if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
from scipy.misc import comb
x, y = map(int, input().split())
t = (2*y-x)/3
s = (2*x-y)/3
if not t.is_integer() or t<0 or not s.is_integer() or s<0:
  print(0)
else:
  print(int(comb(s+t, min(s, t))%1000000007))

Submission status: Runtime Error

Solution code:

import sys
input = sys.stdin.readline
from math import factorial
large_p = 10**9 + 7

def comb_mod(n, r, large_p):
    a, b = 1, 1
    r = min(r, n - r)
    for i in range(r):
        a = a * (n - i) % large_p
        b = b * (r - i) % large_p
    return a * pow(b, large_p - 2, large_p) % large_p

def main():
    x, y = map(int, input().split())
    p1, p2 = 0, 0
    p1_2, P2_2 = 0, 0
    for i1 in range(1, x//2 + 1):
        if x - i1 == (y - i1 * 2) * 2:
            p1 = i1
            p2 = y - i1 * 2
            break
    for i2 in range(1, y//2 + 1):
        if (x - i2 * 2) * 2 == y - i2:
            p1_2 = i2
            p2_2 = x - i2 * 2

    p1 = min(p1, p1_2)
    p2 = min(p2, p2_2)
    r = comb_mod(p1 + p2, p1, large_p)
    print(r)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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


def main():
    X, Y = map(int, input().split())
    if (X + Y) % 3 != 0:
        print(0)
        exit()
    n = (X+Y) // 3
    if X < 2 or Y < 2:
        print(0)
        exit()
    r = X - n

    # nCrを計算する
    a = [None] * (n+1)
    inva = [None] * (n+1)
    a[0] = 1
    inva[0] = 1
    p = 10**9 + 7

    for i in range(1, n+1):
        a[i] = i * a[i-1] % p
        inva[i] = pow(i, p-2, p) * inva[i-1] % p

    ans = (a[n] * inva[r] % p) * inva[n-r] % p
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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


def main():
    X, Y = map(int, input().split())
    if (X + Y) % 3 != 0:
        print(0)
        exit()
    n = (X+Y) // 3
    r = X - n

    # nCrを計算する
    a = [None] * (n+1)
    inva = [None] * (n+1)
    a[0] = 1
    inva[0] = 1
    p = 10**9 + 7

    for i in range(1, n+1):
        a[i] = i * a[i-1] % p
        inva[i] = pow(i, p-2, p) * inva[i-1] % p

    ans = (a[n] * inva[r] % p) * inva[n-r] % p
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

MOD = 1000000007
if (2*X-Y)%3!=0 or (2*X-Y)<0:
    print(0)
    sys.exit()

A = int((2*X-Y)/3)
B = int(Y-2*A)

if A>B:

ans = 1
inv = 1
for i in range(B):
    ans = ans * (A+B-i) %MOD
    inv = inv * (i+1) %MOD

ans = ans * pow(inv, MOD-2, MOD) %MOD
print(ans)

Submission status: Runtime Error

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

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

if m.is_integer() == False or n.is_integer() == False:
  print(0)
  exit()
if m < 0 or n < 0:
  print(0)
  exit()

def comb(n, k):
  if k > n - k:
    comb(n, n - k)
    return
  mul, div = 1, 1
  for i in range(k):
    mul = mul * (n - i) % mod
    div = div * (k - i) % mod
  return mul * pow(div, mod-2, mod)

ans = comb(int(n+m), int(n)) % mod
print(ans)

Submission status: Runtime Error

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

X, Y = min(X,Y), max(X,Y)

dist = X+Y
if dist%3 != 0 or 2*X < Y:
  ans = 0
else:
  N = dist//3
  Y -= N
  Y = min(N,Y)
  
  ans = 1
  ue = 1
  shita = 1
  for n in range(Y):
    ans = ans*(N-n)/(n+1)
    #ue *= N-n
    #shita *= n+1
    
  ans = int(ans) % (10**9+7)
  
print(ans)

Submission status: Runtime Error

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

X, Y = min(X,Y), max(X,Y)

dist = X+Y
if dist%3 != 0 or 2*X < Y:
  ans = 0
else:
  N = dist//3
  Y -= N
  Y = min(N,Y)
  
  ans = 1
  ue = 1
  shita = 1
  for n in range(Y):
    ans *= (N-n)/(n+1)
    #ue *= N-n
    #shita *= n+1
    
  ans = int(ans) % (10**9+7)
  
print(ans)

Submission status: Runtime Error

Solution code:
memo = [[0]*1000000]*1000000
def p(x,y):
    if (x == 0) | (y == 0):
        return 0
    if (x == 1) & (y == 2):
        return 1
    if (x == 2) & (y == 1):
        return 1
    if (memo[x-1][y-1] != 0):
        return memo[x-1][y-1]
    memo[x-1][y-1] = 2*p(x-1,y-2)
    return memo[x-1][y-1]

def main():
    X, Y = map(int, input().split())
    print(p(X,Y))
    return 0
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

import sys
sys.setrecursionlimit(200000000)
p = 10**9+7

def exp(y,x):
  xbin=str(bin(x))[2:]
  ans=1
  yl=[0]*(len(xbin)+1)
  yl[0]=y
  yl[1]=y**2
  for d,i in enumerate(xbin[::-1],start=0):
    if d > 1:
      yl[d]=yl[d-1]**2%p
    if i == "1":
      ans=(ans*yl[d])%p
  return ans%p

def ff(n,ca):
  if ca == 1:
    return n
  return n*ff(n-1,ca-1)%p

if (y+x)%3 != 0:
  print(0)
elif y/x > 2:
  print(0)
elif y/x < 0.5:
  print(0)
else:
  n=(2*x-y)//3
  m=(2*y-x)//3
  fact=1
  for i in range(2,n+1):
    fact=fact*i%p
  ans=ff(n+m,n)*exp(fact,p-2)%p
  print(ans)

Submission status: Runtime Error

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

import sys
sys.setrecursionlimit(200000000)
p = 10**9+7

def exp(y,x):
  xbin=str(bin(x))[2:]
  ans=1
  yl=[0]*(len(xbin)+1)
  yl[0]=y
  yl[1]=y**2
  for d,i in enumerate(xbin[::-1],start=0):
    if d > 1:
      yl[d]=yl[d-1]**2%p
    if i == "1":
      ans=(ans*yl[d])%p
  return ans%p

def ff(n,ca):
  if ca == 1:
    return n
  return n*ff(n-1,ca-1)%p

if (y+x)%3 != 0:
  print(0)
elif y/x > 2:
  print(0)
elif y/x < 0.5:
  print(0)
else:
  n=(2*x-y)//3
  m=(2*y-x)//3
  fact=[0,1]
  for i in range(2,n+m+1):
    fact.append(fact[-1]*i % p)
  ans=ff(n+m,n)*exp(fact[n],p-2)%p
  print(ans)

Submission status: Runtime Error

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

import sys
sys.setrecursionlimit(200000000)
p = 10**9+7
fact=[0,1]
for i in range(2,max(x,y)+1):
  fact.append(fact[-1]*i % p)

def exp(y,x):
  xbin=str(bin(x))[2:]
  ans=1
  yl=[0]*(len(xbin)+1)
  yl[0]=y
  yl[1]=y**2
  for d,i in enumerate(xbin[::-1],start=0):
    if d > 1:
      yl[d]=yl[d-1]**2%p
    if i == "1":
      ans=(ans*yl[d])%p
  return ans%p

def ff(n,ca):
  if ca == 1:
    return n
  return n*ff(n-1,ca-1)%p

if (y+x)%3 != 0:
  print(0)
elif y/x > 2:
  print(0)
elif y/x < 0.5:
  print(0)
else:
  n=(2*x-y)//3
  m=(2*y-x)//3
  ans=ff(n+m,n)*exp(fact[n],p-2)%p
  print(ans)

Submission status: Runtime Error

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

mx = 10**6
fact = [1]*(mx+1)
for i in range(mx):
  fact[i+1] = fact[i]*(i+1)%mod
def inv(n):
  return pow(n,mod-2,mod)
if (x%3==0 and y%3==0) or (x%3==1 and y%3==2) or (x%3==2 and y%3==1):
  n = int(2*x/3-y/3)
  m = int(-x/3 + 2*y/3)
  s += fact[n+m]*inv(fact[n])*inv(fact[m])%mod
  print(s)
else:
  print(0)

Submission status: Runtime Error

Solution code:
# X = a1 + 2 * a2
# Y = 2 * a1 + a2
# 2Y-X = 3a1
# Y = 2*(2Y-X)/3 + a2
# (2X-Y)/3 = a2
# (2Y-X)/3 = a1

import sys
sys.setrecursionlimit(100000)

from fractions import math
import itertools

X,Y = map(int, input().split())
a1 = (2*Y - X) / 3
a2 = (2*X - Y) / 3
if a1.is_integer() and a2.is_integer():
  ans = len(list(itertools.combinations(range(int(a1+a2)), int(a2)))) % (10**9+7)
  # ans = (math.factorial(a1+a2)/math.factorial(a1)/math.factorial(a2)) % (10**9+7)
  print(int(ans))
else:
  print(0)

Submission status: Runtime Error

Solution code:
class Pos():
    def __init__(self, x, y):
        self.x = int(x)
        self.y = int(y)
        
    def nextPositions(self):
        p = []
        p.append(Pos(self.x+1, self.y+2))
        p.append(Pos(self.x+2, self.y+1))
        return p
        
    def checkOutOfRange(self, area):
        if area.x < self.x or area.y < self.y :
            return True
        return False
    
    def checkAtGoal(self, area):
        if area.x == self.x and area.y == self.y:
            return True
        return False

def forward(pos, area, count):
    #print("now({0},{1})".format(pos.x, pos.y))
    if pos.checkAtGoal(area):
        #print("goal({0},{1})".format(pos.x,pos.y))
        count = count + 1
        return (False,count)
    
    if pos.checkOutOfRange(area):
        return (False, count)
    else:
        next = pos.nextPositions()
        rslt, cnt = forward(next[0], area, count)
        rslt, cnt = forward(next[1], area, cnt)
        return (True, cnt)
    

x,y = input().split()

area = Pos(int(x),int(y))
start = Pos(0, 0)

rslt, count = forward(start, area, 0)

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

Submission status: Runtime Error

Solution code:
class Pos():
    def __init__(self, x, y):
        self.x = int(x)
        self.y = int(y)
        
    def nextPositions(self):
        p = []
        p.append(Pos(self.x+1, self.y+2))
        p.append(Pos(self.x+2, self.y+1))
        return p
        
    def checkOutOfRange(self, area):
        if area.x < self.x or area.y < self.y :
            return True
        return False
    
    def checkAtGoal(self, area):
        if area.x == self.x and area.y == self.y:
            return True
        return False

def forward(pos, area, count):
    #print("now({0},{1})".format(pos.x, pos.y))
    if pos.checkAtGoal(area):
        #print("goal({0},{1})".format(pos.x,pos.y))
        count = count + 1
        return (False,count)
    
    if pos.checkOutOfRange(area):
        return (False, count)
    else:
        next = pos.nextPositions()
        rslt, cnt = forward(next[0], area, count)
        rslt, cnt = forward(next[1], area, cnt)
        return (True, cnt)
    

x,y = input().split()

area = Pos(int(x),int(y))
start = Pos(0, 0)

rslt, count = forward(start, area, 0)

print(count/(10^9+7))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)
 
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
 
def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
 
def combination(n,r,q):
    if r==1:
        return n%q
 
    return ((n*combination(n-1,r-1,q)%q)*modinv(r,q))%q
 
def _input():
    return list(map(int, input().split()))
 
def main():
    i=_input()
    x,y=i[0],i[1]
    if 2*y>=x and 2*x>=y and (2*y-x)%3==0 and (2*x-y)%3==0:
        n=(2*y-x)//3
        m=(2*x-y)//3
        print(int(combination(n+m,min(m,n),1000000007)))
    else:
        print(0)
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def combination(n,r,q):
    if r==1:
        return n%q

    return (n*combination(n-1,r-1,q)*modinv(r,q))%q

def _input():
    return list(map(int, input().split()))

def main():
    i=_input()
    x,y=i[0],i[1]
    if (2*y-x)%3==0 and (2*x-y)%3==0:
        n=(2*y-x)/3
        m=(2*x-y)/3
        print(int(combination(n+m,min(m,n),1000000007)))
    else:
        print(0)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000000)

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def combination(n,r,q):
    if r==1:
        return n%q

    return (n*combination(n-1,r-1,q)*modinv(r,q))%q

def _input():
    return list(map(int, input().split()))

def main():
    i=_input()
    x,y=i[0],i[1]
    if (2*y-x)%3==0 and (2*x-y)%3==0:
        n=(2*y-x)/3
        m=(2*x-y)/3
        print(int(combination(n+m,n,1000000007)))
    else:
        print(0)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def combination(n,r,q):
    if r==1:
        return n%q

    return (n*combination(n-1,r-1,q)*modinv(r,q))%q

def _input():
    return list(map(int, input().split()))

def main():
    i=_input()
    x,y=i[0],i[1]
    if (2*y-x)%3==0 or (2*x-y)%3==0:
        n=(2*y-x)/3
        m=(2*x-y)/3
        print(int(combination(n+m,n,1000000007)))
    else:
        print(0)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def combination(n,r,q):
    if r==1:
        return n%q

    return (n*combination(n-1,r-1,q)*modinv(r,q))%q

def _input():
    return list(map(int, input().split()))

def main():
    i=_input()
    x,y=i[0],i[1]
    if (2*y-x)%3==0 and (2*x-y)%3==0:
        n=(2*y-x)/3
        m=(2*x-y)/3
        print(int(combination(n+m,n,1000000007)))
    else:
        print(0)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
import math

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 )


judge=1
x,y = map(int,input().split())
a = x + y 
if x/y < 0.5 or x/y >2:
    print(0)
    judge=0
if a % 3 != 0:
    print(0)
    judge=0
if judge==1:
    goukei = a//3
    sa = abs(x-y)
    kaisuu = (goukei - sa)//2
    print(cmb(goukei,kaisuu,mod))

Submission status: Runtime Error

Solution code:
import sys
import math

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 )


judge=1
x,y = map(int,input().split())
a = x + y 
if a % 3 != 0:
    print(0)
    judge=0
if judge==1:
    goukei = a//3
    sa = abs(x-y)
    kaisuu = (goukei - sa)//2
    print(cmb(goukei,kaisuu,mod))

Submission status: Runtime Error

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

x,y = map(int,input().split())
a = x + y 
if a % 3 != 0:
    print(0)
    sys.exit()
goukei = a//3
sa = abs(x-y)
kaisuu = (goukei - sa)//2
print(com(goukei,kaisuu)%(10**9+7))

Submission status: Runtime Error

Solution code:
x,y = map(int,input().split())
a = x + y 
if a % 3 != 0:
    print(0)
    exit()
goukei = a//3
sa = abs(x-y)
kaisuu = (goukei - sa)//2
import math
def com(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
print(com(goukei,kaisuu)%(10**9+7))

Submission status: Runtime Error

Solution code:
x,y = map(int,input().split())
a = x + y 
if a % 3 != 0:
    print(0)
    exit()
goukei = a//3
sa = abs(x-y)
kaisuu = (goukei - sa)//2
import math
def com(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
pritn(com(goukei,kaisuu)%(10**9+7))

Submission status: Runtime Error

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



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

if x==0 and y==0:
    print(0)
    exit()


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



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

if n==0 and m==1:
    print(1)
    exit()
if n==1 and m==0:
    print(1)
    exit()
    

#n+mCm
#(n+m)!/m!


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

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

#print(n+m,m)

print(cmb(n+m, m, 10**9+7))

Submission status: Runtime Error

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

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

if (2*X < Y):
    print (0)
    exit()

W = X - ((X+Y)//3)
H = Y - ((X+Y)//3)

mx = 10**6
fact = [1] * (mx+1) # 階乗を格納するリスト
def inv(n): # MODを法とした逆元
    return pow(n, MOD-2, MOD)
for i in range(mx):
    fact[i+1] = fact[i] * (i+1) % MOD # 階乗を計算
ans = (fact[W+H] * inv(fact[W]) * inv(fact[H])) % MOD # comb(W+H,W) = (W+H)!/(W!H!)
print (ans)

Submission status: Runtime Error

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

a = 2*x - y
b = -x + 2*y
if a < 0 or b < 0:
    print(0)
    eixt()

a //= 3
b //= 3
MOD = 10**9+7
MAX_N = 10**6
fact = [1]
fact_inv = [0]*(MAX_N+4)
for i in range(MAX_N+3):
    fact.append(fact[-1]*(i+1)%MOD)

fact_inv[-1] = pow(fact[-1],MOD-2,MOD)
for i in range(MAX_N+2,-1,-1):
    fact_inv[i] = fact_inv[i+1]*(i+1)%MOD

def mod_comb_k(n,k,MOD):
    return fact[n] * fact_inv[k] % MOD * fact_inv[n-k] %MOD


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

Submission status: Runtime Error

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

a = (2*x - y)//3
b = (-x + 2*y)//3
if a < 0 or b < 0:
    print(0)
    eixt()

MOD = 10**9+7
MAX_N = 10**6
fact = [1]
fact_inv = [0]*(MAX_N+4)
for i in range(MAX_N+3):
    fact.append(fact[-1]*(i+1)%MOD)

fact_inv[-1] = pow(fact[-1],MOD-2,MOD)
for i in range(MAX_N+2,-1,-1):
    fact_inv[i] = fact_inv[i+1]*(i+1)%MOD

def mod_comb_k(n,k,MOD):
    return fact[n] * fact_inv[k] % MOD * fact_inv[n-k] %MOD


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

Submission status: Runtime Error

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

dp[0][0] = 1
dp[0][1] = 0
dp[1][0] = 0
dp[1][1] = 0
for j in range(1,Y+1):
    for i in range(1,X+1):
        dp[j][i]=(dp[j-1][i-2]+dp[j-2][i-1])%mod
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
import math
import sys

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

#互いに素な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は互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

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

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

mod = 10 ** 9 + 7

numerater = math.factorial(x + y) % mod
denominator_x = math.factorial(x) % mod
denominator_y = math.factorial(x) % mod
denominator = (denominator_x * denominator_y) % mod

res = (numerater * mod_inv(denominator, mod)) % mod

print(res)

Submission status: Runtime Error

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

MOD = 10**9 + 7
def prepare(n, MOD):

    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(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 factorials, invs
if (X+Y)%3!=0:
    print(0)
else:
    #最初に行き方を決めて、使う移動方法の個数を求めて、重複組み合わせ
    #決め打ちしてから n:2x+yの移動　m:x+2yの移動
    n = (2*X-Y)//3
    m = (2*Y-X)//3


    fac, invs = prepare((n+m), MOD)


    print(fac[n+m]*invs[n]*invs[m]%MOD)

Submission status: Runtime Error

Solution code:
// #include <bits/stdc++.h>
#include <iostream>  // cin, cout, string
#include <algorithm> // sort, min/max, upper/lower_bound, transform, count/copy_if
#include <vector>
#include <utility> // pair, swap
#include <functional>
#include <iomanip> // setprecision
#include <map>
#include <set> // multiset
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <stack>
#include <queue> // priority_queue
#include <deque>
#include <bitset>
#include <array>
#include <list>
#include <forward_list>
#include <complex>
#include <ratio>
#include <cassert>
#include <numeric> // accumulate, itoa
#include <random>  // mt19937
#include <iterator>
#include <chrono>
#include <cstring>

using namespace std;

// #define int long long

using i64 = int64_t;
using ll = long long;
using ld = long double;

template <typename T>
using vec = vector<T>;
template <typename T>
using mat = vec<vec<T>>;
template <typename T>
using dic = unordered_map<string, T>;
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>; // dijkstra
// template<typename T, typename U> using P = pair<T, U>;
// template<typename... Args> using func = function<Args...>;
// template<typename T> using pq = priority_queue<T>;

using pii = pair<int, int>;
using ppi = pair<pii, int>;
using pip = pair<int, pii>;
using ppp = pair<pii, pii>;

using vi = vec<int>;
using mi = mat<int>; // Graph
using vp = vec<pii>;

constexpr int IINF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
// constexpr int INF = sizeof(int) == sizeof(long long) ? LINF : IINF;
constexpr long long MOD = 1e9 + 7;

#define _overload(_1, _2, _3, name, ...) name
#define _rep1(i, a, b) for (int i = (a), _##i = (b); i < _##i; ++i)
#define _rep2(i, n) _rep1(i, 0, n)
#define _rep3(n) _rep2(i, n)
#define rep(...) _overload(__VA_ARGS__, _rep1, _rep2, _rep3)(__VA_ARGS__)
#define _rrep1(i, a, b) for (int i = (b)-1, _##i = (a); i >= _##i; --i)
#define _rrep2(i, n) _rrep1(i, 0, n)
#define _rrep3(n) _rrep2(i, n)
#define rrep(...) _overload(__VA_ARGS__, _rrep1, _rrep2, _rrep3)(__VA_ARGS__)

#define each(i, a) for (auto &&i : a)
#define each2(i, a) for (const auto &i : a)

#define pb push_back
// emplace_back(*) == push_back(constructor(*))
#define eb emplace_back
#define pob pop_back
#define pf push_front
#define pof pop_front

#define np next_permutation
#define pp prev_permutation

// make_pair(A, B) == pair<T, U>(A, B)
#define mp make_pair
// mt(...) == tie(...)
#define mt make_tuple

#define ft first
#define sd second

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define sz(a) (int)(a).size()
#define rev(a) reverse(all(a))
#define rs(a, l) (a).resize(l)

#define upper(s) transform(all(s), (s).begin(), topper)
#define lower(s) transform(all(s), (s).begin(), tolower)

#define sum(a) accumulate(all(a), 0)
#define elif else if
#define unless(a) if (!(a))
#define qt(a) #a

#define endl '\n'
#define dec(n) fixed << setprecision(n)
#define zfl(n) setfill(‘0’) << setw(n)

template <typename T = int, T l = 0, T r = (T)MOD>
auto rnd = bind(uniform_int_distribution<T>(l, r), mt19937(chrono::steady_clock::now().time_since_epoch().count()));

template <typename T>
inline constexpr T gcd(T a, T b)
{
    if (a == 0 || b == 0)
        return 0;
    while (b)
    {
        a = a % b;
        swap(a, b);
    }
    return a;
}
template <typename T>
inline constexpr T extgcd2(T a, T b, T &x, T &y)
{
    x = 1;
    y = 0;
    while (b)
    {
        T t = a / b;
        a -= t * b;
        swap(a, b);
        x -= t * y;
        swap(x, y);
    }
    return a;
}
template <typename T>
inline constexpr T lcm(T a, T b) { return a / gcd(a, b) * b; }

template <typename T>
inline constexpr bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T>
inline constexpr bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return true;
    }
    return false;
}

template <typename A, typename B>
istream &operator>>(istream &is, pair<A, B> &p)
{
    is >> p.first;
    is >> p.second;
    return is;
}
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p)
{
    os << p.first << " " << p.second;
    return os;
}

template <typename T>
istream &operator>>(istream &is, vector<T> &v)
{
    for (auto &&x : v)
        is >> x;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    for (int i = 0; i < (int)v.size(); ++i)
        cout << v[i] << (i + 1 != (int)v.size() ? " " : "");
    return os;
}

#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg>
void __f(const char *name, const Arg &arg)
{
    cerr << name << " : " << arg << endl;
}
template <typename Arg, typename... Args>
void __f(const char *names, const Arg &arg, const Args &... args)
{
    const char *comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << " : " << arg << " | ";
    __f(comma + 1, args...);
}

inline auto yes(const bool &c) { return c ? "yes" : "no"; }
inline auto Yes(const bool &c) { return c ? "Yes" : "No"; }
inline auto YES(const bool &c) { return c ? "YES" : "NO"; }
inline auto Possible(const bool &c) { return c ? "Possible" : "Impossible"; }
inline auto POSSIBLE(const bool &c) { return c ? "POSSIBLE" : "IMPOSSIBLE"; }

constexpr int lim = 100007; // 10^5+7

ll x, y;

ll c(ll n, ll r)
{
    if (r == 1)
        return n;
    return (n * c(n - 1, r - 1) / r) % 100000007;
}

long long modinv(long long a)
{
    long long b = MOD, u = 1, v = 0;
    while (b)
    {
        long long t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= MOD;
    if (u < 0)
        u += MOD;
    return u;
}
ll comb(ll n, ll r)
{
    ll ret = 1;
    rep(r)
    {
        ret = ret * (n - i) % MOD;
        //cout << i << endl;
    }
    rep(r)
    {
        ret = ret * modinv(i + 1) % MOD;
        // cout << i << endl;
    }
    return ret;
}

signed main()
{
    // cin.tie(0);
    // cout.tie(0);
    // ios_base::sync_with_stdio(false);

    cin >> x >> y;
    //cout << c(x, y) << endl;
    ;
    if ((x + y) % 3 != 0)
    {
        cout << 0 << endl;
        return 1;
    }
    ll n = (x + y) / 3;
    ll tx, ty;
    tx = x - n;
    ty = y - n;
    cout << comb(n, tx) << endl;

    return 0;
}

Submission status: Runtime Error

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


def c(n, k):
    from math import factorial

    ans = factorial(n) / factorial(k) / factorial(n - k)

    return ans % mod


mod = 10**9 + 7

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

if y > x:
    temp = y
    y = x
    x = temp

if ((x + y) % 3 != 0) or x > y * 2:
    print("0")
else:
    n = ((x + y) // 3)
    k = ((n - abs(x - y)) // 2)
    ans = c(n, k)
    print(ans)

Submission status: Runtime Error

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

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


def c(n, k):
    return 1 if(k <= 0 or n <= k) else c(n-1, k-1) + c(n-1, k)


if y > x:
    temp = y
    y = x
    x = temp

if ((x + y) % 3 != 0) or x > y * 2:
    print("0")
else:
    n = ((x + y) // 3)
    k = ((n - abs(x - y)) // 2)
    print(c(n, k))