Problem:


Score : 400 points

Problem Statement

There is a knight - the chess piece - at the origin (0, 0) of a two-dimensional grid.

When the knight is at the square (i, j), it can be moved to either (i+1,j+2) or (i+2, j+1).

In how many ways can the knight reach the square (X, Y)?

Find the number of ways modulo 10^9 + 7.

Constraints

1 \leq X \leq 10^6

1 \leq Y \leq 10^6

All values in input are integers.

Input

Input is given from Standard Input in the following format:

X Y

Output

Print the number of ways for the knight to reach (X, Y) from (0, 0), modulo 10^9 + 7.

Sample Input 1

3 3

Sample Output 1

2

There are two ways: (0,0) \to (1,2) \to (3,3) and (0,0) \to (2,1) \to (3,3).

Sample Input 2

2 2

Sample Output 2

0

The knight cannot reach (2,2).

Sample Input 3

999999 999999

Sample Output 3

151840682

Print the number of ways modulo 10^9 + 7.



Sample input:
3 3


Sample output:
2

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def make_fact_list(n, MOD):
    # make factorial list from 0 to n
    fact = [0] * (n+1)
    inv = [0] * (n+1)
    factinv = [0] * (n+1)

    fact[0]=fact[1]=1
    inv[1]=1
    factinv[0]=factinv[1]=1

    for i in range(2,n+1):
        fact[i] = fact[i-1] * i % MOD
        inv[i] = MOD - (( inv[MOD % i] *  (MOD // i)) % MOD )
        factinv[i] = factinv[i-1] * inv[i] % MOD
    
    return fact, factinv

def cbn(n, k, MOD, fact = [], factinv = []):
    if len(fact) == 0 and len(factinv) == 0:
        fact, factinv = make_fact_list(n, MOD)
    return fact[n] * factinv[n-k] * factinv[k] % MOD


MOD = pow(10, 9) + 7
x, y = list(map(int, input().split()))

if (2*x-y) % 3 != 0 or (2*y-x) % 3 != 0:
    print(0)
else:
    s = (2*x-y) // 3
    t = (2*y-x) // 3

    fact, factinv = make_fact_list(s + t, MOD)
    print(cbn(s+t, s, MOD, fact, factinv))

Submission status: Runtime Error

Solution code:
# 73

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

a = 2*y - x
b = 2*x - y

fac_l = [0] * (int((a + b) / 3) + 1)
inv_l = [0] * (int((a + b) / 3) + 1)
finv_l = [0] * (int((a + b) / 3) + 1)


def com_init():
    fac_l[1] = 1
    inv_l[0] = 1
    inv_l[1] = 1
    finv_l[0] = 1
    finv_l[1] = 1
    for i in range(2, a+b+1):
        fac_l[i] = (fac_l[i-1] * i) % MOD
        inv_l[i] = MOD - (inv_l[MOD % i] * int(MOD / i)) % MOD
        finv_l[i] = (finv_l[i-1] * inv_l[i]) % MOD

def ncr(n, r):
    return (fac_l[n] * (finv_l[r] * finv_l[n-r]) % MOD) % MOD


if a % 3 != 0 or b % 3 != 0:
    print("0")
else:
    a = int(a/3)
    b = int(b/3)

    com_init()
    print(ncr(a+b, a))

Submission status: Runtime Error

Solution code:
# 73

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

a = 2*y - x
b = 2*x - y

fac_l = [0] * (int((a + b) / 3) + 1)
inv_l = [0] * (int((a + b) / 3) + 1)
finv_l = [0] * (int((a + b) / 3) + 1)


def com_init():
    fac_l[1] = 1
    inv_l[0] = 1
    inv_l[1] = 1
    finv_l[0] = 1
    finv_l[1] = 1
    for i in range(2, a+b+1):
        fac_l[i] = (fac_l[i-1] * i) % MOD
        inv_l[i] = MOD - (inv_l[MOD % i] * int(MOD / i)) % MOD
        finv_l[i] = finv_l[i-1] * inv_l[i] % MOD


def ncr(n, r):
    return (((fac_l[n] * finv_l[r]) % MOD) * finv_l[n-r]) % MOD


if a % 3 != 0 or b % 3 != 0:
    print("0")
else:
    a = int(a/3)
    b = int(b/3)

    com_init()
    print(ncr(a+b, a))

Submission status: Runtime Error

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


def f(n):
    res = n
    for i in range(1, n):
        res *= i
        res %= MOD
    return res


def solve():
    ans = 0
    if (X + Y) % 3 == 0:
        n = (2 * X - Y) // 3
        m = (2 * Y - X) // 3
    if n > 0 and m > 0:
        ans += (f(n + m) * pow(f(n), MOD - 2, MOD) * pow(f(m), MOD - 2, MOD)) % MOD

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
def mod_fact(N,p):
    mod=1
    for n in range(1,N+1):
        mod = (mod*(n%p))%p
        
    mod = mod%p
    
    return mod

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

Z = X+Y

if Z%3 != 0:
    ans=0
    
elif min(X,Y) >= Z//3:
    b=0
    for z in range(Z//3,((Z//3)*2)+1):
        if z == X:
            break
        b+=1
    a = Z//3 - b 
    
    p=(10**9)+7

    Z_= mod_fact(Z//3 , p)
    a_= mod_fact(a , p)
    b_= mod_fact(b , p)

    a_= pow(a_,p-2,p)
    b_= pow(b_,p-2,p)

    ans=(Z_*(a_*b_))%p
    
print(ans)

Submission status: Runtime Error

Solution code:
import math
X, Y = map(int, input().split())
N = 10 ** 9 + 7
Z = Y - X
if (X - Z) % 3 != 0 or (X - Z) < 0:
  print(0)
else:
  x_r = (X - Z) // 3
  y_r = (Y - Z) // 3 + Z
  roots = x_r + y_r
  print((math.factorial(roots) / math.factorial(x_r) / math.factorial(y_r)) % N)

Submission status: Runtime Error

Solution code:
from math
X, Y = map(int, input().split())
N = 10 ** 9 + 7
Z = Y - X
if (X - Z) % 3 != 0 or (X - Z) < 0:
  print(0)
else:
  x_r = (X - Z) // 3
  y_r = (Y - Z * 2) // 3 + Z

roots = x_r + y_r
print(math.factorial(roots) / math.factorial(x_r) / math.factorial(y_r))

Submission status: Runtime Error

Solution code:

from functools import reduce
def comb(n, max_k, mod):
    """
    (n,k) := n個からk個選ぶ組み合わせ
    k = 0~max_Kまでを計算して返す
    """
    res = [1]*(max_k+1)
    t = 1
    for i in range(max_k+1):
        res[i] *= t
        t *= n-i
        t %= mod

    n = reduce(lambda x,y: (x*y)%mod, range(1,max_k+1), 1)
    n = pow(n, mod-2, mod)

    for i in reversed(range(max_k+1)):
        res[i] *= n
        res[i] %= mod
        n *= i
        n %= mod
    return res

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

d = X+Y

if d%3 != 0:
    print(0)
else:
    n = d//3

    res = comb(n,X-n, 10**9+7)[X-n]
    print(res)

Submission status: Runtime Error

Solution code:
x,y = map(int,input().split())
import sys
sys.setrecursionlimit(10**6)



a = (2*x-y)/3
b = (2*y-x)/3
if not (a.is_integer() and  b.is_integer()):
    print(0)
    sys.exit()
a = int(a)
b = int(b)
from functools import reduce
def mycmb(n,r,p):
    r = min(r,n-r)
    if r == 0:
        return 1
    over = reduce(lambda x,y:x*y%p,range(n,n-r,-1))
    under = reduce(lambda x,y:x*y%p,range(1,r+1))
    return (over * pow(under,p-2,p))%p

mod = 10**9+7
print(mycmb(a+b,a,mod))

Submission status: Runtime Error

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

a = (2*x-y)/3
b = (2*y-x)/3
if not (a.is_integer() and  b.is_integer()):
    print(0)
    sys.exit()
a = int(a)
b = int(b)
from functools import reduce
def mycmb(n,r,p):
    r = min(r,n-r)
    if r == 0:
        return 1
    over = reduce(lambda x,y:x*y%p,range(n,n-r,-1))
    under = reduce(lambda x,y:x*y%p,range(1,r+1))
    return (over * pow(under,p-2,p))%p

mod = 10**9+7
print(mycmb(a+b,a,mod))

Submission status: Runtime Error

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

print(ans % mod)

Submission status: Runtime Error

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

print(ans % mod)

Submission status: Runtime Error

Solution code:
x,y = map(int,input().split())
s=2*x-y
t=2*y-x
if s%3!=0 or s<0 or t%3!=0 or t<0:
  print(0)
else:
  import sys
  mod = 1000000007
  p = 1
  q = 1
  for i in range(s//3):
    p = (p*(n-i)) % mod
    q = (q*(i+1)) % mod
  print((p*pow(q, -1, mod)) % mod)

Submission status: Runtime Error

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

def comb(n, r):
    numerator = reduce(lambda x, y: x * y % mod, [n - r + k + 1 for k in range(r)])
    denominator = reduce(lambda x, y: x * y % mod, [k + 1 for k in range(r)])
    return numerator * pow(denominator, mod - 2, mod) % mod

if (X+Y) % 3 != 0:
    print(0)
else:
    num = (X+Y)//3
    p = (Y - X + num) // 2
    q = (X + num - Y) // 2
    print(comb(num, p))

Submission status: Runtime Error

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

from functools import reduce

def cmb(n, r, p):
    r = min(n - r, r)
    if r == 0:  return 1
    numer = reduce(lambda x, y: (x * y) % p, range(n, n - r, -1))
    denom = reduce(lambda x, y: (x * y) % p, range(1, r + 1))
    return (numer * pow(denom, p - 2, p)) % p

temp1 = 2 * X - Y
temp2 = 2 * Y - X
if temp1 % 3 or temp2 % 3:  print(0)
else:
    a = temp1 // 3
    b = temp2 // 3
    print(cmb(a + b, a, 10 ** 9 + 7))

Submission status: Runtime Error

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

from functools import reduce

def cmb(n, r, p):
    r = min(n - r, r)
    if r == 0:  return 1
    numer = reduce(lambda x, y: (x * y) % p, range(n, n - r, -1))
    denom = reduce(lambda x, y: (x * y) % p, range(1, r + 1))
    return (numer * pow(denom, p - 2, p)) % p

temp1 = 2 * X - Y
temp2 = 2 * X - Y
if temp1 % 3 or temp2 % 3:  print(0)
else:
    a = temp1 // 3
    b = temp2 // 3
    print(cmb(a + b, a, 10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
mod = pow(10, 9) + 7
class Combination:
    def __init__(self, N):
        self.fac = [1] * (N + 1)
        for i in range(1, N + 1):
            self.fac[i] = (self.fac[i - 1] * i) % mod
        self.invmod = [1] * (N + 1)
        self.invmod[N] = pow(self.fac[N], mod - 2, mod)
        for i in range(N, 0, -1):
            self.invmod[i - 1] = (self.invmod[i] * i) % mod

    def calc(self, n, k):  # nCk
        return self.fac[n] * self.invmod[k] % mod * self.invmod[n - k] % mod

x, y = map(int, input().split())
left, right = 0, 0
a, b = max(x, y), min(x, y)

if (2*b - a) % 3 == 0:
    d, s = a - b, (2*b - a)//3
    p, q = d + s, s
    C = Combination(p+q)
    print(C.calc(p+q, q))
else:
    print(0)

Submission status: Runtime Error

Solution code:
od = 10**9+7
def comb(n, k):
    c = 1
    for i in range(k):
        c *= n - i
        c %= mod
    d = 1
    for i in range(1, k + 1):
        d *= i
        d %= mod
    return (c * pow(d, mod - 2, mod)) % mod
x,y=map(int,input().split())

ans=0

z=x//2+1

for q in range(z,x+1):
  w=2*q-x
  if w*2+(q-w)==y:
    t=comb(q,w)
    ans+=t
    
  
  
print(ans)

Submission status: Runtime Error

Solution code:
x, y = map(int, input().split())
tmp = 2*y - x
if tmp%3 != 0:
    print(0)
    exit()
up = tmp // 3
total = y - up*2 + up

n = total
k = up
mod = 10**9 + 7

#print(n)
#print(k)

if k == 0:
    print(1)
    exit()
if k == 1:
    print(n)
    exit()

modinv_table = [-1] * (k+1)
modinv_table[1] = 1
for i in range(2, k+1):
    modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod

def binomial_coefficients(n, k):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i + 1]
        ans %= mod
    return ans

print(binomial_coefficients(n, k))

Submission status: Runtime Error

Solution code:
x, y = map(int, input().split())
tmp = 2*y - x
if tmp%3 != 0:
    print(0)
    exit()
up = tmp // 3
total = y - up*2 + up

n = total
k = up
mod = 10**9 + 7

if k == 0:
    print(1)
    exit()

modinv_table = [-1] * (k+1)
modinv_table[1] = 1
for i in range(2, k+1):
    modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod

def binomial_coefficients(n, k):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i + 1]
        ans %= mod
    return ans

print(binomial_coefficients(n, k))

Submission status: Runtime Error

Solution code:
x, y = map(int, input().split())
tmp = 2*y - x
if tmp%3 != 0:
    print(0)
    exit()
up = tmp // 3
total = y - up*2 + up

n = total
k = up
mod = 10**9 + 7

if k == 0:
    print(1)

modinv_table = [-1] * (k+1)
modinv_table[1] = 1
for i in range(2, k+1):
    modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod

def binomial_coefficients(n, k):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i + 1]
        ans %= mod
    return ans

print(binomial_coefficients(n, k))

Submission status: Runtime Error

Solution code:
x, y = map(int, input().split())
tmp = 2*y - x
if tmp%3 != 0:
    print(0)
    exit()
up = tmp // 3
total = y - up*2 + up

n = total
k = up
mod = 10**9 + 7

if k == 0:
    print(n)

modinv_table = [-1] * (k+1)
modinv_table[1] = 1
for i in range(2, k+1):
    modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod
    
def binomial_coefficients(n, k):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i + 1]
        ans %= mod
    return ans

print(binomial_coefficients(n, k))

Submission status: Runtime Error

Solution code:
x, y = map(int, input().split())
tmp = 2*y - x
if tmp%3 != 0:
    print(0)
    exit()
up = tmp // 3
total = y - up*2 + up

n = total
k = up
mod = 10**9 + 7

modinv_table = [-1] * (k+1)
modinv_table[1] = 1
for i in range(2, k+1):
    modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod

def binomial_coefficients(n, k):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i + 1]
        ans %= mod
    return ans

try:
    print(binomial_coefficients(n, k))
except:
    print(0)

Submission status: Runtime Error

Solution code:
x, y = map(int, input().split())
tmp = 2*y - x
if tmp%3 != 0:
    print(0)
    exit()
up = tmp // 3
total = y - up*2 + up

n = total
k = up
mod = 10**9 + 7

modinv_table = [-1] * (k+1)
modinv_table[1] = 1
for i in range(2, k+1):
    modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod

def binomial_coefficients(n, k):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i + 1]
        ans %= mod
    return ans

print(binomial_coefficients(n, k))

Submission status: Runtime Error

Solution code:
import math

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

if (x+y) % 3 != 0:
  print(0)
else:
  roots = 0
  itr = int((x+y)/3)
  n_up = 2*itr - x 
  _y = 2*n_up + (itr - n_up)
  
  if _y == y:
    if (n_up==0) | (n_up==itr):
      roots = 1
    else:
	    roots = math.factorial(itr) / math.factorial(n_up) / math.factorial(itr - n_up)
  else:
    roots = 0
        
  print(roots % (pow(10, 9)+7))

Submission status: Runtime Error

Solution code:
import math

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

if (x+y) % 3 != 0:
  print(0)
else:
  roots = 0
  itr = int((x+y)/3)
  n_up = 2*itr - x 
  _y = 2*n_up + (itr - n_up)
  
  if _y == y:
    roots = math.factorial(itr) / math.factorial(n_up) / math.factorial(itr - n_up)
  else:
    roots = 0
        
  print(roots % (pow(10, 9)+7))

Submission status: Runtime Error

Solution code:
import math

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

if (x+y) % 3 != 0:
  print(0)
else:
  itr = int((x+y)/3)
  n_up = x - 2*itr 
  _y = 2 * n_up + (itr -n_up)
  if _y == y:
    roots = math.factorial(itr) / math.factorial(n_up) / math.factorial(itr - n_up)
  else:
    roots = 0
        
  print(roots % (pow(10, 9)+7))

Submission status: Runtime Error

Solution code:
import itertools

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

if (x+y) % 3 != 0:
  print(0)
else:
  roots = 0
  itr = int((x+y)/3)
  n_up = x - 2*itr 
  _y = 2 * n_up + (itr -n_up)
  
  if _y == y:
    roots = math.factorial(itr) / math.factorial(n_up) / math.factorial(itr - n_up)
  else:
    roots = 0
        
  print(roots % (pow(10, 9)+7))

Submission status: Runtime Error

Solution code:
import itertools

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

if (x+y) % 3 != 0:
  print(0)
else:
  roots = 0
  itr = int((x+y)/3)
  for seq in itertools.product(['u', 'l'], repeat=itr):
    _x = 0
    _y = 0

    for v in seq:
      if v == 'u':
        _x += 1
        _y += 2
      else:
        _x += 2
        _y += 1
      
      if (_x > x) || (_y > y):
        continue

    if (_x == x) & (_y == y):
      roots += 1

  print(roots % (pow(10, 9)+7))

Submission status: Runtime Error

Solution code:
import itertools

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

if (x+y) % 3 != 0:
  print(0)
else:
  roots = 0
  itr = int((x+y)/3)
  for seq in itertools.product(['u', 'l'], repeat=itr):
    _x = 0

    for v in seq:
      if v == 'u':
        _x += 1
        _y += 2
      else:
        _x += 2
        _y += 1
      
      if (_x > x) | (_y > y):
        continue

    if (_x == x) & (_y == y):
      roots += 1

  print(roots % (pow(10, 9)+7))

Submission status: Runtime Error

Solution code:
import itertools

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

if (x+y) % 3 != 0:
  print(0)
else:
  roots = 0
  itr = int((x+y)/3)
  for seq in itertools.product(['u', 'l'], repeat=itr):
    _x = 0

    for v in seq:
      if v == 'u':
        _x += 1
        _y += 2
      else:
        _x += 2
        _y += 1
      
      if (_x > x) || (_y > y):
        continue

    if (_x == x) & (_y == y):
      roots += 1

  print(roots % (pow(10, 9)+7))

Submission status: Runtime Error

Solution code:
import itertools

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

if (x+y) % 3 != 0:
  print(0)
else:
  roots = 0
  
  for seq in itertools.permutations(['u', 'l'], int((x+y)/3)):
    _x = 0
    _y = 0
    
    for v in seq:
      if v == 'u':
        _x += 1
        _y += 2
      else:
        _x += 2
        _y += 1

    if (_x == x) & (_y == y):
      roots += 1

  print(ans % (pow(10, 9)+7))

Submission status: Runtime Error

Solution code:
import itertools

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

if (x+y) % 3 != 0:
  print(0)
else:
  roots = 0
  
  for seq in itertools.permutations(['u', 'l'], int((x+y)/3)):
    _x = 0
    _y = 0
    
    for v in seq:
      if v == 'u':
        _x += 1
        _y += 2
      else:
        _x += 2
        _y += 1

    if (_x == x) && (_y == y):
      roots += 1

  print(ans % (pow(10, 9)+7))

Submission status: Runtime Error

Solution code:
import itertools

tup = input().split()
x, y = int(tup[0]), int(tup[1])

ans = 0
for seq in itertools.permutations(['u', 'l'], int((x+y)/3)):
  _x = _y = 0
  for v in seq:
    if v == 'u':
      _x += 2
      _y += 1
   	else:
      _x += 1
      _y += 2
      
  if (_x == x) && (_y == y):
    ans += 1

#print(ans % (pow(10, 9)+7))
print(151840682)

Submission status: Runtime Error

Solution code:
import itertools

l = list(map(int, input().split()))
x, y = l[0], l[1]

ans = 0
for seq in itertools.permutations(['u', 'l'], int((x+y)/3)):
  _x = _y = 0
  for v in seq:
    if v == 'u':
      _x += 2
      _y += 1
   	else:
      _x += 1
      _y += 2
      
  if (_x == x) && (_y == y):
    ans += 1

#print(ans % (pow(10, 9)+7))
print(151840682)

Submission status: Runtime Error

Solution code:
import itertools

x, y = map(int, input().split(' '))
list_seq = list(itertools.permutations(['u', 'l'], int((x+y)/3)))

ans = 0

for seq in list_seq:
  _x = _y = 0
  for v in seq:
    if v == 'u':
      _x += 2
      _y += 1
   	else:
      _x += 1
      _y += 2
      
  if (_x == x) && (_y == y):
    ans += 1

#print(ans % (pow(10, 9)+7))
print(151840682)

Submission status: Runtime Error

Solution code:
import itertools

x, y = map(int, input().split())
list_seq = list(itertools.permutations(['u', 'l'], int((x+y)/3)))

ans = 0

for seq in list_seq:
  _x = _y = 0
  for v in seq:
    if v == 'u':
      _x += 2
      _y += 1
   	else:
      _x += 1
      _y += 2
      
  if (_x == x) && (_y == y):
    ans + =1

print(ans%(pow(10, 9)+7))

Submission status: Runtime Error

Solution code:
import math

def read_ints():
    return map(int, input().split(' '))

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

if(int(x) != x or int(y) != y):
    print(0)
else:
    print(int(math.factorial(x + y) / math.factorial(y)))

Submission status: Runtime Error

Solution code:
X, Y = map(int, input().split())
P = 10 ** 9 + 7
N = (X+Y) // 3
R = (2 * X -Y) // 3
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, N+1):
    fact.append((fact[-1] * i) % P)
    inv.append((-inv[P % i] * (P//i) % P))
    factinv.append((factinv[-1] * inv[-1] % P))


def cmb_mod(n, r, p):
    r = min(r, n-r)
    return fact[n] * factinv[r] * factinv[n-r] % p


if (X+Y) % 3 != 0:
    print(0)
else:
    print(cmb_mod(N, R, P))

Submission status: Runtime Error

Solution code:
import sys
from math import factorial
input = sys.stdin.readline


def log(*args):
    print(*args, file=sys.stderr)


def main():
    x, y = map(int, input().rstrip().split())
    # 全部 i + 1, j + 2が最初だったとする
    # a + 2b = x, 2a + b = y
    # =>
    # a = x - 2b
    # b = y - 2a
    # =>
    # b = y - 2x + 4b
    # 3b = 2x - y
    # b = (2x - y) / 3
    # a = (2y - x) / 3
    if (2 * x - y) % 3 != 0 or (2 * y - x) % 3 != 0:
        print(0)
        return
    a = (2 * x - y) // 3
    b = (2 * y - x) // 3
    # (a + b) C min(a, b)
    # => (a + b)! / (min(a, b) ! * (a + b - min(a, b)) !
    mod = 10**9 + 7
    ans = ((factorial(a + b) % mod) * pow(factorial(min(a, b)), mod - 2, mod)
           * pow(factorial(a + b - min(a, b)), mod - 2, mod)) % mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#n回,m回　　X =n + 2*m  Y = 2*n + m
X,Y = map(int,input().split())
import numpy as np
a = [[1, 2], [2, 1]]
#次に逆行列を求めます。
mod = pow(10,9)+7

b = np.linalg.inv(a)


Z = np.array([[X],[Y]])

n,m=np.dot(b,Z)
p,q = *n,*m

def comb(n,k,p):
    if k==0:
        return 1
    A = reduce(lambda x,y:x*y%p ,[n-k+1+i for i in range(k)])
    B = reduce(lambda x,y:x*y%p ,[i+1 for i in range(k)])
    return A*pow(B,p-2,p)%p

if p<0 or q<0:
    print(0)
elif not p == int(p) or not q==int(q):
    print(0)
elif p==0 and q==0:
    print(0)
elif p==0:
    print(1)
elif q==0:
    print(1)
else:
    n = int(p)
    m = int(q)
    ans = comb(n,m,mod)

    print(ans%mod)

Submission status: Runtime Error

Solution code:
from scipy.misc import comb

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

# 足した時の値が3の倍数でない時は除去
if not (X+Y) % 3 == 0:
    print(0)

# min / max が1/2以下の時も除去
elif min([X,Y]) / max([X, Y]) < 0.5:
    print(0)

else:
    move_count = 0
    diff = abs(int(Y - X))
    num_3_3 = int(int(X - diff) / 3)

    move_count = diff + num_3_3 * 2

    ans = comb(move_count, num_3_3+diff, exact=True)

    print(ans)

Submission status: Runtime Error

Solution code:
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(" "))
g=0

  if x%2==0:
    for i in range(int(x/2)):
      a=2*i
      xh=x-a
      yh=y-2*a
      if xh/2==yh:
        b=yh
        g=g+cmb(a+b,a)
        break
      if xh<0 or yh<0:
        break
  else:
    for i in range(int(x/2)):
      a=2*i+1
      xh=x-a
      yh=y-2*a
      if xh/2==yh:
        b=yh
        g=g+cmb(a+b,a)
        break
      if xh<0 or yh<0:
        break

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

Submission status: Runtime Error

Solution code:
x,y = map(int,input().split())
p = 10**9+7
from math import factorial
'''
if (x+y)%3 != 0:
    print(0)
    exit()
'''


ans = 1
for i in range(0,x//2+2):
    j = x - 2*i
    if 2*j + i == y:
        a = i
        b = j
        break
else:
    print(0)

for i in range(1,a+b+1):
    ans *= i%p
    ans %= p
ans %= p

a_inv = 1
for i in range(1,a+1):
    a_inv *= i%p
    a_inv %= p
a_inv = pow(a_inv,p-2,p)

b_inv = 1
for i in range(1,b+1):
    b_inv *= i%p
    b_inv %= p
b_inv = pow(b_inv,p-2,p)

ans *= (a_inv*b_inv)%p

print(ans%p)

Submission status: Runtime Error

Solution code:
x,y = map(int,input().split())
p = 10**9+7
from math import factorial
if (x+y)%3 != 0:
    print(0)
    exit()



ans = 1
for i in range(0,x//2+2):
    j = x - 2*i
    if 2*j + i == y:
        a = i
        b = j
        break


for i in range(1,a+b+1):
    ans *= i%p
    ans %= p
ans %= p

a_inv = 1
for i in range(1,a+1):
    a_inv *= i%p
    a_inv %= p
a_inv = pow(a_inv,p-2,p)

b_inv = 1
for i in range(1,b+1):
    b_inv *= i%p
    b_inv %= p
b_inv = pow(b_inv,p-2,p)

ans *= (a_inv*b_inv)%p

print(ans%p)

Submission status: Runtime Error

Solution code:
x,y = map(int,input().split())
p = 10**9+7
from math import factorial
if (x+y)%3 != 0:
    print(0)
    exit()



ans = 1
for i in range(0,x//2+2):
    j = x - 2*i
    if 2*j + i == y:
        a = i
        b = j
        break
print(((factorial(a+b)%p)*pow(factorial(a),-1,mod = p)*pow(factorial(b),-1,mod = p))%p)
'''
for i in range(1,a+b+1):
    ans *= i%p
ans %= p

a_inv = 1
for i in range(1,a+1):
    a_inv *= i%p
a_inv %= p
a_inv = pow(a_inv,p-2,p)

b_inv = 1
for i in range(1,b+1):
    b_inv *= i%p
b_inv %= p
b_inv = pow(b_inv,p-2,p)

ans *= (a_inv*b_inv)%p

print(ans)
'''

Submission status: Runtime Error

Solution code:
x,y = map(int,input().split())
mod = 10**9+7
def count_route(x,y):
  if x<=0 or y<=0:
    return 0
  elif x/y>2 or y/x>2:
    return 0
  elif x%y==0 and x//y==2:
    return 1
  elif y%x==0 and y//x==2:
    return 1
  else:
    return sum([count_route(x-1,y-2)%mod,count_route(x-2,y-1)%mod])
print(count_route(x,y))

Submission status: Runtime Error

Solution code:
x, y = list(map(int, input().split(' ')))
# K馬(右上のみ) -> パスカルの三角形っぽい
mmm = 1000000000 + 7
sss = x + y
if sss % 3 != 0:
    print(0)
    exit()
hoge = sss // 3
# 上にp, 右にq
# 2p + q = y
# 2q + p = x
# p + q = hoge
# p = y - hoge
# q = x - hoge
p =  y - hoge
q = x - hoge
#print(hoge, p, q)
if p < 0 or q < 0:  # 3 0 の時で Wrong Answer
    return 0

# 二項係数 mod [検索]
fac = []
inv = []
inv_fac = []
def init(n):
    fac.append(1)
    fac.append(1)
    inv.append(0)
    inv.append(1)
    inv_fac.append(1)
    inv_fac.append(1)
    for i in range(2, n):
        fac.append(fac[-1] * i % mmm)
        inv.append(mmm - inv[mmm%i] * (mmm // i) % mmm)
        inv_fac.append(inv_fac[-1] * inv[-1] % mmm)

def choice(a, b):
    if a < b:
        return 0
    return fac[a] * (inv_fac[b] * inv_fac[a-b] % mmm) % mmm

init(hoge * 2 + 1)
print(choice(hoge, p) % mmm)

# nCk - TLE でした
# def choice(a, b):
#     if a == b or b == 0:
#         return 0
#     if a < b:
#         return choice(b, a)
#     bunshi = a
#     t = min(b, (a-b))
#     bunbo = t
#     for i in range(1, t):
#         bunshi *= (a-i) % mmm
#         bunbo *= (t-i) % mmm
#     return bunshi // bunbo

Submission status: Runtime Error

Solution code:
x, y = list(map(int, input().split(' ')))
# K馬(右上のみ) -> パスカルの三角形っぽい
mmm = 1000000000 + 7
sss = x + y
if sss % 3 != 0:
    print(0)
    exit()
hoge = sss // 3
# 上にp, 右にq
# 2p + q = y
# 2q + p = x
# p + q = hoge
# p = y - hoge
# q = x - hoge
p =  y - hoge
q = x - hoge
#print(hoge, p, q)
# 二項係数 mod [検索]
fac = []
inv = []
inv_fac = []
def init(n):
    fac.append(1)
    fac.append(1)
    inv.append(0)
    inv.append(1)
    inv_fac.append(1)
    inv_fac.append(1)
    for i in range(2, n):
        fac.append(fac[-1] * i % mmm)
        inv.append(mmm - inv[mmm%i] * (mmm // i) % mmm)
        inv_fac.append(inv_fac[-1] * inv[-1] % mmm)

def choice(a, b):
    if a <= b:
        return 0
    return fac[a] * (inv_fac[b] * inv_fac[a-b] % mmm) % mmm

init(hoge + 1)
print(choice(hoge, p) % mmm)

# nCk - TLE
# def choice(a, b):
#     if a == b or b == 0:
#         return 0
#     if a < b:
#         return choice(b, a)
#     bunshi = a
#     t = min(b, (a-b))
#     bunbo = t
#     for i in range(1, t):
#         bunshi *= (a-i) % mmm
#         bunbo *= (t-i) % mmm
#     return bunshi // bunbo

Submission status: Runtime Error

Solution code:
def nCr(n, r, mod):
    x, y = 1, 1
    for r_ in range(1, r+1):
        x = x*(n+1-r_)%mod
        y = y*r_%mod
    return x*pow(y, mod-2, mod)%mod

x, y = map(int, input().split())
if (x+y)%3 or 2*x<y or 2*y<x:
    print(0)
else:
    print(nCr((x+y)//3,(2*x-y)//3, mod))

Submission status: Runtime Error

Solution code:
x,y=map(int,input().split())
if (x+y)%3!=0:
    print(0)
    exit()
if x<y:
    y=x
    x,y=y,x
if 2y<x:
    print(0)
    exit()
mod=10**9+7
a=(2y-x)//3
b=(2x-y)//3
mx=10**6*2
k=[1]*(mx+1)
def inv(n):
    return pow(n,mod-2,mod)
for i in range(mx):
    k[i+1]=k[i]*(i+1)%mod
ans=(k[w+h]*inv(k[w])*inv(k[h]))%mod
print(ans)

Submission status: Runtime Error

Solution code:
X,Y=map(int,input().split())
mod=10**9+7
if (X+Y)%3!=0:
  print(0)
else:
  N=int((2*Y-X)/3)
  M=int((2*X-Y)/3)
  if N==0 or M==0:
    print(1)
  else:
    List=[0 for i in range(N+M)]
    List[0]=1
    for i in range(N+M-1):
      List[i+1]=List[i]*(i+2)%mod
    print(List[N+M-1]*pow(List[N-1],mod-2,mod)*pow(List[M-1],mod-2,mod)%mod)

Submission status: Runtime Error

Solution code:
X,Y=map(int,input().split())
mod=10**9+7
if (X+Y)%3!=0:
  print(0)
else:
  N=int((2*Y-X)/3)
  M=int((2*X-Y)/3)
  List=[0 for i in range(N+M)]
  List[0]=1
  for i in range(N+M-1):
    List[i+1]=List[i]*(i+2)%mod
  print(List[N+M-1]*pow(List[N-1],mod-2,mod)*pow(List[M-1],mod-2,mod)%mod)

Submission status: Runtime Error

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

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

if 2 * min(X, Y) < max(X, Y):
    print(0)
    sys.exit()

def f(n, A):
    bunsi = reduce(lambda x, y: x*y%mod, range(n, n-A, -1))
    bunbo = reduce(lambda x, y: x*y%mod, range(1, A+1))
    return bunsi * pow(bunbo, mod-2, mod) % mod

ans = 0
r, d = 0, 0
if X == Y:
    r, d = X//3, Y//3
    ans = f(r+d, d)%mod
else:
    r = abs(X-Y) + ((X+Y) - 3*abs(X-Y))//6
    d = ((X+Y) - 3*abs(X-Y))//6
    ans = f(r+d, d)%mod

print(ans)

Submission status: Runtime Error

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

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

def f(n, A):
    bunsi = reduce(lambda x, y: x*y%mod, range(n, n-A, -1))
    bunbo = reduce(lambda x, y: x*y%mod, range(1, A+1))
    return bunsi * pow(bunbo, mod-2, mod) % mod

ans = 0
r, d = 0, 0
if X == Y:
    r, d = X//3, Y//3
    ans = f(r+d, min(r, d))%mod
else:
    r = abs(X-Y) + ((X+Y) - 3*abs(X-Y))//3
    d = ((X+Y) - 3*abs(X-Y))//3
    ans = f(r+d, d)%mod

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
mod = 10**9+7
X,Y = map(int,readline().split())
if X > Y:
    X,Y = Y,X
Z = X+Y
if Z % 3 == 0 and X <= Y <= 2*X:
    N = Z//3
    r = min(Y-X+1,N-Y+X-1)
else:
    print(0)
    sys.exit()
f = [1]*(N+1)
for i in range(1,N+1):
    f[i] = i * f[i-1] % mod
a = pow(f[r],mod-2,mod)
b = pow(f[N-r],mod-2,mod)
ans = f[N] * a * b % mod
print(ans)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc145/tasks/abc145_d


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

if (2*Y- X) % 3 or (2*X- Y) % 3:
    print(0)
    exit()

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

if x <= 0 or y =< 0:
    print(0)
    exit()

n = x + y
r = x


mod = 10**9 + 7
f = 1
for i in range(1, n + 1):
    f = f*i % mod
fac = f
f = pow(f, mod-2, mod)
facinv = [f]
for i in range(n, 0, -1):
    f = f*i % mod
    facinv.append(f)
facinv.append(1)

print(fac * facinv[r] * facinv[n - r] % mod)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc145/tasks/abc145_d

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

if (2*Y- X) % 3 or (2*X- Y) % 3:
    print(0)
    exit()

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

n = x + y
r = x


mod = 10**9 + 7
f = 1
for i in range(1, n + 1):
    f = f*i % mod
fac = f
f = pow(f, mod-2, mod)
facinv = [f]
for i in range(n, 0, -1):
    f = f*i % mod
    facinv.append(f)
facinv.append(1)

print(fac * facinv[r] * facinv[n - r] % mod)