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 sq(a, b, mod):  # aのb乗を剰余
    if b == 0:
        return 1
    elif b % 2 == 0:
        return sq(a, b // 2, mod)**2 % mod
    else:
        return sq(a, b - 1, mod) * a % mod
  
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

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

def nCk(n,k,mod):
  prev=1
  for i in range(1,min(k,n-k)+1):
    v=(prev * (n+1-i) % mod * modinv(i, mod) % mod)
    prev=v
  return prev

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

if (x+y)%3!=0:
  print(0)
else:
  n=int((x+y)/3)
  k=int((2*x-y)/3)
  print(nCk(n,k,mod))

Submission status: Runtime Error

Solution code:
import math

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

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

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

print(int(comb(a+b, a)%(1e9+7)))

Submission status: Runtime Error

Solution code:
from scipy.special import comb

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

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

print(int(comb(a+b, a, exact=True)%(1e9+7)))

Submission status: Runtime Error

Solution code:
from math import factorial

X, Y = [int(i) for i in input().split()]
n = 2 * X - Y
m = 2 * Y - X

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

def comb(a, b):
    return factorial(a) // (factorial(a - b) * factorial(b))

n, m = n / 3, m / 3

print(comb(n + m, n) % (10**9 + 7))

Submission status: Runtime Error

Solution code:
x,y=map(int,input().split())
a=(2*x-y)/3
b=(-x+2*y)/3
if (2*x-y)%3!=0:
    print(0)
    exit()
a=int(a)
b=int(b)
if a<0 or b<0:
  print(0):
    exit()
mod=10**9+7
if a==0 or b==0:
  print((a+b)%mod)
  exit()
def comb(x,y):
    s=x
    t=1
    for i  in range(1,y):
        s=(s*(x-i))%mod
    for j  in range(1,y+1):
        t=(t*j)%mod
    return (s*pow(t,mod-2,mod))%mod
print(comb(a+b,min(a,b)))

Submission status: Runtime Error

Solution code:
import sys
#import bisect
#from collections import deque
import math

def input():
    return sys.stdin.readline().rstrip('\n')


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

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

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

M = max((2*X-Y)//3, (2*Y-X)//3)
N = min((2*X-Y)//3, (2*Y-X)//3)

from scipy.special import comb
#print(comb(M+N,N) % (pow(10,9) + 7))
print(comb(M+N,N, exact=True)% (pow(10,9) + 7))

Submission status: Runtime Error

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

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def combi(n,r,mod=10**9+7):
    fac = [0]*(n+1)
    fac[0] = 1
    fac[1] = 1
    for i in range(2,n+1):
        fac[i] = fac[i-1] * i % mod
    return( ( fac[n] * modinv(fac[r]) )%mod * modinv(fac[n-r]) % mod)

if ( X + Y ) % 3 != 0:
    print(0)
else:
    n = X - (X + Y)//3
    m = (X + Y)//3 - n
    print(combi(n+m,m))

Submission status: Runtime Error

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

for i in range(2,X+1):
    for j in range(max(2,i//2),min(Y+1,i//2+1)):
        dp[i][j] = (dp[i-2][j-1] + dp[i-1][j-2]) % (10**9+7)

print(dp[X][Y])

Submission status: Runtime Error

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

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

print(dp[X][Y])

Submission status: Runtime Error

Solution code:
x,y=map(int,input().split())
import math
count = 0
if (x+y)%3==0:
  movement=(x+y)//3
  distance=abs(x-y)
  move1=(movement + distance)//2
  count = math.factorial(movement)//math.factorial(move1)
  
  count = count//math.factorial(movement-move1)

else:
  count = 0

print(count)

Submission status: Runtime Error

Solution code:
from functools import reduce
mod = 10**9+7

def P(n, k):
  return reduce(lambda x, y:x*y%mod, range(n-k+1, n+1))

def factorial(n):
  return 1 if n == 0 else P(n, n)

X, Y = map(int, input().split())
L, S = max(X, Y), min(Y, X)
if (S-(L-S))%3 != 0:
  print(0)
else:
  s = (S-(L-S))//3
  l = (S-(L-S))//3+(L-S)
  bunshi = factorial(s+l)
  bunbo = (factorial(s)*factorial(l))%mod
  print((bunshi*pow(bunbo,mod-2, mod))%mod)

Submission status: Runtime Error

Solution code:
from functools import reduce
mod = 10**9+7

def P(n, k):
  return reduce(lambda x, y:x*y%mod, range(n-k+1, n+1))

def factorial(n):
  return P(n, n)

X, Y = map(int, input().split())
L, S = max(X, Y), min(Y, X)
if (S-(L-S))%3 != 0 or S-(L-S) < 0:
  print(0)
else:
  s = (S-(L-S))//3
  l = (S-(L-S))//3+(L-S)
  bunshi = factorial(s+l)
  bunbo = (factorial(s)*factorial(l))%mod
  print((bunshi*pow(bunbo,mod-2, mod))%mod)

Submission status: Runtime Error

Solution code:
from functools import reduce
mod = 10**9+7

def P(n, k):
  return reduce(lambda x, y:x*y%mod, range(n-k+1, n+1))

def factorial(n):
  return P(n, n)

X, Y = map(int, input().split())
L, S = max(X, Y), min(Y, X)
if (S-(L-S))%3 != 0:
  print(0)
else:
  s = (S-(L-S))//3
  l = (S-(L-S))//3+(L-S)
  bunshi = factorial(s+l)
  bunbo = (factorial(s)*factorial(l))%mod
  print((bunshi*pow(bunbo,mod-2, mod))%mod)

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7

def make_fac_tables_mod_p(n, p):
  fac = [0] * (n+1)
  fac_inv = [0] * (n+1)
  mod_inv = [0] * (n+1)
  fac[0] = fac[1] = 1
  fac_inv[0] = fac_inv[1] = 1
  mod_inv[1] = 1
  for i in range(2, n+1):
    fac[i] = (fac[i-1] * i) % p
    mod_inv[i] = p - mod_inv[p % i] * (p // i) % p
    fac_inv[i] = fac_inv[i-1] * mod_inv[i] % p
  return fac, fac_inv

def nCk_mod_p(fac, fac_inv, n, k, p):
  return ((fac[n] * fac_inv[n-k]) % p) * fac_inv[k] % p

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

ans = 0
q, r = divmod(X+Y, 3)
if r == 0:
  n = q
  k = X - q
  fac, fac_inv = make_fac_tables_mod_p(n, MOD)
  ans = nCk_mod_p(fac, fac_inv, n, k, MOD)

print(ans)

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7
x, y = map(int, input().split())
if (x + y) % 3 != 0:
    print(0)
    exit()
a = 0
while y / x != 2 and x / y != 2:
    x -= 2
    y -= 1
    a += 1
b = min(x, y)

n = a + b
r = min(a, b)
x = 1
for i in range(n - r):
    x = x * (n - i) % mod
y = 1
for j in range(1, r):
    y = y * j
ans = x * pow(y, mod - 2, mod) % mod
print(ans)

Submission status: Runtime Error

Solution code:
def gho1(x):
  g=1
  for i in range(1,x+1):
    g*=i
  return g
def gho2(x):
  g=1
  for i in range(1,x+1):
    g*=i;g=g%(10**9+7)
  return g

q,w=map(int,input().split())
e,d=divmod((2*w-q),3)
r,f=divmod((2*q-w),3)

if d!=0 or f!=0:print(0)
else:
  print((gho(e+r)//(gho(e)*gho(r)))%(10*9+7))

Submission status: Runtime Error

Solution code:
mod = 10**9+7

def Pow(a, n):
    if n == 0: return 1
    if n%2 == 0:
        return (Pow(a, n//2))**2%mod
    else:
        return Pow(a, n-1)*a%mod

X, Y = map(int, input().split())
if (X+Y)%3 != 0:
    print(0)
else:
    n = (X+Y)//3
    if X < n or Y < n or X > 2*n or Y > 2*n:
        print(0)
    else:
        k = X-n
        R = [0] * n
        for i in range(1,n):
            R[i] = Pow(i, mod-2)
        cmb = [0]*n
        cmb[0] = 1
        for i in range(n-1):
            cmb[i+1] = ((cmb[i]*(n-i))%mod)*R[i+1]%mod
        print(cmb[k])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys

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

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

c = 0
check = 0
X_k, Y_k = X, Y
while c < max([X, Y]):
    if (X_k / 2) == Y_k:
        check = 1
        c_r = Y_k
        break
    else:
        X_k -= 1
        Y_k -= 2
        c += 1

N = c + c_r
r = min([c, c_r])
fact = [1, 1]
inv = [0, 1] 
factinv = [1, 1]
p = 10 ** 9 + 7
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(fact[N] * factinv[r] * factinv[N-r] % p)

Submission status: Runtime Error

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

c = 0
check = 0
X_k, Y_k = X, Y
while c < max([X, Y]):
    if (X_k / 2) == Y_k:
        check = 1
        c_r = Y_k
        break
    else:
        X_k -= 1
        Y_k -= 2
        c += 1

if ((X + Y) % 3) != 0:
    print(0)
else:
    N = c + c_r
    r = min([c, c_r])
    fact = [1, 1]
    inv = [0, 1] 
    factinv = [1, 1]
    p = 10 ** 9 + 7
    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(fact[N] * factinv[r] * factinv[N-r] % p)

Submission status: Runtime Error

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

c = 0
check = 0
X_k, Y_k = X, Y
while c < max([X, Y]):
    if (X_k / 2) == Y_k:
        check = 1
        c_r = Y_k
        break
    else:
        X_k -= 1
        Y_k -= 2
        c += 1

if check == 0:
    print(0)
else:
    N = c + c_r
    r = min([c, c_r])
    fact = [1, 1]
    inv = [0, 1] 
    factinv = [1, 1]
    p = 10 ** 9 + 7
    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(fact[N] * factinv[r] * factinv[N-r] % p)

Submission status: Runtime Error

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

c = 0
check = 0
X_k, Y_k = X, Y
while c < max([X, Y]):
    if (X_k / 2) == Y_k:
        check = 1
        c_r = Y_k
        break
    else:
        X_k -= 1
        Y_k -= 2
        c += 1

if check == 0:
    print(0)
else:
    N = c + c_r
    r = min([c, c_r])
    fact = [1, 1]
    inv = [0, 1] 
    factinv = [1, 1]
    p = 10 ** 9 + 7
    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(fact[N] * factinv[r] * factinv[N-r] % p)

Submission status: Runtime Error

Solution code:
from math import factorial
mod = 10**9 + 7
a, b = map(int, input().split())
if (a + b) % 3 != 0:
    print(0)
    exit()
x, y = (2 * a - b) // 3, (2 * b - a) // 3
mi, ma = min(x, y), max(x, y)
print(factorial(ma + mi) // (factorial(ma) * factorial(mi)) % mod)

Submission status: Runtime Error

Solution code:
import sys

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 = (int(x) for x in input().split())

if (X+Y) % 3 != 0:
  print(0)
  sys.exit()
  
n = (2*Y-X) / 3 if (2*Y-X) % 3 == 0 else -1
m = (2*X-Y) / 3 if (2*X-Y) % 3 == 0 else -1
if n < 0 or m < 0:
  print(0)
  sys.exit()
print(int(cmb(n+m,n)))

Submission status: Runtime Error

Solution code:
import sys

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 = (int(x) for x in input().split())

if (X+Y) % 3 != 0:
  print(0)
  sys.exit()
  
n = (2*Y-X) / 3
m = (2*X-Y) / 3
if n < 0 or m < 0:
  print(0)
  sys.exit()
  
print(int(cmb(n+m,n)))

Submission status: Runtime Error

Solution code:
import sys

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 = (int(x) for x in input().split())

if (X+Y) % 3 != 0:
  print(0)
  sys.exit()
  
n = (2*Y-X) / 3
m = (2*X-Y) / 3
if n < 0 or m < 0:
  print(0)
  sys.exit()
  
a = min(n,m)
print(int(cmb(n+m,a)))

Submission status: Runtime Error

Solution code:
#(a*x)をmで割った余りが1になるようなxを求める
#aで割ったときの余りはa^(-1)をかけた余りと同じ
#逆元a^(-1)を求める
#aとmが互いに素であることが条件

def gyakugen( a, m ):
  b = m
  x, y = 1, 0
  while b>0:
    q = a // b
    a, b = b, a-q*b
    x, y = y, x-q*y
  return x if x>0 else x+m


#(a/b)をmで割った余りを求める
#b^(-1)にaを掛けたものをmで割ればよい

def div_remainder(a,b,m):
    b_inv=gyakugen(b,m)
    a%=m
    return (a*b_inv)%m


#(a*b)をmで割った余りを求める

def multi_remainder(a,b,m):
    a%=m
    b%=m
    return (a*b)%m



#nPrをmで割った余りを求める(ただしn<m、mは素数)

def perm_remainder(n,r,m):
    if r>=1:
        return (perm_remainder(n-1,r-1,m)*n)%m
    else:
        return 1

#nCrをmで割った余りを求める(ただしn<m,mは素数)

def comb_remainder(n,r,m):
    r=min(r,n-r)
    return (perm_remainder(n,r,m)*gyakugen(perm_remainder(r,r,m),m))%m


x,y=map(int,input().split())
m=10**9+7
if (2*x-y)%3!=0 or (-x+2*y)%3!=0 or 2*x-y<0 or -x+2*y<0:
  ans=0
else:
  nx=(2*x-y)//3
  n=(x+y)//3
  ans=comb_remainder(n,nx,m)
print(ans)

Submission status: Runtime Error

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

dp = [[0]*(Y+1) for i in range(X+1)]
dp[0][0] = 1

for i in range(X+1) :
    for j in range(Y+1) :
        if i >= 1 and j >= 2 :
            dp[i][j] = (dp[i][j] + dp[i-1][j-2])%mod
        if i >= 2 and j >= 1 :
            dp[i][j] = (dp[i][j] + dp[i-2][j-1])%mod

print(dp[X][Y])

Submission status: Runtime Error

Solution code:
X,Y = map(int,input().split())
mod = 10**9+7
if (2*X-Y) % 3 != 0 or (2*Y-X) % 3 != 0:
    print(0)
    exit(0)
x,y = (2*Y-X)//3,(2*X-Y)//3
N = x+y
K = min(x,y)
def pow(x, n, mod):
    ret = 1
    while n>0:
        if (n&1):
            ret = (ret*x) % mod
        x = (x*x) % mod
        n >>= 1
    return ret
fact = [0]*(N+1)
fact[0] = 1
for i in range(1, N+1):
    fact[i] = (fact[i-1]*i) % mod
finv = [0]*(N+1)
finv[N] = pow(fact[N], mod-2, mod)
for i in range(N, 0, -1):
    finv[i-1] = (finv[i]*i) %mod

print((fact[x+y]*finv[x]*finv[y]) % mod)

Submission status: Runtime Error

Solution code:
X,Y = map(int,input().split())
mod = 10**9+7
if (2*X-Y) % 3 != 0 or (2*Y-X) % 3 != 0:
    print(0)
    exit(0)
x,y = (2*Y-X)//3,(2*X-Y)//3
N = x+y
K = min(x,y)
def pow(x, n, mod):
    ret = 1
    while n>0:
        if (n&1):
            ret = (ret*x) % mod
        x = (x*x) % mod
        n >>= 1
    return ret
fact = [None]*(N+1)
fact[0] = 1
for i in range(1, N+1):
    fact[i] = (fact[i-1]*i) % mod
finv = [None]*(N+1)
finv[N] = pow(fact[N], mod-2, mod)
for i in range(N, 0, -1):
    finv[i-1] = (finv[i]*i) %mod
def comb(n, k):
    return (fact[n]*finv[n-k]*finv[k]) % mod
print(comb(N,K))

Submission status: Runtime Error

Solution code:
X,Y = map(int,input().split())
mod = 10**9+7
if (2*X-Y) % 3 != 0 or (2*Y-X) % 3 != 0:
    print(0)
    exit(0)
x,y = (2*Y-X)//3,(2*X-Y)//3
N = x+y
K = x
def pow(x, n, mod):
    ret = 1
    while n>0:
        if (n&1):
            ret = (ret*x) % mod
        x = (x*x) % mod
        n >>= 1
    return ret
fact = [None]*(N+1)
fact[0] = 1
for i in range(1, N+1):
    fact[i] = (fact[i-1]*i) % mod
finv = [None]*(N+1)
finv[-1] = pow(fact[-1], mod-2, mod)
for i in range(N, 0, -1):
    finv[i-1] = (finv[i]*i) %mod
def comb(n, k):
    return (fact[n]*finv[n-k]*finv[k]) % mod
print(comb(N,K))

Submission status: Runtime Error

Solution code:
X,Y = map(int,input().split())
mod = 10**9+7
if (2*X-Y) % 3 != 0 or (2*Y-X) % 3 != 0:
    print(0)
    exit(0)
x,y = (2*Y-X)//3,(2*X-Y)//3
N = x+y
K = x
def pow(x, n, mod):
    ret = 1
    while n>0:
        if (n&1):
            ret = (ret*x) % mod
        x = (x*x) % mod
        n >>= 1
    return ret
fact = [None]*(N+1)
fact[0] = 1
for i in range(1, N+1):
    fact[i] = (fact[i-1]*i) % mod
finv = [None]*(N+1)
finv[-1] = pow(fact[-1], mod-2, mod)
for i in range(N, min(x,y)-1, -1):
    finv[i-1] = (finv[i]*i) %mod
def comb(n, k):
    return (fact[n]*finv[n-k]*finv[k]) % mod
print(comb(N,K))

Submission status: Runtime Error

Solution code:
from itertools import combinations
# from math import factorial as f
def cmb(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    """
    階乗テーブル、逆元の階乗テーブルを作成する
    """
    fac = [1, 1] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)

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

MOD = 10**9 + 7
def main():
    X, Y = map(int, input().split())
    a = 2 * X - Y
    if a % 3 != 0:
        print(0)
        return
    a = a // 3

    b = 2 * Y - X
    if b % 3 != 0:
        print(0)
        return
    b = b // 3

    total = a + b
    fac, ifac = make_tables(MOD, total)
    ans = cmb(a+b, min(a, b), MOD, fac, ifac)
    print(ans)


main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import math
x, y = map(int,input().split())

if (2 * y - x) % 3 != 0 and (2 * x - y) % 3 != 0:
    print(0)
else:
    a = (2 * y - x) // 3
    b = (2 * x - y) // 3
    ans = math.factorial(a + b) / (math.factorial(a) * math.factorial(b))
    print(int(ans) % (pow(10, 9) + 7))

Submission status: Runtime Error

Solution code:
import math
def solve():
    a,b,c = map(int, input().split())
    if (4 * a * b < (c-a-b)**2 and c-a-b>=0) or (4 * a * b > (c-a-b) ** 2 and c-a-b<0):
        print('Yes')
    else:
        print('No')
    
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import math
def solve():
    a,b,c = map(int, input().split())
    if (4 * a * b < (c-a-b)**2 and c-a-b>=0) \
        or (4 * a * b > (c-a-b) ** 2 and c-a-b<0):
        print('Yes')
    else:
        print('No')
    
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

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

def main():
    x,y=map(int,input().split())
    MOD=10**9+7
    if (x+y)%3!=0:
        print(0)
    else:
        n=int((x+y)/3)
        k=int((2*x-y)/3)
    a,b=1,1
    for i in range(k):
        a=(a*(n-i))%MOD
        b=(b*(1+i))%MOD
    ans=(a*pow(b,MOD-2,MOD))%MOD
    print(int(ans))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

def main():
    x,y=map(int,input().split())
    MOD=10**9+7
    if (x+y)%3!=0:
        print(0)
    else:
        n=int((x+y)/3)
        k=int((2*x-y)/3)
    a,b=1,1
    for i in range(k):
        a=(a*(n-i))%MOD
        b=(b*(1+i))%MOD
    ans=(a*pow(b,MOD-2,MOD))%MOD
    print(int(ans))
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#145_D
x,y=map(int,input().split())
mod=10**9+7
if (x+y)%3!=0:
    print(0)
else:
    n=(2*x-y)//3
    m=(2*y-x)//3
    f=[1 for i in range(m+n+1)]
    for i in range(2,m+n+1):
        f[i]=f[i-1]*i%mod
    print(f[m+n]*pow(f[n],mod-2,mod)*pow(f[m],mod-2,mod)%mod)

Submission status: Runtime Error

Solution code:
from math import factorial
mod = int(1e9) + 7
x, y = map(int, input().split())

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

n = (x+y)//3
a = x - n
b = y - n
r = min(a, b)
val1 = factorial(a+b) % mod
val2 = (factorial(r) % mod * factorial((a+b)-r) % mod) % mod
print(val1 * pow(val2,mod-2,mod) % mod)

Submission status: Runtime Error

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

if (X+Y)%3:
    print(0)
    exit()
n = (X+Y)//3
r = X-n
if not 0 <= r <= n:
    print(0)

MAXN = n
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
def comb(n,r):
    ret = 1
    for i in range(r):
        ret *= n-i
        ret *= inv[i+1]
        ret %= MOD
    return ret

print(comb(n,r))

Submission status: Runtime Error

Solution code:
from collections import deque
mod = 10 ** 9 + 7

x,y = map(int,input().split())
dp = [[0] * (y + 1) for _ in range(x + 1)]
dp[0][0] = 1

que = deque()
a = 0
b = 0
que.append([a,b])

while a != x or b != y:
    if not que:
        break
    else:
        a,b = que.popleft()
    if a + 1 <= x and b + 2 <= y:
        que.append([a + 1,b + 2])
        dp[a + 1][b + 2]+=dp[a][b]
        dp[a + 1][b + 2]%=mod
    if a + 2 <= x and b + 1 <= y:
        que.append([a + 2,b + 1])
        dp[a + 2][b + 1]+=dp[a][b]
        dp[a + 2][b + 1]%=mod

print(dp[x][y]%mod)

Submission status: Runtime Error

Solution code:
from functools import reduce
import sys
sys.setrecursionlimit(100000)
mod = 10**9+7
def mul(a,b):
    return a*b % mod
def cmb(n,r,mod):
    above = reduce(mul,range(n-r+1,n+1)) 
    below = reduce(mul,range(1,r+1)) 
    ans = above*pow(below,mod-2,mod) % mod
    if ans < 0:
        ans += mod
    return ans
x,y = map(int,input().split())
if 2*x-y < 0 or 2*y-x<0 or (2*x-y) % 3 != 0:
    print(0)
    exit()
a = (2*x-y)//3
b = (2*y-x)//3
print(cmb(a+b,min(a,b),mod))

Submission status: Runtime Error

Solution code:
from functools import reduce
mod = 10**9+7
def mul(a,b):
    return a*b % mod
def cmb(n,r,mod):
    above = reduce(mul,range(n-r+1,n+1)) 
    below = reduce(mul,range(1,r+1)) 
    ans = above*pow(below,mod-2,mod) % mod
    if ans < 0:
        ans += mod
    return ans
x,y = map(int,input().split())
if 2*x-y < 0 or 2*y-x<0 or (2*x-y) % 3 != 0:
    print(0)
    exit()
a = (2*x-y)//3
b = (2*y-x)//3
print(cmb(a+b,min(a,b),mod))

Submission status: Runtime Error

Solution code:
X,Y=map(int,input().split())
mod=10**9+7
"""2a+b=X "2b+a=Yを満たすabの並び替え"""
###a+b=(X+Y)/3,a-b=X-Y
###a,b>=0 かつ X+Y(mod3)==0
if (X+Y)%3!=0:
    print("0")##immposible
else:
    a=((X+Y)//3+(X-Y))/2
    b=((X+Y)//3-(X-Y))/2
    ###(a+b)combination a!
    a=min(a,b)
    b=max(a,b)
    c=1
    d=1
    if a>0 and b>=0:
        for i in range(a):
            c*=(a+b-i)
            c=c%mod
            d*=(i+1)
            d=d%mod
        print((c*pow(d,mod-2,mod))%mod)
    elif a==0 and b>0:
        for i in range(b):
            c*=(b-i)
            c=c%mod
        print(c)
    else:
        print("0")

Submission status: Runtime Error

Solution code:
X,Y=map(int,input().split())
mod=10**9+7
"""2a+b=X "2b+a=Yを満たすabの並び替え"""
###a+b=(X+Y)/3,a-b=X-Y
###a,b>=0 かつ X+Y(mod3)==0
if (X+Y)%3!=0:
    print("0")##immposible
else:
    a=((X+Y)//3+(X-Y))/2
    b=((X+Y)//3-(X-Y))/2
    ###(a+b)combination a!
    a=min(a,b)
    b=max(a,b)
    c=1
    d=1
    if a>0 and b>=0:
        for i in range(a):
            c*=(a+b-i)
            c=c%mod
            d*=(i+1)
            d=d%mod
        print((c*pow(d,mod-2,mod))%mod)
    elif a==0 and b>0:
        for i in range(b):
            c*=(b-i)
            c=c%mod
            print(c)
    else:
        print("0")

Submission status: Runtime Error

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

mod=10 ** 9 + 7
def binomial(n,k):
    x=1
    y=1
    for i in range(k):
        x=x*(n-i)%mod
        y=y*(i+1)%mod
    return x*power(y,mod-2)%mod

a=(2*X-Y)//3
b=(2*Y-X)//3

print(binomial(a+b,a)%mod)

Submission status: Runtime Error

Solution code:
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

""" 
参考:http://drken1215.hatenablog.com/entry/2018/06/08/210000
maximとmodを適宜設定。
あ入力忘れを考慮してあえて入力例通らないようにしておいたで。

combを使う前にcominit()を使う

"""
maxim = 10**6 + 10
mod = 10**9+7
fac = [None] * maxim
finv = [None] * maxim
inv = [None] * maxim

def cominit():
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1

    for i in range(2, maxim):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod

def com(n, k):
    if (n < k):
        return 0
    if (n < 0 or k < 0):
        return 0

    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


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

    # (x+y) // 3で何段目かわかる
    # パスカルの三角形で言うところのハジから何番目かがわかればいい

    # k段目の点は -x + 3*k上にある
    # 2*xが一番端にある
    
    k = (x+y) // 3
    # k段目の上端は (k, 2k)に存在する
    # 左から何番目かは2*k -yで求まる
    # 解は kC2*k-y

    cominit()
    m = (2*y-x)//3
    n = m+x-y
    
    print(comb(m+n,n))

    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

""" 
参考:http://drken1215.hatenablog.com/entry/2018/06/08/210000
maximとmodを適宜設定。
あ入力忘れを考慮してあえて入力例通らないようにしておいたで。

combを使う前にcominit()を使う

"""
maxim = 10**6 + 10
mod = 10**9+7
fac = [None] * maxim
finv = [None] * maxim
inv = [None] * maxim

def cominit():
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1

    for i in range(2, maxim):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod

def com(n, k):
    if (n < k):
        return 0
    if (n < 0 or k < 0):
        return 0

    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


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

    # (x+y) // 3で何段目かわかる
    # パスカルの三角形で言うところのハジから何番目かがわかればいい

    # k段目の点は -x + 3*k上にある
    # 2*xが一番端にある

    if y < x:
        y,x = x,y
        # パスカルの三角形は左右対称
    
    k = (x+y) // 3
    # k段目の上端は (k, 2k)に存在する
    # 左から何番目かは2*k -yで求まる
    # 解は kC2*k-y

    cominit()
    m = (2*x-y)//3
    n = y-x+m
    print(comb(n+m, m))


    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

""" 
参考:http://drken1215.hatenablog.com/entry/2018/06/08/210000
maximとmodを適宜設定。
あ入力忘れを考慮してあえて入力例通らないようにしておいたで。

combを使う前にcominit()を使う

"""
maxim = 10**6 + 10
mod = 10**9+7
fac = [None] * maxim
finv = [None] * maxim
inv = [None] * maxim

def cominit():
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1

    for i in range(2, maxim):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod

def com(n, k):
    if (n < k):
        return 0
    if (n < 0 or k < 0):
        return 0

    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


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

    # (x+y) // 3で何段目かわかる
    # パスカルの三角形で言うところのハジから何番目かがわかればいい

    # k段目の点は -x + 3*k上にある
    # 2*xが一番端にある

    if y < x:
        y,x = x,y
        # パスカルの三角形は左右対称
    
    k = (x+y) // 3
    # k段目の上端は (k, 2k)に存在する
    # 左から何番目かは2*k -yで求まる
    # 解は kC2*k-y

    cominit()
    print(comb(k, 2*k-y))


    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

""" 
参考:http://drken1215.hatenablog.com/entry/2018/06/08/210000
maximとmodを適宜設定。
あ入力忘れを考慮してあえて入力例通らないようにしておいたで。

combを使う前にcominit()を使う

"""
maxim = 10**6 + 10
mod = 10**9+7
fac = [None] * maxim
finv = [None] * maxim
inv = [None] * maxim

def cominit():
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1

    for i in range(2, maxim):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod

def com(n, k):
    if (n < k):
        return 0
    if (n < 0 or k < 0):
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


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

    # (x+y) // 3で何段目かわかる
    # パスカルの三角形で言うところのハジから何番目かがわかればいい

    # k段目の点は -x + 3*k上にある
    # 2*xが一番端にある

    if y < x:
        y,x = x,y
        # パスカルの三角形は左右対称
    
    k = (x+y) // 3
    # k段目の上端は (k, 2k)に存在する
    # 左から何番目かは2*k -yで求まる
    # 解は kC2*k-y

    cominit()
    print(comb(k, 2*k-y))


    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
x, y = map(int, input().split())
mod = 10**9+7 
def check(x, y):
  if (2*y-x)/3 < 0 or (2*x -y)/3 < 0:
    return False
  if (x+y)%3 != 0:
    return False
  return True

def comb(n, r, mod):
    r = min(r, n-r)
    x, y  = 1, 1
    for i in range(1, r+1):
      y =  y* i % mod
      x =  x* (n+1-i) % mod
    return int(x * pow(y, mod-2, mod) % mod)
  
if check(x, y):
  print(comb((2*y-x)//3+(2*x -y)/3, (2*y-x)//3, mod))
else:
  print(0)

Submission status: Runtime Error

Solution code:
X,Y = map(int,input().split())
if (X + Y) % 3 != 0:
    print(0)
    exit()
n = (-X+2*Y)//3
m = (2*X-Y)//3
if n < 0 or m < 0:
    print(0)
    exit()

mod = 10**9+7
mod_inv = [0, 1] + [0] * (min(n,m)+3)
for i in range(2, min(n,m)+5):
    mod_inv[i] = - mod_inv[mod % i] * (mod // i) % mod
def comod(n, r, mod):
    ans = 1
    for i in range(r):
        ans *= (n-i) % mod
        ans *= mod_inv[i+1]
        ans %= mod
    return ans
ans = comod(n+m,n,mod)
print(ans)