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:
import sys
sys.setrecursionlimit(10**9)
import time

t1 = time.time()

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

nagasa = kyori // 3
dif = x - y

n_x = (nagasa + dif) // 2
n_y = nagasa - n_x

print(nagasa,n_x,n_y)

if x != n_x * 2 + n_y * 1 or y != n_x * 1+ n_y*2:
    print(0)
    exit()

if n_x < 0 or n_y < 0:
    print(0)
    exit()
#H, W, A, B = map(int, raw_input().split())

def kj(n, x,y, mod):
    #if ( r<0 or r>n ):
     #   return 0
    #r = min(r, n-r)
    return g1[n] * g2[x] * g2[y] % mod

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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


a = kj(nagasa,n_x,n_y,mod)
print(a)

Submission status: Wrong Answer

Solution code:
X,Y=map(int,input().split())
N=10**9+7
def kaizyou(n):
    l=[1]
    for i in range(1,n+1):
        ll=(l[i-1]*i)%N
        l.append(ll)
    return l
def modpow(a,n,p):#a^n mod p ,O(log n)
    res=1
    while n>0:
        if n&1:#１とのビット論理積が１、つまり奇数
            res=res*a%p
        a=a*a%p
        n>>=1
        #ビットの右シフト_2進数表記のnを小数点を固定して右に１桁ずらす_１桁小さくなる
    return res
if (2*X-Y)%3==0 and (2*Y-X)%3==0 and 2*X-Y>0 and 2*Y-X>0:
    nx=int((2*X-Y)/3)
    ny=int((2*Y-X)/3)
    l=kaizyou(nx+ny)
    nxdv=modpow(l[nx],N-2,N)
    nydv=modpow(l[ny],N-2,N)
    ans=l[-1]*nxdv%N
    ans=ans*nydv%N
    print(ans)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
MOD = 1000000007
def solve(x, y):
    from math import factorial
    if (x + y) % 3 != 0:
        return 0
    m = (x + y) // 3
    n = m 
    k = x - m
    if n - k < k:
        k = n - k
    return C2(n, k)

def C2(n, k):
    d = 1
    for i in range(n-k+1, n+1):
        d *= i 
        d %= MOD
    r = 1
    for i in range(1, k+1):
        r *= i 
        r %= MOD
    return (d * modinv(r, MOD)) % MOD

def modinv(a, m):
    b, u, v = m, 1, 0
    while b != 0:
        t = a // b
        a -= t * b
        a, b = b, a

        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u

a = 12345678900000
b = 100000
a %= MOD
#print(a * modinv(b, MOD) % MOD)

x, y = map(int, input().split())
if x > y:
    x, y = y, x
answer = solve(x, y)
#print(dp)
print(answer)

Submission status: Wrong Answer

Solution code:
import random
MOD = 10 ** 9 + 7
fac = [1] * (10 ** 6 * 2 + 2)
for i in range(len(fac) - 1):
    fac[i + 1] = fac[i] * (i + 1) % MOD
x, y = map(int, input().split())
t = min(x, y) // 3
if (2 * x - y) % 3 or (2 * y - x) % 3:
    print(0)
    exit(0)
a, b = (2 * x - y) // 3, (2 * y - x) // 3
k = max(a, b)
n = a + b
print((fac[n] * pow(fac[n - k], MOD - 2, MOD)
       * pow(fac[k], MOD - 2, MOD)) % MOD)

Submission status: Wrong Answer

Solution code:
def mod_pow(a, x, p):
    res = 1
    while x > 0:
        if x % 2 != 0:
            res = (res * a) % p
        a = (a * a) % p
        x //= 2
    return res


def mod_inv(a, p):
    return mod_pow(a, p-2, p)


def mod_binomial(n, k, p):
    numerator = 1
    for i in range(k):
        numerator = (numerator * (n-i)) % p

    denominator = 1
    for i in range(1, k+1):
        denominator = (denominator * i) % p

    return (numerator * mod_inv(denominator, p)) % p


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

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

    print(mod_binomial(a+b, a, 10**9+7))

Submission status: Wrong Answer

Solution code:
x,y = map(int,input().split())
n = [[0 for i in range(y+1)] for i in range(x+1)]
for i in range(x+1):
    for j in range(y+1):
        if (i-2 >= 0 and j-1 >= 0) and (i-1 >= 0 and j-2 >= 0):
            n[i][j] = n[i-1][j-2] + n[i-2][j-1] + 1
        elif (i-2 >= 0 and j-1 >= 0) and (i-1 < 0 or j-2 < 0):
            n[i][j] = n[i-1][j-2] + 1
        elif (i-2 < 0 and j-1 < 0) and (i-1 >= 0 and j-2 >= 0):
            n[i][j] = n[i-2][j-1] + 1
print(n[x][y])

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7


def pwr(p, q):
    if q == 1:
        return p%mod
    elif q % 2 == 0:
        return (pwr(p, q//2)%mod)**2%mod
    else:
        return (pwr(p, q//2)%mod)**2*p%mod

x, y = map(int,input().split())
if (2*x-y)%3 != 0 or (2*y-x)%3 != 0:
    print(0)
else:
    n = (2*x-y)//3
    m = (2*y-x)//3
    if m == 0 or n == 0:
        print(1)
    else:
        s1 = 1
        s2 = 1
        for i in range(m+1, n+m+1):
            s1 *= i
            s1 %= mod
        for i in range(n):
            s2 *= (i+1)
            s2 %= mod

        print(s1*pwr(s2, mod-2)%mod)

Submission status: Wrong Answer

Solution code:
import random
MOD = 10 ** 9 + 7
fac = [1] * (10 ** 6 * 2 + 2)
for i in range(len(fac) - 1):
    fac[i + 1] = fac[i] * (i + 1) % MOD
x, y = map(int, input().split())
t = min(x, y) // 3
if (2 * x - y) % 3 or (2 * y - x) % 3:
    print(0)
a, b = (2 * x - y) // 3, (2 * y - x) // 3
k = max(a, b)
n = a + b
print((fac[n] * pow(fac[n - k], MOD - 2, MOD)
       * pow(fac[k], MOD - 2, MOD)) % MOD)

Submission status: Wrong Answer

Solution code:
x, y = map(int, input().split())
MOD = 1000000007
# 拡張ユークリッド互除法
# gcd(a,b) と ax + by = gcd(a,b) の最小整数解を返す
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

if x>y:
    x,y = y,x
    
both = x//3

x -= both*3
y -= both*3

if 2*x!=y:
    print(0)
else:
    r = both
    l = both + x


    ret = 1
    for i in range(1,l+r+1):
        ret *= i
        ret %= MOD
    for i in range(1,l+1):
        ret = ret * modinv(i, MOD) % MOD 
    for i in range(1,r+1):
        ret = ret * modinv(i, MOD) % MOD 
    print(ret)

Submission status: Wrong Answer

Solution code:
import math

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

a = 0
b = 0
for i in range(y//2+1):
    if (x-i)/2 == y-2*i:
        a = i
        b = y-2*i
        break
print(a,b)
if a == 0 and b == 0:
    print(0)
else:    
    print((math.factorial(a+b)//(math.factorial(a)*math.factorial(b)))%(10**9+7))

Submission status: Wrong Answer

Solution code:
import sys
G = list(map(int, input().split()))
total = G[0] + G[1]
if total % 3 != 0:
  print(0)
  sys.exit(0)

total //= 3
dis = G[0] - total

mod = 10 ** 9 + 7
fact = [1]
fact_inv = [1]
for i in range(10**6):
    new_fact = fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))

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

print(mod_comb_k(total, dis, mod))

Submission status: Wrong Answer

Solution code:
import sys


def alg_combination_mod(n, r, mod):
    r = min(n - r, r)
    if r == 0:
        return 1
    else:
        denominator = 1
        for i in range(n, n - r, -1):
            denominator = (denominator * i) % mod
        molecule = 1
        for i in range(1, r + 1):
            molecule = (molecule * i) % mod
        return denominator * pow(molecule, mod - 2, mod) % mod


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    x, y = list(map(int, readline().split()))
    if x / y == 2 or y / x == 2:
        print(1)
    else:
        cnt = min(x // 3, y // 3)
        x -= cnt * 3
        y -= cnt * 3
        xcnt = 0
        ycnt = 0
        if x == 0 and y == 0:
            xcnt = cnt
            ycnt = cnt
        elif x % 2 == 0 and y % 2 == 0:
            if x != 0 and y / x == 2:
                xcnt = cnt + x
                ycnt = cnt
            elif y != 0 and x / y == 2:
                xcnt = cnt
                ycnt = cnt + y
        else:
            print(0)
            exit()
        print(alg_combination_mod(xcnt + ycnt, xcnt, mod))


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import math

def main():

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

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

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

    mod = pow(10, 9) + 7
    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]

    for i in range(2,  n+m+1):

        g1.append( ( g1[-1] * i ) % mod )
        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )

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

    return cmb(n+m, n, mod)


if __name__ == '__main__':
    print(main())

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

#(3,3)セット回数 + 残り
X,Y = map(int,input().split())
if(X > Y): 
  A,B = Y,X
else:  
  A,B = X,Y
  
# A<=B
r = A//3
a,b = A-(A//3)*3 , B-(A//3)*3

if((a == 1)and(b == 2)):
 n = 2*r+1
 r = r + 1
 #ans = cmb(n,r)%(10**9 + 7)
 mod = 10**9+7 #出力の制限
 N = n
 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 )
 ans = cmb(n, r, mod)

elif((a == 2)and(b == 4)):
 n = 2*r+2
 r = r + 2
 mod = 10**9+7 #出力の制限
 N = n
 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 )
 ans = cmb(n, r, mod)
  
  
elif((a == 0)and(b == 0)):
 n = 2*r
 mod = 10**9+7 #出力の制限
 N = n
 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 )
 ans = cmb(n, r, mod)


elif((a == 0)and(B == 2*A)):
 ans = 1
else:
 ans = 0

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


X, Y = map(int, input().split())
X = min(X, Y)
Y = max(X, Y)
l = [(0, 0), (1, 2), (2, 1)]
if X * 2 < Y or Y * 2 < X:
    print(0)
else:
    x = X % 3
    y = Y % 3
    if not (x, y) in l:
        print(0)
    else:  # nCr
        n = (X + Y) // 3
        r = (n - (Y - X)) // 2
        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)
        print(cmb(n, r, mod))

Submission status: Wrong Answer

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

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

import itertools
p = len(list(itertools.combinations(range(x + y), x))) % (10 ** 9 + 7)
print(p)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod
def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

x,y=map(int,input().split())
if (x>2*y and 2*x<y) or (x+y)%3!=0:
    #print(1)
    print(0)
else:
    print(comb((x+y)//3, min(x,y)-(x+y)//3,10**9+7))

Submission status: Wrong Answer

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

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):
    _X = 2*X - Y
    _Y = -X + 2*Y
    if _X%3!=0 or _Y%3!=0:
        return 0

    X = _X//3
    Y = _Y//3
    return cmb(X+Y, X)

print(main(X, Y)%MAX)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

X, Y = MAP()

x, y = 0, 0
while (X!=0 or Y!=0):
	if X * 2 == Y:
		x += x
		break

	elif Y * 2 == X:
		y += Y
		break

	elif X >= 3 and Y >= 3:
		x += 1
		y += 1
		X -= 3
		Y -= 3
	else:
		if X-1 == 0 and Y-2==0:
			y += 1
			break
		elif X-2 == 0 and Y-4==0:
			y += 2
			break

		elif X-2==0 and Y-1==0:
			x += 1
			break
		elif X-4==0 and Y-2==0:
			x += 2
			break
		else:
			print(0)
			sys.exit()

H = 10**6//2
W = 10**6//2
factorial = [1]
for i in range(1, H+W):
	factorial.append(factorial[i-1] * i % mod)


def power(x, y):
	if y == 0:
		return 1
	elif y == 1:
		return x % mod
	elif y % 2 == 0:
		return power(x, int(y/2)) ** 2 % mod
	else:
		return power(x, int((y-1)/2)) ** 2 * x % mod
def C(n, r):
	return (((factorial[n] * x_inv[r]) % mod) * x_inv[n-r]) % mod

x_inv = [0] * (H+W)
x_inv[-1] = power(factorial[-1], mod-2)
for i in range(H+W-2, -1, -1):
	x_inv[i] = x_inv[i+1] * (i+1) % mod

if x == 0 or y == 0:
	print(1)
else:
	print(C(x+y, y))

Submission status: Wrong Answer

Solution code:
x,y=map(int,input().split())
if (x+y)%3!=0:
  print(0)
else:
  n=(x+y)//3
  if x<n:
    print(0)
  else:
    def modinv(a, mod=10**9+7):
      return pow(a, mod-2, mod)
    def comb(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 
    print(comb(n,x-n)%(10**9+7))

Submission status: Wrong Answer

Solution code:
import math

def main():

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

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

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

    mod = pow(10, 9) + 7
    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]

    for i in range(2,  n+m+1):

        g1.append( ( g1[-1] * i ) % mod )
        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )

    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

    return cmb(n+m, n, mod)


if __name__ == '__main__':
    print(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 = 0
b = 0

if (2*Y-X)%3 == 0 and (2*X-Y)%3 == 0:
    a = (2*X-Y)//3
    b = (2*Y-X)//3



if a < 0 or b < 0:
    ans = 0
else:
    ans = cmb(a+b, b)
print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
x, y = map(int, input().split())
if (x + y) % 3 == 0:
    n = x + y
    ans = n - 1 - (n // 3 - 1) * 2
    print(ans % (10**9 + 7))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys
import math
sys.setrecursionlimit(10**9)

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

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 )

if (X + Y) % 3 == 0:
    n_plus_m = (X + Y) // 3
    if X > Y:
        diff = X - Y
    else:
        diff = Y - X
    n = (n_plus_m // 2) + diff
    print(cmb(n_plus_m, n, mod))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
def mod_pow(a, x, p):
    res = 1
    while x > 0:
        if x % 2 != 0:
            res = (res * a) % p
        a = (a * a) % p
        x //= 2
    return res


def mod_inv(a, p):
    return mod_pow(a, p-2, p)


def mod_binomial(n, k, p):
    numerator = 1
    for i in range(k):
        numerator = (numerator * (n-i)) % p

    denominator = 1
    for i in range(1, k+1):
        denominator = (denominator * i) % p

    return (numerator * mod_inv(denominator, p)) % p


X, Y = map(int, input().split())
a = (2*Y-X) / 3
b = (2*X-Y) / 3

if a != int(a) or b != int(b):
    print(0)
    exit()

a = int(a)
b = int(b)
N = a + b

print(mod_binomial(N, a, 10**9+7))

Submission status: Wrong Answer

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

# (1, 2) * a + (2, 1) * b = (x, y)
#
# a + 2 * b = x
# 2 * a + b = y
# b = y - 2 * a
# a = x - 2 * b
# b = y - 2 * (x - 2 * b)
#   = y - 2 * x + 4 * b
# 3 * b = - y + 2 * x

b = (-y + 2*x)# / 3
if b % 3 != 0:
    print(0)
    sys.exit()
b //= 3
a = x - 2 * b
# (a + b)! / (a! * b!)
if a < 0:
    print(0)
    sys.exit()
if a == 0 or b == 0:
    print(1)
    sys.exit()

def fact(n):
    ans = n
    for i in range(1, n):
        ans *= i
        if ans >= M:
            ans %= M
    return ans

def pm(value, n):
    if n == 0:
        return 1
    if n % 2:
        return pm(value, n - 1) * value % M
    else:
        return pm(value, n // 2) ** 2 % M

# A * B ^ (M-2)
print(fact(a + b) * pm(fact(a) * fact(b) % M, M - 2) % M)

Submission status: Wrong Answer

Solution code:
x,y = map(int,input().split())
if x > y*2 or y > x*2 or (x*y)%3 != 0:
  print(0)
  exit()
n = (x+y)//3
r = min(x-n,2*n-x)

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 )

print(cmb(n,r,mod))

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 = 0
b = 0

if (2*Y-X)%3 == 0 and (2*X-Y)%3 == 0:
    a = (2*X-Y)//3
    b = (2*Y-X)//3

if a <= 0 or b <= 0:
    ans = 0
else:
    ans = cmb(a+b, b)
print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

X, Y = MAP()

x, y = 0, 0
while (X!=0 or Y!=0):
	if X >= 3 and Y >= 3:
		x += 1
		y += 1
		X -= 3
		Y -= 3
	else:
		if X-1 == 0 and Y-2==0:
			y += 1
			break
		elif X-2 == 0 and Y-4==0:
			y += 2
			break

		elif X-2==0 and Y-1==0:
			x += 1
			break
		elif X-4==0 and Y-2==0:
			x += 2
			break
		else:
			print(0)
			sys.exit()

H = 10**6//2
W = 10**6//2
factorial = [1]
for i in range(1, H+W):
	factorial.append(factorial[i-1] * i % mod)


def power(x, y):
	if y == 0:
		return 1
	elif y == 1:
		return x % mod
	elif y % 2 == 0:
		return power(x, int(y/2)) ** 2 % mod
	else:
		return power(x, int((y-1)/2)) ** 2 * x % mod
def C(n, r):
	return (((factorial[n] * x_inv[r]) % mod) * x_inv[n-r]) % mod

x_inv = [0] * (H+W)
x_inv[-1] = power(factorial[-1], mod-2)
for i in range(H+W-2, -1, -1):
	x_inv[i] = x_inv[i+1] * (i+1) % mod

if x == 0 or y == 0:
	print(1)
else:
	print(C(x+y, y))

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7


def main():
    X, Y = map(int, input().split())
    if X > Y:
        tmp = X
        X = Y
        Y = tmp
    if (X - (Y-X)) % 3 != 0:
        print("0")
        exit()
    Xleft = (X-(Y-X)) // 3
    Yleft = (X-(Y-X)) // 3 + (Y-X)//2
    Xkaijou = 1

    for i in range(1, Xleft+1):
        Xkaijou = (Xkaijou*i)%MOD
    Ykaijou = Xkaijou
    for i in range(Xleft+1, Yleft+1):
        Ykaijou = (Ykaijou*i)%MOD
    zenbu = Ykaijou
    p = 0
    for i in range(Yleft+1, Xleft+Yleft+1):
        zenbu = (zenbu*i)%MOD
        p += 1
    ans = (zenbu * (pow(Xkaijou,MOD-2,MOD)*pow(Ykaijou,MOD-2,MOD)%MOD)%MOD)
    print(int(ans))
    # print(Xkaijou, Ykaijou, zenbu)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

MOD = 10 ** 9 + 7

X, Y = map(int, input().split())
maxf = 2 * 10 ** 6 + 100

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

if 2 * a + b != X or a + 2 * b != Y:
    print(0)
    exit()

f, invf = [1] * maxf, [1] * maxf

for i in range(1, maxf):
    f[i] = f[i - 1] * i % MOD
invf[maxf - 1] = pow(f[maxf - 1], MOD - 2, MOD)
for i in range(maxf - 1, 0, -1):
    invf[i - 1] = invf[i] * i % MOD

comb = lambda a, b: f[a] * invf[b] * invf[a - b] % MOD

print(comb(a + b, b) % MOD)

Submission status: Wrong Answer

Solution code:
import math
import sys

m=10**9 + 7 
sys.setrecursionlimit(1000010)
(x,y) = map(int,input().split())

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

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod


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

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

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

print(comb(a+b,a,m))

Submission status: Wrong Answer

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

x_n = 0
y_n = 0

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

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

if (X+Y)%3==0:
  _sum = (X+Y)//3
  a = Y-_sum
  b = X-_sum
  print(cmb(_sum,a)%1000000007)
  
else:
  print(0)

Submission status: Wrong Answer

Solution code:
x, y = map(int, input().split())
mod = 10 ** 9 + 7
if (x == 1 and y == 2) or (x == 2 and y == 1):
    print(1)
    quit()
if (x % 3 == 0 and y % 3 != 0) or (x % 3 != 0 and y % 3 == 0):
    print(0)
    quit()
ans = 1
ans = 2 ** (x//3)
# for i in range(1, x // 3+1):
#     ans *= 2
# for j in range(1, y // 3+1):
#     ans *= 2
print(ans % mod)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

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

# nCr
def nCr(n,r):
  if n<r:
    return 0
  return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

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

  if x==0 or y==0:
    return 0

  sm=x+y
  if sm%3!=0:
    return 0

  cnt=sm//3
  ac=cnt//2-((x-y)//2)
  bc=cnt-ac

  # print(ac)
  # print(bc)

  return cmb(cnt,ac)%mod


# main()
print(main())

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7
fac = [1] * (10 ** 6 + 2)
for i in range(len(fac) - 1):
    fac[i + 1] = fac[i] * (i + 1) % MOD
x, y = map(int, input().split())
t = min(x, y) // 3
if (2 * x - y) % 3 or (2 * y - x) % 3:
    print(0)
    exit(0)
a, b = (2 * x - y) // 3, (2 * x - y) // 3
k = max(a, b)
n = a + b
print((fac[n] * pow(fac[n - k], MOD - 2, MOD)
       * pow(fac[k], MOD - 2, MOD)) % MOD)

Submission status: Wrong Answer

Solution code:
import math

def comb(n, k, MOD, N):
    fact = [1]*(N+1)
    rfact = [1]*(N+1)
    r = 1
    for i in range(1, N+1):
        fact[i] = r = r * i % MOD
    rfact[N] = r = pow(fact[N], MOD-2, MOD)
    for i in range(N, 0, -1):
        rfact[i-1] = r = r * i % MOD
    return fact[n] * rfact[k] * rfact[n-k] % MOD

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

diff = abs(x-y)
if (min(x, y) - diff) % 3 != 0:
    print(0)
else:
    count = (min(x, y) - diff) // 3
    print(comb(2*count+diff, count, mod, 10**6))

Submission status: Wrong Answer

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

#a(1, 2) + b(2, 1) = (X, Y)
#a=(2*Y-X)//3
#b=(2*X-Y)//3


def comb(x, y):
    if y * 2 > x:
        y = x - y
    result = 1
    for j in range(1, y + 1):
        result *= (x + j - y) * pow(j, mod - 2, mod)
        result %= mod
    return result


if (2 * Y - X) % 3 == (2 * X - Y) % 3 == 0:
    a = (2 * Y - X) // 3
    b = (2 * X - Y) // 3
    print(comb(a + b, b))
else:
    print(0)

Submission status: Wrong Answer

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

# (1, 2) * a + (2, 1) * b = (x, y)
#
# a + 2 * b = x
# 2 * a + b = y
# b = y - 2 * a
# a = x - 2 * b
# b = y - 2 * (x - 2 * b)
#   = y - 2 * x + 4 * b
# 3 * b = - y + 2 * x

b = (-y + 2*x)# / 3
if b % 3 != 0:
    print(0)
    sys.exit()
b //= 3
a = x - 2 * b
# (a + b)! / (a! * b!)
if a <= 0:
    print(0)
    sys.exit()

def fact(n):
    ans = n
    for i in range(1, n):
        ans *= i
        if ans >= M:
            ans %= M
    return ans

def pm(value, n):
    if n == 0:
        return 1
    if n % 2:
        return pm(value, n - 1) * value % M
    else:
        return pm(value, n // 2) ** 2 % M

# A * B ^ (M-2)
print(fact(a + b) * pm(fact(a) * fact(b) % M, M - 2) % M)

Submission status: Wrong Answer

Solution code:
import math

def modinv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = a // b
        a -= t * b
        b, a = a, b
        u -= t * v
        v, u = u, v
    u = u % m
    if (u < 0):
        u += m
    return u

def fact(n):
    if n <= 1:
        return 1
    ret = 1
    for i in range(2, n + 1):
        ret *= i
        ret = ret % (10 ** 9 + 7)
    
    return ret

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

nx, ny = (2 * y - x) / 3, (2 * x - y) / 3

if nx.is_integer() and ny.is_integer() and (nx > 0.0 or ny > 0.0):
    n2x = int(nx)
    n2y = int(ny)
    gnx = modinv(fact(n2x), 10 ** 9 + 7)
    gny = modinv(fact(n2y), 10 ** 9 + 7)
    print((fact(n2x + n2y) * gnx % (10 ** 9 + 7)) * gny % (10 ** 9 + 7))
else:
    print('0')

Submission status: Wrong Answer

Solution code:
import functools, sys

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

mod = 10 ** 9 + 7

def modpow(x, y):
    z = 1
    while y > 0:
        if y % 2 == 0:
            x = (x * x) % mod
            y //= 2
        else:
            z = (z * x) % mod
            y -= 1
    return z

def modinv(x):
    return modpow(x, mod - 2)

def c(n, r):
    fct = [None] * (n + 1)
    fct[0] = 1
    for i in range(1, n + 1):
        fct[i] = fct[i - 1] * i % mod
    return fct[n] * (modinv(fct[n - r]) * modinv(fct[r]) % mod) % mod

def f():
    a = 0
    while True:
        p = x - a
        q = y - 2 * a
        if p <= 0 or q <= 0:
            return 0
        if p % 2 == 0 and p // 2 == q:
            b = q
            break
        a += 1
    
    return c(a + b, a)

print(f())