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: Wrong Answer

Solution code:
def ext_gcd(p, a):
  #require a, m be relative prime
  #m > a  
  if a == 0:
    return 1, 0
  else:
    x1, y1 = ext_gcd(a, p%a)
    y = x1 - y1 * int(p/a)
    x = y1
    return x, y

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

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

if n != int(n) or m != int(m) or n<0 or m<0:
  ans = 0
else:
   n = int(n)
   m = int(m)
   if n < m :
      c = m
      m = n
      n = c
   # (n+m!)/(n!)(m!) mod (1e9+7)
   ans = 1
   prime = 1000000007 
   for i in range(n+1,m+n+1):
        ans = int(ans * i) 
        ans = (ans % prime)
   for i in range(1, m+1):
      ori_inv = int(ext_gcd(prime, i)[1])
      while ori_inv < 0 :
        ori_inv += prime
      ans = int(ans * ori_inv)  
      ans = (ans % prime)
print(ans)

Submission status: Wrong Answer

Solution code:
def ext_gcd(p, a):
  #require a, m be relative prime
  #m > a  
  if a == 0:
    return 1, 0
  else:
    x1, y1 = ext_gcd(a, p%a)
    y = x1 - y1 * int(p/a)
    x = y1
    return x, y

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

n = (-1/3)*x + (2/3)*y
m = (-1/3)*y + (2/3)*x
f = 1
if f == 0:
  ans = 0
else:
   n = int(n)
   m = int(m)
   if n < m :
      c = m
      m = n
      n = c
   # (n+m!)/(n!)(m!) mod (1e9+7)
   ans = 1
   prime = 1000000007 
   for i in range(n+1,m+n+1):
        ans = int(ans * i) 
        ans = (ans % prime)
   for i in range(1, m+1):
      ori_inv = int(ext_gcd(prime, i)[1])
      while ori_inv < 0 :
        ori_inv += prime
      ans = int(ans * ori_inv)  
      ans = (ans % prime)
print(ans)

Submission status: Wrong Answer

Solution code:
def ext_gcd(p, a):
  #require a, m be relative prime
  #m > a  
  if a == 0:
    return 1, 0
  else:
    x1, y1 = ext_gcd(a, p%a)
    y = x1 - y1 * int(p/a)
    x = y1
    return x, y

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

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

if n != int(n) or m != int(m) or n<0 or m<0:
  ans = 0
else:
   n = int(n)
   m = int(m)
   if n < m :
      c = m
      m = n
      n = c
   # (n+m!)/(n!)(m!) mod (1e9+7)
   ans = 1
   prime = 1000000007 
   for i in range(n+1,m+n+1):
        ans = int(ans * i) 
        ans = (ans % prime)
   for i in range(1, m+1):
      ori_inv = int(ext_gcd(prime, i)[1])
      while ori_inv < 0 :
        ori_inv += prime
      ans = int(ans * ori_inv)  
      ans = (ans % prime)
print(ans)

Submission status: Wrong Answer

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

if (2 * x - y) % 3 != 0:
  print(0)
elif (2 * y - x) % 3 != 0:
  print(0)
elif 2 * x - y <= 0:
  print(0)
elif 2 * y - x <= 0:
  print(0)
else:
  m = (2 * x - y) // 3
  n = (2 * y - x) // 3
  mm = max(m, n)
  nn = min(m, n)
  for i in range(mm + 1, m + n + 1):
    ans *= i % mod
  for i in range(1, nn + 1):
    ans //= i % mod
  print(ans % mod)

Submission status: Wrong Answer

Solution code:
M=10**9+7
f=[1]
for j in range(1,10**6):f+=f[-1]*j%M,
i=[pow(f[-1],M-2,M)]
for j in range(1,10**6)[::-1]:i+=i[-1]*j%M,
x,y=map(int,input().split())
n,m=divmod(x+y,3)
print((m<1)*(y-n<=n)*f[n]*i[~n-n+y]*i[~y+n]%M)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

res = 0
mod = 10 ** 9 + 7

def IsPositiveAndInt(num):
    return int(num)-num == 0.0 and num > 0

# Copy from https://atcoder.jp/contests/abc145/submissions/8515099
def Comb(n, r, mod=mod):
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n+1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

if (X+Y) % 3 == 0:
    A = (2*X-Y) / 3
    B = (-X + 2*Y) / 3
    if IsPositiveAndInt(A) and IsPositiveAndInt(B):
        A, B = int(A), int(B)
        res = Comb(A+B, A, mod)
        
print(int(res))

Submission status: Wrong Answer

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

res = 0
mod = 10 ** 9 + 7

def IsPositiveAndInt(num):
    return int(num)-num == 0.0 and num > 0

# Copy from https://atcoder.jp/contests/abc145/submissions/8515099
def Comb(n, r, mod=mod):
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n+1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

if (X+Y) % 3 == 0:
    A = (2*X-Y) / 3
    B = (-X + 2*Y) / 3
    if IsPositiveAndInt(A) and IsPositiveAndInt(B):
        A, B = int(A), int(B)
        res = Comb(A+B, A, mod)
        
print(res)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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



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

if not (X+Y) % 3 == 0:
    print(0)
else:
    # 2n + m = X
    # n + 2m = Y
    n = (Y - 2*X) // -3
    m = X - (2 * n)
    if n < 0 or m < 0:
        print(0)
    else:
        print(n,m)
        print(cmb(n+m, n, mod))

Submission status: Wrong Answer

Solution code:
a,b=map(int,input().split())
if (a+b)%3!=0:
  print(0)
else:
  n=(a+b)//3
  r=(2*b-a)//3
  r=min(r,n-r)
  def comb(n, r):
    if r == 0:
      return 1
    if r == 1:
      return n
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i 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 *= numerator[k]
    return result
  ans=comb(n,r)
  print(ans%(10**9+7))

Submission status: Wrong Answer

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

N, T = map(int, readline().split())
m = map(int, read().split())
AB = sorted(zip(m, m))

dp = np.zeros(T, np.int64)

ans = 0
table = np.zeros(T, int)
for a, b in AB:
    ans = max(ans, max(table) + b)
    np.maximum(table[:-a] + b, table[a:], out=table[a:])
print(ans)

Submission status: Wrong Answer

Solution code:
def combinations(n1, n2):
    n1, n2 = max(n1, n2), min(n1, n2)
    a = 1
    for i in range(n2):
        a *= n1
        n1 -= 1
    return a

x, y = map(int, input().split())
if (x + y) % 3 != 0:
    print(0)
elif 2 * x < y or x > 2 * y:
    print(0)

else:
    n = (x + y) // 3
    r = y - n
    print((combinations(n, r)) % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

from math import factorial

MOD = 10 ** 9 + 7

def readInts():
  return [int(s) for s in input().split(" ")]

def combi(n, r):
  num = 1
  den1 = 1
  den2 = 1

  for i in range(1, n + 1):
    num = (num * i) % MOD

  for i in range(1, r + 1):
    den1 = (den1 * i) % MOD

  for i in range(1, n - r + 1):
    den2 = (den2 * i) % MOD

  return (num * pow(den1 * den2, MOD - 2, MOD)) % MOD

def solve():
  X, Y = readInts()

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

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

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

  return combi(a + b, min(a, b)) % MOD

def main():
  print(solve())

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

from math import factorial

MOD = 10 ** 9 + 7

def readInts():
  return [int(s) for s in input().split(" ")]

def combi(n, r):
  num = 1
  den = 1

  for i in range(r):
    num = (num * (n - i)) % MOD

  for i in range(1, n - r + 1):
    den = (den * i) % MOD

  return (num * pow(den, MOD - 2, MOD)) % MOD

def solve():
  X, Y = readInts()

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

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

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

  return combi(a + b, min(a, b)) % MOD

def main():
  print(solve())

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

from math import factorial

MOD = 10 ** 9 + 7

def readInts():
  return [int(s) for s in input().split(" ")]

def combi(n, r):
  num = 1
  den = 1

  for i in range(r):
    num = (num * (n - i)) % MOD

  for i in range(1, n - r + 1):
    den = (den * i) % MOD

  return (num * pow(den, MOD - 2, MOD)) % MOD

def solve():
  X, Y = readInts()

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

  if (2 * X - Y) % 3 > 0 or (2 * Y - X) % 3 > 0:
    return 0

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

  return combi(a + b, min(a, b)) % MOD

def main():
  print(solve())

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import sys
MOD = 10**9 + 7
list_size = 700000

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

x, y = map(int, input().split())
if (x+y)%3 != 0:
	print(0)
	sys.exit()
n = (x+y)//3
r = n - (n-x+y)//2
print(comb(n, r))

Submission status: Wrong Answer

Solution code:
def cmd(n,r,mod=10*9+7):
    fac = [0] * (n+1)
    finv = [0] * (n+1)
    inv = [0]*(n+1)

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

    if n < r: return 0
    if n < 0 or r < 0: return 0
    return (fac[n]*(finv[r]*finv[n-r]%mod)%mod)

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

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

i = (x+y)//3
j = x-i

print(cmd(i,j))

Submission status: Wrong Answer

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

if (2 * x - y) % 3 != 0:
  print(0)
elif (2 * y - x) % 3 != 0:
  print(0)
else:
  m = (2 * x - y) // 3
  n = (2 * y - x) // 3
  mm = max(m, n)
  nn = min(m, n)
  for i in range(mm + 1, m + n + 1):
    ans *= i
  for i in range(1, nn + 1):
    ans //= i
  print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
x,y = map(int,input().split())
mod = 10**9+7
if (x+y) % 3 != 0:
  print(0)
elif abs(y-x) > min(x,y)*2:
  print(0)
else:
  a = (x+y) // 3
  print(cmb(a,(a - (abs(x-y) // 2))) % mod)

Submission status: Wrong Answer

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

if 2*x-y>=0 and 2*y-x>=0 and x%3==-y%3:
    n=(2*x-y)//3
    m=(2*y-x)//3
    ans=1
    for i in range(1,m+1):
        ans = ans*(i+n)//i
        ans %= 10**9+7
else:
    ans=0
print(ans)

Submission status: Wrong Answer

Solution code:
X, Y = [int(_) for _ in input().split()]

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

def f(_X,_Y):
    y = (2 * _Y - _X) // 3
    x = (_X - y) // 2
    if x <= 0 or y <= 0:
        return None
    return x,y
tmp = f(Y,X) or f(Y,X)
if not tmp:
    print(0)
    exit()
x,y = tmp


kaijo = [0] * (X + Y + 10)
gyaku = [0] * (X + Y + 10)

kaijo[0] = 1
kaijo[1] = 1
MOD = 10 ** 9 + 7
for i in range(2, len(kaijo)):
    kaijo[i] = (i * kaijo[i - 1]) % MOD
gyaku[0] = 1
gyaku[1] = 1
for i in range(2, len(gyaku)):
    gyaku[i] = pow(kaijo[i], MOD - 2, MOD)


def nCm(n, m):
    return (kaijo[n] * gyaku[n - m] * gyaku[m]) % MOD


print(nCm(x + y, x))

Submission status: Wrong Answer

Solution code:
X, Y = [int(_) for _ in input().split()]

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

def f(_X,_Y):
    y = (2 * _Y - _X) // 3
    x = (_X - y) // 2
    if x <= 0 or y <= 0:
        return None
    return x,y
tmp = f(X,Y) or f(Y,X)
if not tmp:
    print(0)
    exit()
x,y = tmp


kaijo = [0] * (X + Y + 10)
gyaku = [0] * (X + Y + 10)

kaijo[0] = 1
kaijo[1] = 1
MOD = 10 ** 9 + 7
for i in range(2, len(kaijo)):
    kaijo[i] = (i * kaijo[i - 1]) % MOD
gyaku[0] = 1
gyaku[1] = 1
for i in range(2, len(gyaku)):
    gyaku[i] = pow(kaijo[i], MOD - 2, MOD)


def nCm(n, m):
    return (kaijo[n] * gyaku[n - m] * gyaku[m]) % MOD


print(nCm(x + y, x))

Submission status: Wrong Answer

Solution code:
X, Y = [int(_) for _ in input().split()]

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

y = (2 * Y - X) // 3
x = (X - y) // 2
if x <= 0 or y <= 0:
    print(0)
    exit()

kaijo = [0] * (X + Y + 10)
gyaku = [0] * (X + Y + 10)

kaijo[0] = 1
kaijo[1] = 1
MOD = 10 ** 9 + 7
for i in range(2, len(kaijo)):
    kaijo[i] = (i * kaijo[i - 1]) % MOD
gyaku[0] = 1
gyaku[1] = 1
for i in range(2, len(gyaku)):
    gyaku[i] = pow(kaijo[i], MOD - 2, MOD)


def nCm(n, m):
    return (kaijo[n] * gyaku[n - m] * gyaku[m]) % MOD


print(nCm(x + y, x))

Submission status: Wrong Answer

Solution code:
X, Y = [int(_) for _ in input().split()]

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

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

kaijo = [0] * (X + Y + 10)
gyaku = [0] * (X + Y + 10)

kaijo[0] = 1
kaijo[1] = 1
MOD = 10 ** 9 + 7
for i in range(2, len(kaijo)):
    kaijo[i] = (i * kaijo[i - 1]) % MOD
gyaku[0] = 1
gyaku[1] = 1
for i in range(2, len(gyaku)):
    gyaku[i] = pow(kaijo[i], MOD - 2, MOD)


def nCm(n, m):
    return (kaijo[n] * gyaku[n - m] * gyaku[m]) % MOD


print(nCm(x + y, x))

Submission status: Wrong Answer

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

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

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

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

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

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

if y > 2 * x or y < x / 2:
    print(0)
    sys.exit()

cnt = (x + y) // 3
# p = cnt // 2
p = (2 * x - y) // 3
print(cnt, p)

# Calclate cntCp
comb = Combination(1000000)
ans = comb(cnt, p)

print(ans)

Submission status: Wrong Answer

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

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

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

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

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

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

if y > 2 * x or y < x / 2:
    print(0)
    sys.exit()

cnt = (x + y) // 3
p = cnt // 2

# Calclate cntCp
comb = Combination(1000000)
ans = comb(cnt, p)

print(ans)

Submission status: Wrong Answer

Solution code:
x, y = map(int, input().split())
p = 10 ** 9 + 7
fac = [1]
finv = [1]
inv = [1]

if (x + y) % 3 == 0:
    n = (2 * x - y) // 3
    m = (2 * y - x) // 3
    for i in range(1, n + m):  # リストの中は1!スタートでn+m!まで入れている
        fac.append(fac[i - 1] * (i + 1) % p)
    for i in range(1, n):
        finv.append(finv[i - 1] * (i + 1) % p)
    for i in range(1, m):
        inv.append(inv[i - 1] * (i + 1) % p)
    # print(fac[-1],finv[-1],inv[-1])
    print(fac[-1] * ((finv[-1] * inv[-1]) % p) % p)


else:
    print(0)

Submission status: Wrong Answer

Solution code:
import math

M = 10 ** 9 + 7

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

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

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

if a > 0 and b > 0 and a % 3 ==  0 and b % 3 == 0:
	a /= 3
	b /= 3
	counter = comb(a+b,a)

result = counter % M
print(counter)
print(result)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7


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


def modpow(a, b, mod):
    ret = 1
    while b > 0:
        if b % 2 == 1:
            ret = ret * a % mod
        a = a * a % mod
        b //= 2
    return ret


def modcomb(n, r, mod):
    ret = 1
    for k in range(n, n - r, -1):
        ret = ret * k % mod
    for k in range(1, r + 1):
        ret = ret * modpow(k, mod - 2, mod) % mod
    return ret


X, Y = map(int, input().split())
if (2 * X - Y) % 3 == 0 and (2 * Y - X) % 3 == 0:
    A, B = (2 * X - Y) // 3, (2 * Y - X) // 3
    print(modcomb(A + B, A, MOD) % MOD)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7


def modpow(a, b, mod):
    ret = 1
    while b > 0:
        if b % 2 == 1:
            ret = ret * a % mod
        a = a * a % mod
        b //= 2
    return ret


X, Y = map(int, input().split())
if (2 * X - Y) % 3 == 0 and (2 * Y - X) % 3 == 0:
    A, B = (2 * X - Y) // 3, (2 * Y - X) // 3
    ans = 1
    for n in range(A + B, A, -1):
        ans = ans * n % MOD
    for n in range(1, B + 1):
        ans = ans * modpow(n, MOD - 2, MOD) % MOD
    print(ans % MOD)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
def combnk_mod(n, k, p):
    # pが素数かつaとpが互いに素であるとき
    # フェルマーの小定理より以下が成り立つ.
    # 1 / a = a ** (p - 2) (mod p)
    # これを使って (1 / k!) mod p を計算する.

    if  2 * k > n:
        k = n - k
    x = 1 # 分母にあたる数 1 / n! mod p
    y = 1 # 分子にあたる数. n! / (n - k)! mod p
    for i in range(1, k + 1):
        x *= pow(i, p - 2, p)
        y *= n - i + 1
        x %= p
        y %= p
    return (x * y) % p

MOD = 10 ** 9 + 7
x, y = map(int, input().split())
if (2 * x - y) % 3 > 0 or (2 * y - x) % 3 > 0:
    ans = 0
else:
    m = (2 * x - y) // 3
    n = (2 * y - x) // 3
    ans = combnk_mod(m + n, min(m, n), MOD)
print(ans)

Submission status: Wrong Answer

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())

b = max(x, y)
s = min(x, y)

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

ans = 0
if (x+y) % 3 != 0 or b / s > 2:
    print(ans)
else:
    print(cmb(a, b) % (10 ** 9 + 7) )

Submission status: Wrong Answer

Solution code:
from sys import stdin


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


def main():
    X, Y = [int(x) for x in stdin.readline().rstrip().split()]
    if (X + Y) % 3:
        print(0)
    else:
        m = (2 * X - Y) // 3
        n = X - 2 * m
        ans = cmb(n + m, min(n, m))
        print(ans % (10 ** 9 + 7))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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())

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

ans = 0
if (x+y) % 3 != 0:
    print(ans)
else:
    print(cmb(a, b) % (10 ** 9 + 7) )

Submission status: Wrong Answer

Solution code:
from sys import stdin

MAX = 10 ** 6
MOD = 10 ** 9 + 7
fac = [0] * MAX
finv = fac[:]
inv = fac[:]


def cmb_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        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 cmb(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 = [int(x) for x in stdin.readline().rstrip().split()]
    if (X + Y) % 3:
        print(0)
    else:
        n = (X * 2 - Y) // 3
        m = (X - n) // 2
        if n < 0 or m < 0:
            print(0)
        else:
            cmb_init()
            ans = cmb(n + m, min(n, m))
            print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin


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


def main():
    X, Y = [int(x) for x in stdin.readline().rstrip().split()]
    if (X + Y) % 3:
        print(0)
    else:
        n = (X * 2 - Y) // 3
        m = (X - n) // 2
        if n < 0 or m < 0:
            print(0)
        else:
            ans = cmb(n + m, min(n, m))
            print(ans % (10 ** 9 + 7))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

MAX = 10 ** 6
MOD = 10 ** 9 + 7
fac = [0] * MAX
finv = fac[:]
inv = fac[:]


def cmb_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        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 cmb(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():
    cmb_init()
    X, Y = [int(x) for x in stdin.readline().rstrip().split()]
    if (X + Y) % 3:
        print(0)
    else:
        n = (X * 2 - Y) // 3
        m = (X - n) // 2
        ans = cmb(n + m, min(n, m))
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
import functools

law = 10 ** 9 + 7
def mul_mod(x, y):
  return x * y % law

def prod_mod(seq):
  return functools.reduce(mul_mod, seq, 1)
#互いに素な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
  
def comb(n, k):
  return prod_mod(i for i in range(n - k + 1, n + 1)) * mod_inv(prod_mod(i for i in range(1, k + 1)), law) % law

if __name__ == "__main__":
  
  x, y = sorted(map(int, input().split()), reverse=True)
  
  if (x + y) % 3 != 0:
    print(0)
  else:
    print(comb((x + y) // 3, y - (x + y) // 3))

Submission status: Wrong Answer

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

MOD = 10**9+7  # type: int

def combi_count(n, r):
    x = 1
    y = 1
    for i in range(1, r+1):
        x = x * (n-i) % MOD
        y = y * i % MOD

    # nCr = n!/((n-r)!*r!) = (n!/(n-r)!) / r! 
    #     :=                 (    x    ) / y

    # x / y            % MOD
    # x * y^(-1)       % MOD
    # x * y**(MOD - 2) % MOD (from フェルマー定理)

    return x * pow(y, MOD-2, MOD) % MOD

def solve(X: int, Y: int):
    a = int((2*Y - X)/3)
    b = int((2*X - Y)/3)
    if ((2*Y - X)%3 != 0) and ((2*X - Y)%3 != 0):
        ans = 0
    else:
        ans = combi_count(a+b+1, min(a, b))
    print(ans)

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    X, Y = map(int, input().split())
    solve(X, Y)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

MOD = 10**9+7  # type: int

def combi_count(n, r):
    x = 1
    y = 1
    for i in range(1, r+1):
        x *= (n-i) % MOD
        y *= i % MOD

    # nCr = n!/((n-r)!*r!) = (n!/(n-r)!) / r! 
    #     :=                 (    x    ) / y

    # x / y            % MOD
    # x * y^(-1)       % MOD
    # x * y**(MOD - 2) % MOD (from フェルマー定理)

    return x * pow(y, MOD-2, MOD) % MOD

def solve(X: int, Y: int):
    a = int((2*Y - X)/3)
    b = int((2*X - Y)/3)
    if ((2*Y - X)%3 != 0) and ((2*X - Y)%3 != 0):
        ans = 0
    else:
        if (a<0) or (b<0):
            ans = 0
        else:
            ans = combi_count(a+b, min(a, b))
    print(ans)

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    X, Y = map(int, input().split())
    solve(X, Y)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

MOD = 10**9+7  # type: int

def combi_count(n, r):
    x = 1
    y = 1
    for i in range(1, r+1):
        x *= (n-i) % MOD
        y *= i % MOD

    # nCr = n!/((n-r)!*r!) = (n!/(n-r)!) / r! 
    #     :=                 (    x    ) / y

    # x / y            % MOD
    # x * y^(-1)       % MOD
    # x * y**(MOD - 2) % MOD (from フェルマー定理)

    return x * pow(y, MOD-2, MOD) % MOD

def solve(X: int, Y: int):
    a = int((2*Y - X)/3)
    b = int((2*X - Y)/3)
    if ((2*Y - X)%3 != 0) and ((2*X - Y)%3 != 0):
        ans = 0
    else:
        if (a<0) or (b<0):
            ans = 0
        else:
            ans = combi_count(a+b, min(a, b))
    print(int(ans%MOD))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(X, Y)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as ddict

if __name__ == "__main__":
  law = 10 ** 9 + 7
  
  dest_x, dest_y = sorted(map(int, input().split()), reverse=True)
  W = H = dest_x + 1
  
  num_pattern = ddict(int)
  
  num_pattern[0, 0] = 1
  
  stack = [(0, 0, 0, 0)]
  moves = [(1, 2), (2, 1)]
  
  while(stack):
    x, y, or_x, or_y = stack.pop(0)
    
    for dx, dy in moves:
      if x + dx != or_x and y + dy != or_y and 0 <= x + dx < W and 0 <= y + dy < H and x + dx >= y + dy:
        num_pattern[x + dx, y + dy] += num_pattern[x, y]
        stack.append((x + dx, y + dy, x, y))
      
  print(num_pattern[dest_x, dest_y] * 2 % law)
  pass