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:
X, Y = map(int, input().split())
mod = pow(10, 9) + 7

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
def combination(m, n):
    a = 1
    b = 1

    for i in range(m-n+1, m+1):
        a *= i

    for j in range(1, n+1):
        b *= j

    return a/b


mod = 10**9 + 7

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

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

print(combination(n, (n - (x-y)) / 2) % mod)

Submission status: Wrong Answer

Solution code:
import math

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

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

p = 10 ** 9 + 7
N = 10 ** 6
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)
    
a = (2*y-x)/3
b = (2*x-y)/3
if a != int(a) or b != int(b) or a <= 0 or b <= 0:
    print(0)
else:
    print(cmb(int(a+b), int(a), p))

Submission status: Wrong Answer

Solution code:
def framod(x,p=10**9+7):
  a=1
  for i in range(1,x+1):
    a = (a*i)%p
  return a
#############################################
X,Y=map(int,input().split())
p=10**9+7

if (X+Y)%3!=0:
  print(0)
else:
  a = (2*X-Y)//3
  b = (2*Y-X)//3
  t = a+b
  
  S=framod(t)
  T=pow(framod(a),p-2,p)
  U=pow(framod(b),p-2,p)
  
  print(((S*T)%p)*U%p)

Submission status: Wrong Answer

Solution code:
def framod(x,p=10**9+7):
  a=1
  for i in range(1,x+1):
    a = (a*i)%p
  return a
#############################################
X,Y=map(int,input().split())
p=10**9+7

if (X+Y)%3!=0:
  print(0)
else:
  a = (2*X-Y)//3
  b = (2*Y-X)//3
  t = a+b
  
  S=framod(t)
  T=pow(framod(a),p-2,p)
  U=pow(framod(b),p-2,p)
  
  print(S*T*U%p)

Submission status: Wrong Answer

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

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

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

mod = 10**9+7


def comb(n, r, mod):
    x=y=1
    for i in range(r):
        x *= n; y *= r
        x %= mod; y %= mod
        n -= 1; r -= 1
    return x * pow(y, mod - 2, mod) % mod

print(comb(n+m, n, mod))

Submission status: Wrong Answer

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

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

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

mod = 10**9+7


def comb(n, r, mod):
    x=y=1
    for i in range(r):
        x *= n; y *= r
        x %= mod; y %= mod
        n -= 1; r -= 1
    return x * pow(y, mod - 2, mod) % mod

print(comb(n+m, n, mod))

Submission status: Wrong Answer

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

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

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

mod = 10**9+7


def comb(n, r, mod):
    x=y=1
    for i in range(r):
        x *= n; y *= r
        x %= mod; y %= mod
        n -= 1; r -= 1
    return x * pow(y, mod - 2, mod) % mod

print(comb(n+m, n, mod))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
x,y = map(int,input().split())
mod = 10**9+7
s = 0
if x<0 or y<0:
  print(s)
  exit()
mx = 10**6
fact = [1]*(mx+1)
for i in range(mx):
  fact[i+1] = fact[i]*(i+1)%mod
def inv(n):
  return pow(n,mod-2,mod)
if (x%3==0 and y%3==0) or (x%3==1 and y%3==2) or (x%3==2 and y%3==1):
  n = int(2*x/3-y/3)
  m = int(-x/3 + 2*y/3)
  s += fact[n+m]*inv(fact[n])*inv(fact[m])%mod
  print(s)

Submission status: Wrong Answer

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

def cmb(n, r):
    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 )

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

if A == 0 and B == 0:
    print(0)
else:
    print(cmb(A + B, A))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): return k.join(list(map(str, lst)))
INF = float('inf')

def mcomb(n, k, mod):
    def mfac(l, r, mod):
        ans = l
        for i in reversed(range(r, l)):
            ans *= i
            ans %= mod
        return ans

    A = mfac(n,n-k+1,mod)
    B = mfac(k,1,mod)
    # B = mpow(B,mod-2,mod)
    B = pow(B, mod-2, mod)
    return A * B % mod

def solve():
    x, y = MI()
    if (x + y) % 3 != 0:
        print(0)
        return

    n = (x + y) // 3
    x -= n
    y -= n
    if x < 0 or y < 0:
        print(0)
        return

    mod = 1000000007
    ans = mcomb(x+y, x, mod)
    print(ans % mod)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

def cmb(n, r, mod):
    n_1 = 1
    n_2 = 1

    r = min(r, n-r)
    for i in range(1, r+1):
        n_1 = n_1 * i % mod
        n_2 = n_2 * (n - i + 1) % mod

    return (n_2 * pow(n_1, mod - 2, mod))%mod

mod = 10**9+7

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

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

if x < 0 or y < 0:
    print(0)
else:
    print(cmb(int(x+y), int(x), mod))

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

def cmb(n, r, mod):
    n_1 = 1
    n_2 = 1

    r = min(r, n-r)
    for i in range(1, r+1):
        n_1 = n_1 * i % mod
        n_2 = n_2 * (n - i + 1) % mod

    return (n_2 * pow(n_1, mod - 2, mod))%mod

mod = 10**9+7

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

A = np.matrix([[1, 2],[2, 1]])
B = np.matrix([[X],  [Y]])

a = np.linalg.inv(A)*B
x = a.getA1()[0]
y = a.getA1()[1]

if x < 0 or y < 0:
    print(0)
else:
    print(cmb(int(x+y), int(x), mod))

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

def cmb(n, r, mod):
    n_1 = 1
    n_2 = 1

    r = min(r, n-r)
    for i in range(1, r+1):
        n_1 = n_1 * i % mod
        n_2 = n_2 * (n - i + 1) % mod

    return (n_2 * pow(n_1, mod - 2, mod))%mod

mod = 10**9+7

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

A = np.matrix([[1, 2],[2, 1]])
B = np.matrix([[X],  [Y]])

a = np.linalg.inv(A)*B
x = a.getA1()[0]
y = a.getA1()[1]

if x.is_integer() == False or y.is_integer == False or x < 0 or y < 0:
    print(0)
else:
    print(cmb(int(x+y), int(x), mod))

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

def cmb(n, r, mod):
    n_1 = 1
    n_2 = 1

    r = min(r, n-r)
    for i in range(1, r+1):
        n_1 = n_1 * i % mod
        n_2 = n_2 * (n - i + 1) % mod

    return (n_2 * pow(n_1, mod - 2, mod))%mod

mod = 10**9+7

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

A = np.matrix([[1, 2],[2, 1]])
B = np.matrix([[X],  [Y]])

a = np.linalg.inv(A)*B
x = a.getA1()[0]
y = a.getA1()[1]

if x.is_integer() == False or y.is_integer == False:
    print(0)
else:
    print(cmb(int(x+y), int(x), mod))

Submission status: Wrong Answer

Solution code:
import sys
import math

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 )


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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	X,Y = inputMap()

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

	turn = (X+Y) // 3

	X -= turn
	Y -= turn

	print(combination(X+Y,Y))

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, 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

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


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

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	X,Y = inputMap()

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

	turn = (X+Y) // 3

	X -= turn
	Y -= turn

	print(combination(X+Y,X))

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, 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

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


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

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

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

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

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

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

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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



if (x+y)%30:
    print(0)
    exit()

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


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

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

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


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

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

#print(n+m,m)

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

Submission status: Wrong Answer

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

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

if x<3 and y<3:
    print(0)
    exit()

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

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

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

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


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

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

#print(n+m,m)

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

Submission status: Wrong Answer

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

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

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

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

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


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

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

#print(n+m,m)

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

Submission status: Wrong Answer

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

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

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

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

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


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

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

#print(n+m,m)

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
import collections

mod = 10 ** 9 + 7
x, y = list(map(int, input().split()))
if ((2 * y - x) % 3 != 0 or (2 * x - y) % 3 != 0):
    print(0)
    exit()

# 合計 a + b回動かす
a = (2*y-x)//3  # a回
b = (2*x-y)//3  # b回
# (a+b)!/a!b!
ans = 1
for i in range(1, a+b+1):
    ans = (ans * i) % mod
a_func = 1
for i in range(1, a+1):
    a_func = (a_func * i) % mod

inv_a_func = pow(a_func, mod-2, mod)
b_func = 1
for i in range(1, b+1):
    b_func = (b_func * i) % mod
inv_b_func = pow(b_func, mod-2, mod)
ans = (ans * inv_b_func) % mod
ans = (ans * inv_a_func) % mod
print(ans)

Submission status: Wrong Answer

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


def calc_comb(n, k, mod):
    '''
        n が大きい場合に使う
    '''
    a = 1
    b = 1
    for i in range(1,k+1):
        a *= i
        a %= mod
        b *= n
        n -= 1
        b %= mod
    return b * pow(a, mod-2, mod) % mod

if (X+Y) % 3 != 0:
    print(0)
else:
    total_move = (X+Y) // 3
    # 右に2つ動くことを選択しなければいけない回数
    right_move =  min(X,Y) - total_move
    if right_move * 2 + total_move - right_move in (X, Y):
        print(calc_comb(total_move, right_move, MOD))
    else:
        print(0)

Submission status: Wrong Answer

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


def calc_comb(n, k, mod):
    '''
        n が大きい場合に使う
    '''
    a = 1
    b = 1
    for i in range(1,k+1):
        a *= i
        a %= mod
        b *= n
        n -= 1
        b %= mod
    return b * pow(a, mod-2, mod) % mod

if (X+Y) % 3 != 0:
    print(0)
else:
    total_move = (X+Y) // 3
    # 右に2つ動くことを選択しなければいけない回数
    right_move =  min(X,Y) - total_move
    if right_move * 2 in (X, Y):
        print(calc_comb(total_move, right_move, MOD))
    else:
        print(0)

Submission status: Wrong Answer

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


def calc_comb(n, k, mod):
    '''
        n が大きい場合に使う
    '''
    a = 1
    b = 1
    for i in range(1,k+1):
        a *= i
        a %= mod
        b *= n
        n -= 1
        b %= mod
    return b * pow(a, mod-2, mod) % mod

if (X+Y) % 3 != 0:
    print(0)
else:
    n = (2 * X - Y) // 3
    m = Y - 2 * n
    print(calc_comb(n+m,m, MOD))

Submission status: Wrong Answer

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


def calc_comb(n, k, mod):
    '''
        n が大きい場合に使う
    '''
    a = 1
    b = 1
    for i in range(1,k+1):
        a *= i
        a %= mod
        b *= n
        n -= 1
        b %= mod
    return b * pow(a, mod-2, mod) % mod

if (X+Y) % 3 != 0:
    print(0)
else:
    total_move = (X+Y) // 3
    # 右に2つ動くことを選択しなければいけない回数
    right_move =  min(X,Y) - total_move
    print(calc_comb(total_move, right_move, MOD))

Submission status: Wrong Answer

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


def calc_comb(n, k, mod):
    '''
        n が大きい場合に使う
    '''
    a = 1
    b = 1
    for i in range(1,k+1):
        a *= i
        a %= mod
        b *= n
        n -= 1
        b %= mod
    return b * pow(a, mod-2, mod) % mod

if (X+Y) % 3 != 0:
    print(0)
else:
    total_move = (X+Y) // 3
    # 右に2つ動くことを選択しなければいけない回数
    right_move =  min(X,Y) - total_move
    print(calc_comb(total_move, min(total_move-right_move, right_move), MOD))

Submission status: Wrong Answer

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


def calc_comb(n, k, mod):
    '''
        n が大きい場合に使う
    '''
    a = 1
    b = 1
    for i in range(1,k+1):
        a *= i
        a %= mod
        b *= n
        n -= 1
        b %= mod
    return b * pow(a, mod-2, mod) % mod


if (X+Y) % 3 != 0:
    print(0)
else:
    total_move = (X+Y) // 3
    # 右に2つ動くことを選択しなければいけない回数
    right_move = X // 2
    print(calc_comb(total_move, right_move, MOD))

Submission status: Wrong Answer

Solution code:
import sys
import math

# import copy
# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
INF = sys.maxsize
MOD = 10 ** 9 + 7


# ===CODE===


class Combination:
    def __init__(self, mod):
        self.mod = mod
        self.fact = [1] * (2 * 10 ** 6 + 1)
        for i in range(1, 2 * 10 ** 6 + 1):
            self.fact[i] = i * self.fact[i - 1] % self.mod

    def nCr(self, n, k):
        a = self.fact[n] % self.mod
        b = (self.fact[k] * self.fact[n - k]) % self.mod
        c = pow(b, self.mod - 2, self.mod)
        return a * c % self.mod


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

if (2 * x - y) % 3 != 0 or (2 * y - x) % 3 != 0:
    print(0)
    exit(0)

yoko = (2 * x - y) // 3
tate = (2 * y - x) // 3

comb = Combination(MOD)
print(comb.nCr(yoko + tate, yoko))

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
import sys, math
from pprint import pprint
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

def combmod(n, k):
	p, q = 1, 1
	for i in range(1, k+1):
		p = p * (n-i+1) % mod
		q = q * i % mod
	return p * pow(q, mod-2, mod) % mod

X, Y = rl()

if (X+Y) % 3 != 0:
	print(0)
	exit()
if X == Y == 0:
	print(0)
	exit()
if X <= 0 or Y <= 0:
	print(0)
	exit()
n = (X+Y)//3
k = X-n
print(combmod(n,k))

Submission status: Wrong Answer

Solution code:
import numpy as np

MAX = 10**6+1
MOD = 10**9+7

fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

def COMinit():
    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 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


if __name__ == '__main__':
    x, y = map(int, input().split())
    if x + y == 0:
        res = 0
    else:
        n, m = map(int, np.linalg.solve([[1, 2], [2, 1]], [x, y]))
        if n < 0 and m < 0:
            res = 0
        else:
            COMinit()
            res = COM(n + m, n)
    print(res)

Submission status: Wrong Answer

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

MAX = 10**6+1
MOD = 10**9+7
fac = [1]
for i in range(1, MAX):
    fac.append(fac[i-1] * i % MOD)

if (x % 3 == 0 and y % 3 == 0) or (min(x % 3, y % 3) == 1 and max(x % 3, y % 3) == 2):
    xx, yy = max(x, y), min(x, y)
    a = b = 0
    while not xx == yy:
        xx -= 2
        yy -= 1
        a += 1
    a += xx // 3
    b += yy // 3
    print(fac[a+b] * pow(fac[a]*fac[b], MOD-2, MOD) % MOD)
else:
    print(0)

Submission status: Wrong Answer

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

MAX = 10**6+1
MOD = 10**9+7
fac = [0, 1]
for i in range(2, MAX):
    fac.append(fac[i-1] * i % MOD)

if (x % 3 == 0 and y % 3 == 0) or (min(x % 3, y % 3) == 1 and max(x % 3, y % 3) == 2):
    xx, yy = max(x, y), min(x, y)
    a = b = 0
    while not xx == yy:
        xx -= 2
        yy -= 1
        a += 1
    a += xx // 3
    b += yy // 3
    print(fac[a+b] * pow(fac[a]*fac[b], MOD-2, MOD) % MOD)
else:
    print(0)

Submission status: Wrong Answer

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

def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def comb(n, r, mod = 10**9 + 7):
    return ( framod(n,mod) * pow(framod(n-r,mod),mod-2,mod ) * pow(framod(r,mod),mod-2,mod))
X,Y=map(int,input().split())
if X % 3 == 0 and Y % 3 ==0:
  s,t= ( 2*X - Y ) // 3 , (2*Y - X) // 3
  print(comb(s+t,s) % mod)
else:
  print(0)