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
input = sys.stdin.readline

MAX = 2000000
MOD = 1000000007

X, Y = map(int, input().split())
count_x = 2*X - Y
count_y = 2*Y - X
if count_x % 3 != 0 or count_y % 3 != 0:
    print(0)
    exit()
count_x = count_x // 3
count_y = count_y // 3

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

fac[0], fac[1] = 1, 1
finv[0], finv[1] = 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):
    global fac
    global finv
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD

print(COM(count_x + count_y, min(count_x, count_y)))

Submission status: Wrong Answer

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

def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

for i in range(X + 1):
    x = X - i
    y = Y - i * 2
    if x / 2 == y:
        print(comb((y+i), min(y, i), 10**9+7))
        exit()
print(-1)

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 = abs(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):
    result = fact[n] % mod
    result *= fact_inv[k]
    result %= mod
    result *= fact_inv[n-k]
    result %= mod
    return result

print(mod_comb_k(total, dis, mod))

Submission status: Wrong Answer

Solution code:
#!python3.4.3
 
X, Y = map(int, input().split(' '))
count = 0
for i in range(1, X+1):
    for j in range(1, Y+1):
        x = 1*i + 2*j 
        y = 2*i + 1*j
        if x==X and y==Y:
            count+=1            
print((count*2)%(10**9+7))

Submission status: Wrong Answer

Solution code:
p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x%p
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
A = [1 for _ in range(10**6+1)]
for i in range(1,10**6+1):
    A[i] = (A[i-1]*i)%p
B = [1 for _ in range(10**6+1)]
B[10**6] = pow(A[10**6],p-2)
for i in range(10**6-1,1,-1):
    B[i] = (B[i+1]*(i+1))%p

X,Y = map(int,input().split())
if (X+Y)%3!=0:
    cnt = 0
else:
    k = (X+Y)//3
    if X>Y:
        X,Y = Y,X
    n = X-k
    cnt = (((A[k]*B[n])%p)*B[k-n])%p
print(cnt)

Submission status: Wrong Answer

Solution code:
import math
import sys


def Knight():
    def check(d):
        if not (d[0] % 3 == 0 and d[1] % 3 == 0) or (d[0] % 3 == 1 and d[1] % 3 == 2) or (d[0] % 3 == 2 and d[1] % 3 == 1):
            print(0)
            sys.exit()
    d = list(map(int, input().split()))
    check(d)

    x = d[0]
    y = d[1]
    diff = x - y if x > y else y - x
    d2 = [x - diff, y - diff * 2] if x < y else [x - diff * 2, y - diff]
    r = d2[0] // 3

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

    print(combinations_count(r * 2 + diff, r))


Knight()

Submission status: Wrong Answer

Solution code:
import math
tmp = input().split()
X = int(tmp[0])
Y = int(tmp[1])

zl = 0
lz = 0

# print(zl)
# print(lz)
x, y = 0, 0
while True:
    x += 2
    y += 1
    zl += 1

    if x >= X or y >= Y:
        x -= 2
        y -= 1
        zl -= 1
        break
# print(x)
# print(y)
# print(zl)
# print()
while True:
    x += 1
    y += 2
    lz += 1

    if x >= X or y >= Y:
        break
# print(x)
# print(y)
# print(lz)

# print()
print(int(math.factorial(zl+lz)/(math.factorial(zl)+math.factorial(lz))))

Submission status: Wrong Answer

Solution code:
from functools import reduce

prime = 1000000007


def modpow(a: int, n: int, mod: int = prime) -> int:
    res = 1
    while n > 0:
        if n & 1 != 0:
            res = res * a % mod
        a = a * a % mod
        n = n // 2
    return res


def modinv(a: int, mod: int = prime) -> int:
    return modpow(a, mod-2, mod)


def modfactrial(n: int, mod: int = prime) -> int:
    return reduce(lambda x, y: (x*y) % mod, range(1, n+1), 1)


def modcombination(n: int, r: int, mod: int = prime) -> int:
    # nCr = n!/(r!(n-r)!)
    n_fact = modfactrial(n, mod)
    r_fact = modfactrial(r, mod)
    nr_fact = modfactrial(n-r, mod)
    r_fact_inv = modinv(r_fact, mod)
    nr_fact_inv = modinv(nr_fact, mod)
    return n_fact * r_fact_inv * nr_fact_inv % mod


def abort():
    import sys
    print(0)
    sys.exit(0)


x, y = [int(x) for x in input().split()]
if (2*x-y) % 3 != 0:
    abort()
if (2*y-x) % 3 != 0:
    abort()
n = (2*y-x)//3
m = (2*x-y)//3
print(modcombination(n+m, n))

Submission status: Wrong Answer

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

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

ans = 0

def mod_Combination(n, k, mod):
    def ext_gcd(a, b):
        if b == 0:
            return a, 1, 0
        else:
            d,x,y = ext_gcd(b,a%b)
            x-=(a//b)*y 
        return d,y,x
    p,q=1,1
    for i in range(n-k+1, n+1):
        p=(p*i)%mod
    for i in range(2, k+1):
        q=(q*i)%mod
    return int(p*(ext_gcd(q, mod)[1]%mod)%mod)

if a%1==0 and b%1==0:
    ans = mod_Combination(int(a + b), int(a), 10**9 + 7)

print(ans)

Submission status: Wrong Answer

Solution code:
from numpy.linalg import solve
mod = 10**9+7
x,y=map(int,input().split(' '))
left = [[1,2],
        [2,1]]
right = [x,y]

A=solve(left,right)
ax,ay=float(A[0]),float(A[1])
if (not float.is_integer(ax) or not float.is_integer(ay)) or ax <0 or ay <= 0:
    print(0)
    exit()
ax,ay=int(ax),int(ay)
fac=[0 for i in range(ax+ay+1)]
inv=[0 for i in range(ax+ay+1)]
finv=[0 for i in range(ax+ay+1)]
fac[0] = 1
fac[1] = 1
finv[0]=1
finv[1]=1
inv[1] = 1
for i in range(2,ax+ay+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
ans = fac[ax+ay]*(finv[ax]*finv[ay])
ans %= mod
print(int(ans))

Submission status: Wrong Answer

Solution code:
def combinations_count(n, r):
    if r < n - r:
        t = r
    else:
        t = n - r
    
    ans= 1
    for i in range(t):
        ans *= ((n - i) // (i + 1))
    return(ans % (10 ** 9 + 7))
X, Y = map(int, input().split())

if (X+Y)%3 == 0 and X < 2*Y and Y < 2 * X:
    print(combinations_count((X+Y)//3, (2*X-Y)//3))
else:
    print("0")

Submission status: Wrong Answer

Solution code:
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

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

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

x,xm = divmod(X*2-Y, 3)
y,ym = divmod(-X+Y*2, 3)
if (xm == 0) & (ym==0):
    print(combination(x+y, x, mod))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
x, y = map(int,input().split())
if (x+y)%3 != 0:
	print(0)
	exit()

check_x = x/3
check_y = y/3

if x == y:
	print(2**int(check_x))
	exit()

Submission status: Wrong Answer

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

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

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

X, Y = [int(x) for x in input().strip().split()]
p = (X, 2 * X)
n1 = X
n2 = 0
f = False
while p != (X, Y):
    n1 -= 2
    n2 += 1
    p = (n1 + 2 * n2, 2 * n1 + n2)
    if p[1] < 0:
        break
else:
    f = True
if f:
    print(combination(n1 + n2, min(n1, n2), 10 ** 9 + 7))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
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())

mm = (2*Y - X) / 3
nn = (2*X - Y) / 3

ans = 0

if mm.is_integer() and nn.is_integer():
    mm = int(mm)
    nn = int(nn)
    if mm<nn:mm, nn = nn, mm
    ans =comb(mm+nn, nn, 10**9+7)
      
print(ans)

Submission status: Wrong Answer

Solution code:
import operator as op
from functools import reduce



def fact(n):
    x = n
    t = 1
    while(x>0):
        t *= x
        t %= (10**9+7)
        x -= 1
    return t



valid = True
n = sorted([int(i) for i in input().split()])
a = n[0]
b = n[1]
x = 0
y = 0

x += b-a
a -= b-a
b -= 2*(b-a)

if(a>0 and b>0 and a%3==0):
    x += a//3
    y += a//3
else:
    valid = False
        
if(valid):
    print (fact(x+y)*pow(fact(x)*fact(y), 10**9+7 - 2, 10**9+7) % (10**9+7))
else:
    print(0)

Submission status: Wrong Answer

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

def power(base, num):
    if num == 0:
        return 1
    elif num % 2==0:
        return power(base, num//2) **2 % MOD
    elif num==1:
        return base % MOD
    else:
        return power(base, num//2) **2 * base % MOD
    
fact = [0 for i in range(N)]
inv_fact = [0 for i in range(N)]
 
fact[0] = 1
for i in range(1, N):
    fact[i] = fact[i-1] * i % MOD

inv_fact[N-1] = power(fact[N-1], MOD-2)
for i in range(1, N):
    inv_fact[N-1-i] = inv_fact[N-i] * (N-i) % MOD
 
def comb(x,y):
    return (fact[x] * inv_fact[y])%MOD * inv_fact[x-y] % MOD

if (2*X-Y)%3==0 and (-X+2*Y)%3==0:
    a = (2*X-Y) //3
    b = (-X+2*Y)//3
    ans = comb(a+b, min(a,b)) % MOD

    print(ans)

    
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys
import math
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
a,b=map(int,input().split())
c=int((2*a-b)/3)
if c<0 or a+b>c:
    print('0')
    sys.exit()
if (a+b)%3!=0:
    print('0')
    sys.exit()
print(cmb((a+b)//3,c)%1000000007)

Submission status: Wrong Answer

Solution code:
import math

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

#initial: (X,Y) = (0,0)

num = 10**9 + 7
sum = 0
#print(num)
for i in range(X+1):# i は1step回数。２stepを行う回数は(X-i)//2(余りあったらbreak)
    if (X-i)% 2 == 0:
        j = (X-i)//2
        #print("i and j is ", i, j)
        if i * 2 + j  == Y:
            conbination_num = math.factorial(j) % num
            sum = conbination_num* ((sum + 1) % num)      

print(int(sum))

Submission status: Wrong Answer

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



if (2 * Y - X) % 3 != 0 or (2 * X - Y) % 3 != 0 or (2 * Y - X) // 3 < 0 or (2 * X - Y) // 3 < 0:
	print(0)
else:
	a = (2 * Y - X) // 3
	b = (2 * X - Y) // 3
	factorial = [1]
	for i in range(1, a + b + 5):
		factorial.append(factorial[i - 1] * i % MOD)
	print(int(factorial[a + b] // (factorial[a] * factorial[b])) % MOD)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**6)
input=sys.stdin.readline

def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p


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

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

val = [X,Y]
val_min = min(val)

val_min_sho = int(val_min/3)

X_henkan = X - 3*val_min_sho
Y_henkan = Y - 3*val_min_sho
if (X_henkan == 1 and Y_henkan == 2) or (X_henkan == 2 and Y_henkan == 1):
    n = (val_min_sho)*2 + 1
    n_2 = int(n/2)
    print(comb(n,n_2,10**9+7))
elif (X_henkan == 0 and Y_henkan == 0):
    n = (val_min_sho)*2
    n_2 = int(n/2)
    print(comb(n,n_2,10**9+7))
else:
    print(0)

Submission status: Wrong Answer

Solution code:


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


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

import numpy as np
from numpy.linalg import solve
 

x=solve([[1,2],[2,1]],[X,Y])

if np.all(x%1.0==0):
    print(cmb(int(np.sum(x)),int(np.min(x)))%(10**9+7))

else:
    print(0)

Submission status: Wrong Answer

Solution code:
def P(n, k):
    a = 1
    for i in range(k):
        a *= n-i
    return a
    
def kaijo(n):
    b = 1
    for i in range(n):
        b *= n-i
    return b

[X, Y] = [int(i) for i in input().split()]

div = 10**9 + 7

kouho = []

for i in range(1, int(X/2) + 1):
    if  Y == i + 2*(X-2*i):
        kouho.append([i, X-2*i])
    
ans = 0

for v in kouho:
    bunshi = P(sum(v), v[1])
    bumbo = kaijo(v[1])
    ans += bunshi//bumbo

print(ans%div)

Submission status: Wrong Answer

Solution code:
from numpy.linalg import solve
mod = 10**9+7
x,y=map(int,input().split(' '))
left = [[1,2],
        [2,1]]
right = [x,y]

A=solve(left,right)
ax,ay=float(A[0]),float(A[1])
if (not float.is_integer(ax) or not float.is_integer(ay)) or ax <0 or ay <= 0:
    print(0)
    exit()
ax,ay=int(ax),int(ay)
fac=[0 for i in range(ax+ay+1)]
inv=[0 for i in range(ax+ay+1)]
finv=[0 for i in range(ax+ay+1)]
fac[0] = 1
fac[1] = 1
finv[0]=1
finv[1]=1
inv[1] = 1
for i in range(2,ax+ay+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
print(ax+ay,ax,ay)
ans = fac[ax+ay]*(finv[ax]*finv[ay])
ans %= mod
print(int(ans))

Submission status: Wrong Answer

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

if (x+y)%3 == 0:
    n_m = (x+y)//3
    for n in range(n_m):
        m = n_m - n
        if n + 2*m == x and 2*n + m == y:
            cnt += factorial(n_m) // factorial(n) // factorial(m)
print(cnt)

Submission status: Wrong Answer

Solution code:
import math
MOD = 1000000000+7
X, Y = map(int, input().split())




if ((2*Y-X)%3 != 0) or ((2*X-Y)%3 != 0) or (2*Y-X) <= 0 or (2*X-Y) <= 0:
    print(0)
else:
    x = (2*Y-X) // 3
    y = (2*X-Y) // 3
    fac_list = [None for _ in range(x+y+2)]
    inv_fac_list = [None for _ in range(x+y+2)]
    
    fac_list[0] = 1
    for i in range(1, x+y+2):
        fac_list[i] = i * fac_list[i-1] % MOD

    inv_fac_list[x+y+1] = pow(fac_list[x+y+1],(MOD - 2), MOD)
    for i in range(x+y, 0, -1):
        inv_fac_list[i] = inv_fac_list[i+1] * (i+1) % MOD

    print((fac_list[x+y] * inv_fac_list[x] * inv_fac_list[y]) % MOD)

Submission status: Wrong Answer

Solution code:
import operator as op
from functools import reduce



def fact(n):
    x = n
    t = 1
    while(x>0):
        t *= x
        t %= (10**9+7)
        x -= 1
    return t



valid = True
n = sorted([int(i) for i in input().split()])
a = n[0]
b = n[1]
x = 0
y = 0

x += b-a
a -= b-a
b -= 2*(b-a)

if(a>0 and b>0):
    if(a%3!=0):
        valid = False
    else:
        x += a//3
        y += a//3
        
if(valid):
    print (fact(x+y)*pow(fact(x)*fact(y), 10**9+7 - 2, 10**9+7) % (10**9+7))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
d = 10**9 + 7

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

def numerator(n, k, p):
    l = 1;
    for j in range(k+1,n+1):
        l = (l*j)%p;
    return l

def denominator(n, k, p):
    l = 1;
    for j in range(2,n-k+1):
        l = (l*j)%p;
    return l


def power(a, k, p):
    if (k == 0):
        return 1
    r = power((a*a)%p,k>>0x01,p);
    if ((k&0x01) == 0x01): #odd number
        r = (r*a)%p;
    return r


def n_choose_K(n, k, p):
    num = numerator(n,k,p)
    den = denominator(n,k,p)
    return (num*power(den,p-2,p))%p
    

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

if n-int(n) != 0 or m-int(m) != 0:
    print(0)
else:
    n = int(n)
    m = int(m)
    ans = n_choose_K(n+m,n,d)
    print(int(ans))

Submission status: Wrong Answer

Solution code:
X, Y = map(int, input().split())
A = max(X, Y)
cnt = 0
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

for i in range(A//2):
    x = X - i
    y = Y - 2*i
    if x/2 == y:
        print(cmb(max(x, y), min(x, y)) % (10**9 + 7))

Submission status: Wrong Answer

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

if X==0 or Y==0:
    print(0)
    exit()

N=min(X,Y)
factl=[1]
for i in range(1,N+1):
    factl.append(factl[-1]*i%mod)
invl=[pow(factl[-1],mod-2,mod)]
for i in range(N,0,-1):
    invl.append(invl[-1]*i%mod)
invl.reverse()
def Comb(a,b):
    return factl[a]*invl[a-b]*invl[b]%mod
if X//Y == 2 and X%Y==0:
    print(Y)
    exit()
d=X-Y
if (Y-d)%3!=0 or Y-d<0:
    print(0)
    exit()
x,y=d+(Y-d)//3,(Y-d)//3

print(Comb(x+y,y))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
from math import factorial

fac = [0] * (10**6+1)
ifac = [0] * (10**6+1)
d = 10**9 + 7

def mpow(x, n):
    ans = 1
    while n != 0:
        if n&1:
            ans = ans * x % d
        x = x*x % d
        n = n >> 1
    return ans

def comb(a, b):
    if a == 0 and b == 0:
        return 1
    if a < b or a < 0:
        return 0
    tmp = ifac[a-b] * ifac[b] % d
    return tmp * fac[a] % d

def main():
    global fac, ifac
    x, y = map(int, input().strip().split())
    if (x + y) % 3 != 0:
        print(0)
        return
    k = (x+y) // 3
    q = x - k

    fac[0] = 1
    ifac[0] = 1
    for i in range(10**6):
        fac[i+1] = fac[i]*(i+1) % d
        ifac[i+1] = ifac[i]*mpow(i+1, d-2) % d

    print(comb(k, q) % d)

if __name__ == '__main__':
    main()

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()))
    xcnt = 0
    ycnt = 0
    cnt = min(x // 3, y // 3)
    if x / y == 2 or y / x == 2:
        print(1)
        exit()
    else:
        x -= cnt * 3
        y -= cnt * 3
        if x == 0 and y == 0:
            xcnt = cnt
            ycnt = cnt
        elif x != 0 and y / x == 2:
            xcnt = cnt
            ycnt = cnt + x
        elif y != 0 and x / y == 2:
            xcnt = cnt + y
            ycnt = cnt
        else:
            print(0)
            exit()
    print(alg_combination_mod(xcnt + ycnt, xcnt, mod))


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from math import factorial
from functools import reduce 

MOD = 10**9 + 7

def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

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

factorial = [1]
for n in range(1, X+Y):
    factorial.append(factorial[n-1]*n%MOD)

ans = 0
prv_m, prv_n = None, None
for m in range(X):
  if (X-m)%2 == 1:continue
  n = (X-m)//2
  if 2*m+n != Y: continue
 
  ans += factorial[m+n]*power_func(factorial[m],MOD-2,MOD)*power_func(factorial[n],MOD-2,MOD)
  ans %= MOD

print(ans%MOD)

Submission status: Wrong Answer

Solution code:
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

MOD = 10**9+7

if (-Y + 2*X) % 3 == 0 and (2*Y - X) %3 == 0:
    x = (-Y + 2*X) // 3
    y = (2*Y - X) // 3
    
    result = comb(x+y,min(x,y),MOD)
    print(int(result % MOD))
    
else:
    print(0)

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] * fact_inv[n-k]) %mod

print(mod_comb_k(total, dis, mod))

Submission status: Wrong Answer

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

chk = False
ct = 0
tx = X
ty = X * 2
for i in range(X+1):
    if tx == X and ty == Y:
        chk = True
        ct = i
        break
    ty -= 3
    if ty < Y:break
if not chk:
    print(0)
    exit()

p = X - (ct*2)
q = ct
#print(p,q)

md = 1000000007
r1 = 1
qn = 2
for i in range(p+1,(p+q)+1):
    r1 *= i
    if (r1 // qn) * qn == r1:
        r1 = r1 // qn
        if qn != 1:
            qn += 1
            if qn == q+1:
                qn = 1
    if qn == 1:
        r1 = r1 % md
print(r1)

Submission status: Wrong Answer

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

if (X + Y) % 3 != 0:
    print(0)
else:
    m = (X + Y) // 3 #動かした回数
    for i in range(m+1):
        d = 0
        if X == i + 2 * (m - i):
            d = i
            break
    
    n = math.factorial(m)
    p = math.factorial(m-d)
    q = math.factorial(d)
    print((n // (p * q)) % ((10**9) + 7))

Submission status: Wrong Answer

Solution code:
from math import factorial
M = 10**9 + 7
X, Y = map(int, input().split())
cnt = 0
while True:
    # print(X, Y)
    if X == 0 or Y == 0 or X / Y == 2:
        break
    cnt += 1
    X -= 1
    Y -= 2
if X == 0 and Y == 0:
    print(cnt)
elif X == 0 or Y == 0:
    print(0)
else:
    cnt2 = min(X, Y)
    maxcnt = max(cnt, cnt2)
    mincnt = min(cnt, cnt2)
    ans = 1
    for i in range(maxcnt+1, cnt+cnt2+1):
        ans = (ans * i) % M
    N = mincnt
    inv_t = [0]+[1]
    for i in range(2,mincnt+1):
        inv_t += [inv_t[M % i] * (M - int(M / i)) % M]
        ans = (ans * inv_t[i]) % M
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p


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

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

val = [X,Y]
val_min = min(val)

val_min_sho = int(val_min/3)

X_henkan = X - 3*val_min_sho
Y_henkan = Y - 3*val_min_sho
if (X_henkan == 1 and Y_henkan == 2) or (X_henkan == 2 and Y_henkan == 1):
    n = (val_min_sho)*2 + 1
    n_2 = int(n/2)
    print(comb(n,n_2,10**9+7))
elif (X_henkan == 0 and Y_henkan == 0):
    n = (val_min_sho)*2
    n_2 = int(n/2)
    print(comb(n,n_2,10**9+7))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
# 2019-11-16 21:01:15(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
from functools import reduce
import operator as op
# from scipy.misc import comb # float
# import numpy as np 


mod = 10 ** 9 + 7

# def nCr(n, r):
#     r = min(r, n-r)
#     upper = reduce(lambda x, y: x*y%mod, range(n, n-r, -1), 1)
#     lower = reduce(op.mul, range(r, 0, -1), 1)
#     return upper // lower
def comb(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 sys.stdin.readline().split()]
    # n(+1, +2), m(+2, +1)
    n, m = (2 * y - x) / 3, (2 * x - y) / 3

    if n != int(n) or m != int(m):
        print(0)
        sys.exit()
    else:
        n, m = int(n), int(m)
        ans = comb(n+m, n) % mod
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

X, Y = map(int, input().split())
if Y > X:
    X, Y = Y, X

ni1 = 0
ni2 = 0
while Y > X:
    ni1 += 1
    X -= 1
    Y -= 2
if X % 3 != 0:
    print(0)
    sys.exit()
ni1 += X // 3
ni2 += X // 3

MAX = ni1 + ni2
MOD = 10**9 + 7
fac = [0] * (MAX + 1)
finv = [0] * (MAX + 1)
inv = [0] * (MAX + 1)
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, MAX + 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

n = ni1 + ni2
k = ni1
if n < k or n < 0 or k < 0:
    ans = 0
else:
    ans = fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
INF = 1000000000+7

x,y = map(int, input().split())
a = 2*x-y
b = -x + 2*y


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

n = a//3
m = b//3
nm = n+m

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

if n==0 or m==0:
    print(max(n,m))
    exit()
ans = cmb(nm,n)
print(ans%INF)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

def main():
    inN = int(1e9+7)
    x, y = list(map(int, input().split()))
    s = (x+y)
    if s%3 != 0:
        print(0)
    else:
        p = abs(x-y)
        n = s//3
        if (n > x) or (n > y):
            print(0)
        else:
            if n%2 == 0:
                k = n//2 + p
            else:
                k = (n+1)//2 + p
            s = combinations_count(n, k) % inN
            print(s)
      
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
  r = min(r, n-r)
  ans = 1
  for i in range(1,r+1):
    ans *= n
    n -= 1
    ans //= i
    ans %= (10**9+7)
  return ans

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

max_diff = min(X,Y)
if (X+Y) % 3 == 0:
  n = (X + Y) // 3
  k = max_diff - n
  ans = cmb(n, k)
else:
  ans = 0

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
inf=1000000007
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
a,b=map(int,input().split())
if (a+b)%3!=0:
    print('0')
    sys.exit()
print(cmb((a+b)//3,int((2*a-b)/3))%1000000007)

Submission status: Wrong Answer

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

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

ans = 0

def mod_Combination(n, k, mod):
    def ext_gcd(a, b):
        if b == 0:
            return a, 1, 0
        else:
            d,x,y = ext_gcd(b,a%b)
            x-=(a//b)*y 
        return d,y,x
    p,q=1,1
    for i in range(n-k+1, n+1):
        p=(p*i)%mod
    for i in range(2, k+1):
        q=(q*i)%mod
    return int(p*(ext_gcd(q, mod)[1]%mod)%mod)
    
if a%1!=0 or b%1!=0:
    pass
elif a==0 and b==0:
    pass
else:
    ans = mod_Combination(int(a + b), int(a), 10**9 + 7)

print(ans)

Submission status: Wrong Answer

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

if X * 2 < Y or X > Y * 2:
    print(0)
    exit()