Problem:


Score : 400 points

Problem Statement

There is a knight - the chess piece - at the origin (0, 0) of a two-dimensional grid.

When the knight is at the square (i, j), it can be moved to either (i+1,j+2) or (i+2, j+1).

In how many ways can the knight reach the square (X, Y)?

Find the number of ways modulo 10^9 + 7.

Constraints

1 \leq X \leq 10^6

1 \leq Y \leq 10^6

All values in input are integers.

Input

Input is given from Standard Input in the following format:

X Y

Output

Print the number of ways for the knight to reach (X, Y) from (0, 0), modulo 10^9 + 7.

Sample Input 1

3 3

Sample Output 1

2

There are two ways: (0,0) \to (1,2) \to (3,3) and (0,0) \to (2,1) \to (3,3).

Sample Input 2

2 2

Sample Output 2

0

The knight cannot reach (2,2).

Sample Input 3

999999 999999

Sample Output 3

151840682

Print the number of ways modulo 10^9 + 7.



Sample input:
3 3


Sample output:
2

Submission status: Wrong Answer

Solution code:
def factorial(N,MOD,r=True):
    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
    if r:
        return fact,rfact
    else:
        return fact
mod = 10**9 + 7
fact,rfact = factorial(10**6,mod)

def perm(n,k): #上のfactorialと併用
    return fact[n]*rfact[n-k]%mod
def comb(n,k): #上のfactorialと併用
    return fact[n]*rfact[k]*rfact[n-k]%mod

x,y = map(int,input().split())
if (x+y)%3:
    print(0)
    exit()
a = (-x+2*y)//3
b = (2*x-y)//3
print(comb(a+b,a))

Submission status: Wrong Answer

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

else:
    bunsi = 1
    bunbo = 1
    for i in range(0, n):
        bunsi = (bunsi * (m + 1 + i)) % mod
        bunbo = (bunbo * (1 + i)) % mod
    print((bunsi * pow(bunbo, mod - 2, mod)) % mod)

Submission status: Wrong Answer

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

else:
    print(0)
    bunsi = 1
    bunbo = 1
    for i in range(0, n):
        bunsi = (bunsi * (m + 1 + i)) % mod
        bunbo = (bunbo * (1 + i)) % mod
    print((bunsi * pow(bunbo, mod - 2, mod)) % mod)

Submission status: Wrong Answer

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

else:
    print(0)

Submission status: Wrong Answer

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

else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
mod=10**9+7
n_max=2*(10**6+1)
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
FI[n_max-1]=pow(F[n_max-1],mod-2,mod)
for i in reversed(range(n_max-1)):
  FI[i]=(FI[i+1]*(i+1))%mod
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod
x,y=map(int,input().split())
if (x+y)%3!=0:
  print(0)
else:
  n=(x+y)//3
  if x<n:
    print(0)
  else:
    print(comb(n,x-n))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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


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

if (n == (2 * Y - X) / 3 and m == (2 * X - Y) / 3):
    a = n + m
    b = min(n, m)
    num = 1
    den = 1
    for i in range(b):
        num = (num * (a - i)) % mod
        den = (den * (i + 1)) % mod
    den_r = pow(den, mod - 2, mod)
    print((num * den_r) % mod)
else:
    print(0)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
import copy
#import numpy as np
 
# 入力
#A, B, C, D = map(int, input().split())
#L = list(map(int, input().split()))
#S = list(str(input()))
#N = int(input())
#S = str(input())

X, Y = map(int, input().split())
MOD = pow(10, 9) + 7

def comb_mod(n, r, mod):
  num = 1
  den = 1
  for i in range(r):
    num = (num * (n - i)) % mod
    den = (den * (i + 1)) % mod
  den_r = pow(den, mod - 2, mod)
  return (num * den_r) % mod


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

if n == (2*Y - X) / 3 and m == (2*X - Y) / 3 :  
  a = n + m
  b = min(n, m)
  print(comb_mod(a, b, MOD))
else :
  print (0)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
import copy
#import numpy as np
 
# 入力
#A, B, C, D = map(int, input().split())
#L = list(map(int, input().split()))
#S = list(str(input()))
#N = int(input())
#S = str(input())

X, Y = map(int, input().split())
MOD = pow(10, 9) + 7

def comb_mod(n, r, mod):
  num = 1
  den = 1
  for i in range(r):
    num = (num * (n - i)) % mod
    den = (den * (i + 1)) % mod
  den_r = pow(den, mod - 2, mod)
  return (num * den_r) % mod


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

if not n.is_integer() or not m.is_integer() :
  print (0)
else :
  a = int(n) + int(m)
  b = min(int(n), int(m))
  print(comb_mod(a, b, MOD))

Submission status: Wrong Answer

Solution code:
import sys

def comb_mod(n, r, mod):
  x = 1
  y = 1
  for i in range(r):
    x = (x * (n - i)) % mod
    y = (y * (i + 1)) % mod
    
  ans = x * pow_k(y, mod-2, mod)
  
  return ans % mod
  
# x^n % mod
def pow_k(x, n, mod):
  if n == 0:
    return 1

  K = 1
  while n > 1:
    if n % 2 != 0:
      K = (x * K) % mod
        
    x = (x * x) % mod

    n //= 2

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

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

ans = comb_mod(a+b, min(a,b), MOD)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

X, Y = map(int, input().split())
A, mod = divmod(2*Y-X, 3)
if mod != 0:
	print(0)
	sys.exit()
B, mod = divmod(2*X-Y, 3)
if mod != 0:
	print(0)
	sys.exit()

mod = 10**9 + 7

a = A+B
b = min(A,B)

ans = 1

for i in range(b):
	ans *= a-i
	ans %= mod

	ans *= pow(i+1, mod-2, mod)

ans %= mod

print(ans)

Submission status: Wrong Answer

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

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

n = (x+y)//3
a = x - n
b = y - n
r = min(a, b)
if r < 0:
    print(0)
val1 = 1
for i in range(a+b):
    val1 = (val1 * ((a+b) - i)) % mod
val2 = 1
for i in range(r):
    val2 = (val2 * (r-i)) % mod
for i in range(a+b-r):
    val2 = ((val2% mod) * ((a+b-r)-i)) % mod
# val1 = factorial(a+b) % mod
# val2 = (factorial(r) % mod * factorial((a+b)-r) % mod) % mod
print((val1 * pow(val2,mod-2,mod)) % mod)

Submission status: Wrong Answer

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

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

n = (x+y)//3
a = x - n
b = y - n
r = min(a, b)
val1 = 1
for i in range(a+b):
    val1 = (val1 * ((a+b) - i)) % mod
val2 = 1
for i in range(r):
    val2 = (val2 * (r-i)) % mod
for i in range(a+b-r):
    val2 = ((val2% mod) * ((a+b-r)-i)) % mod
# val1 = factorial(a+b) % mod
# val2 = (factorial(r) % mod * factorial((a+b)-r) % mod) % mod
print((val1 * pow(val2,mod-2,mod)) % mod)

Submission status: Wrong Answer

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

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

n = (x+y)//3
a = x - n
b = y - n
r = min(a, b)
val1 = 1
for i in range(a+b):
    val1 = (val1 * ((a+b) - i)) % mod
val2 = 1
for i in range(r):
    val2 = (val2 * (r-i)) % mod
for i in range(a+b-r):
    val2 = ((val2% mod) * ((a+b-r)-i)) % mod
# val1 = factorial(a+b) % mod
# val2 = (factorial(r) % mod * factorial((a+b)-r) % mod) % mod
print(val1 * pow(val2,mod-2,mod) % mod)

Submission status: Wrong Answer

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

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

n = (x+y)//3
a = x - n
b = y - n
r = min(a, b)
val1 = 1
for i in range(a+b):
    val1 = (val1 * ((a+b) - i)) % mod
val2 = 1
for i in range(r):
    val2 = (val2 * (r-i)) % mod
for i in range(a+b-r):
    val2 = (val2 * ((a+b-r)-i)) % mod
# val1 = factorial(a+b) % mod
# val2 = (factorial(r) % mod * factorial((a+b)-r) % mod) % mod
print(val1 * pow(val2,mod-2,mod) % mod)

Submission status: Wrong Answer

Solution code:
#コンビネーション
def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod

N = pow(10, 6) + 10  # N は必要分だけ用意する
mod = pow(10, 9) + 7
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) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)


x,y = map(int,input().split())
a = (2 * y - x) // 3
b = (2 * x - y) // 3
#print(a, b)
ans = 0
if a > 0 and b > 0 and (x + y) % 3 == 0:
    ans = cmb(a + b, min(a, b))
elif (x + y) % 3 == 0:
    ans = a + b
print(ans)

Submission status: Wrong Answer

Solution code:
#コンビネーション
def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod

N = pow(10, 6) + 10  # N は必要分だけ用意する
mod = pow(10, 9) + 7
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) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)


x,y = map(int,input().split())
a = (2 * y - x) // 3
b = (2 * x - y) // 3
#print(a, b)
ans = 0
if a > 0 or b > 0:
    ans = cmb(a + b, min(a, b))
print(ans)

Submission status: Wrong Answer

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

if (X+Y)%3 != 0 or abs(X-Y) > (X+Y)//3:
    print(-1)
    exit(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
MOD = 10**9 + 7

print(cmb((X+Y)//3,min(X,Y)-(X+Y)//3)%MOD)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
mod = 10**9+7
def cmb(a,b):
    b = min(a-b,b)
    ans = 1
    for i in range(b):
        ans *= (a-i) * pow(i+1,mod-2,mod)% mod
    return ans % mod
    
x,y = map(int,input().split())
r = (2*y-x)//3
d = (2*x-y)//3
if (2*y-x)% 3 or (2*x-y)%3: print(0)
else:print(cmb(r+d,d))

Submission status: Wrong Answer

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

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

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

def comb(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

print(comb(n,r))

Submission status: Wrong Answer

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

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

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

print(comb(n,r))

Submission status: Wrong Answer

Solution code:
p = 10**9+7
def pow(x,m):
    if m==0:return 1
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2))%p
X,Y = map(int,input().split())
K = X+Y
A = [1 for _ in range(K)]
for i in range(2,K):
    A[i] = (A[i-1]*i)%p
B = [1 for _ in range(K)]
B[K-1] = pow(A[K-1],p-2)
for i in range(K-2,1,-1):
    B[i] = ((i+1)*B[i+1])%p
if (X+Y)%3==0 and (2*Y-X)%3==0:
    k = (X+Y)//3
    i = (2*Y-X)//3
#     cnt = (A[k]*B[i]*B[k-i])%p
    cnt = (A[k]*B[i])%p
    cnt = (cnt*B[k-i])%p
    print(cnt)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
p = 10**9+7
def pow(x,m):
    if m==0:return 1
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2))%p
X,Y = map(int,input().split())
K = X+Y
A = [1 for _ in range(K)]
for i in range(2,K):
    A[i] = (A[i-1]*i)%p
B = [1 for _ in range(K)]
B[K-1] = pow(A[K-1],p-2)
for i in range(K-2,1,-1):
    B[i] = ((i+1)*B[i+1])%p
if (X+Y)%3==0 and (2*Y-X)%3==0:
    k = (X+Y)//3
    i = (2*Y-X)//3
    cnt = (A[k]*B[i]*B[k-i])%p
    print(cnt)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
p,q=map(int,input().split())
mod=10**9+7
x=(2*q-p)//3
y=q-2*x
def ie(n,r,mod):
  if r==1:
    return n%mod
  elif r%2==0:
    return (ie(n,r//2,mod)**2)%mod
  else:
    return ((ie(n,r//2,mod)**2)*n)%mod
if x+2*y!=p or 2*x+y!=q or x<0 or y<0:
  print(0)
else:
  a=[(x+y)%mod]
  b=[1]
  for i in range(1,min(x,y)):
    a.append(a[-1]*(x+y-i)%mod)
    b.append(b[-1]*(i+1)%mod)
  print((a[-1]*ie(b[-1],mod-2,mod))%mod)

Submission status: Wrong Answer

Solution code:
p,q=map(int,input().split())
mod=10**9+7
x=(2*q-p)//3
y=q-2*x
def ie(n,r,mod):
  if r==1:
    return n%mod
  elif r%2==0:
    return (ie(n,r//2,mod)**2)%mod
  else:
    return ((ie(n,r//2,mod)**2)*n)%mod
if x+2*y!=p or 2*x+y!=q:
  print(0)
else:
  a=[(x+y)%mod]
  b=[1]
  for i in range(1,min(x,y)):
    a.append(a[-1]*(x+y-i)%mod)
    b.append(b[-1]*(i+1)%mod)
  print((a[-1]*ie(b[-1],mod-2,mod))%mod)

Submission status: Wrong Answer

Solution code:
X,Y=map(int,input().split())
N=(X+Y)//3
import sys
sys.setrecursionlimit(10**8)
A=X-N
B=Y-N
No=False
if (X+Y)%3!=0 or X<N or Y<N:
    No=True
ans=1
C=min(A,B)
for i in range(0, C):
    ans*=N-i
    ans%=(10**9+7)
def inv(i, p, q):
    if q==1:
        return i%p
    if q%2==0:
        x=inv(i, p,q//2)
        return (x**2)%p
    else:
        x=inv(i, p,q//2)
        return (x**2*i)%p
tmp=1
for i in range(C):
    tmp*=(i+1)
    tmp%=(10**9+7)
iv=inv(tmp, 10**9+7,10**9+5)
ans=ans*iv%(10**9+7)
if No:
    print(0)
else:
    print("ans",ans)

Submission status: Wrong Answer

Solution code:
X, Y = (int(i) for i in input().split())

def power(a, b):
	if b == 0:
		return 1
	elif b == 1:
		return a % 1000000007
	elif b % 2 == 0:
		return (power(a, b//2) ** 2) % 1000000007
	else:
		return (power(a, b//2) ** 2 * a) % 1000000007

def divide(a, b):
	return (a * power(b, 1000000005)) % 1000000007


#階乗の逆元を求める
fac_lim = 1000000
fac = [None]*(fac_lim+1)
fac[0] = 1
for i in range(fac_lim):
    fac[i+1] = fac[i] * (i+1)
    fac[i+1] = fac[i + 1] % 1000000007

fac_inv = [None]*(fac_lim+1)
fac_inv[fac_lim] = power(fac[fac_lim], 1000000005)
for i in range(fac_lim, 0, -1):
    fac_inv[i-1] = (fac_inv[i] * i)  % 1000000007

def conv(a, b):
    return (fac[a] * fac_inv[a-b] * fac_inv[b]) % 1000000007


MOD = 10**9 + 7
if (X+Y)%3 != 0:
    ans = 0
else:
    N = (X+Y)//3
    M = X - Y
    if (N+M)%2 !=0:
        ans = 0
    else:
        a = (N+M)//2
        ans = conv(N, a)
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    x,y = map(int,input().split())
    a_old = 2 * y - x
    b_old = 2 * x - y

    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

    if (a_old % 3 == 0) and (b_old % 3 == 0) and (a_old > 0) and (b_old > 0):
        a_new = int(a_old // 3)
        b_new = int(b_old // 3)
        n = a_new + b_new
        r = cmb(n,a_new)
        print(int(r % (10**9 + 7)))
    else:
        print(0)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    x,y = map(int,input().split())
    a_old = 2 * y - x
    b_old = 2 * x - y

    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

    if (a_old % 3 == 0) and (b_old % 3 == 0):
        a_new = int(a_old // 3)
        b_new = int(b_old // 3)
        n = a_new + b_new
        r = cmb(n,a_new)
        print(int(r % (10**9 + 7)))
    else:
        print(0)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

#nCr フェルマーの小定理より（ABC156D参照）
def comb_mod(n, r, mod):
    num = 1
    den = 1
    for i in range(r):
        num = (num * (n - i)) % mod
        den = (den * (i + 1)) % mod
    den_r = pow(den, mod - 2, mod)
    return (num * den_r) % mod

#3の倍数以外は0
if (X + Y) % 3 != 0:
    print(0)
else:
#n+2m=X,2n+m=Yより    
    n = (2 * Y - X) // 3
    m = (2 * X - Y) // 3
    print(comb_mod(n + m, n, mod))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
MOD = 1000000007  # type: int

# 逆元comb
def comb(n, k):
    k = min(n-k,k)
    ans = 1
    for i in range(1, k + 1):
        ans *= (n + 1 - i) * pow(i,MOD-2,MOD)
        ans %= MOD
    return ans

def solve(X: int, Y: int):
    if (X+Y)%3 != 0:
        print(0)
        return

    # (1,2)の移動をa回, (2,1)の移動をb回するとするをそれぞれ何回か決まる
    a = (Y*2-X)//3
    b = (X*2-Y)//3
    print(comb(a+b,a)%MOD)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(X, Y)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
MOD = 1000000007  # type: int

# 逆元comb
def comb(n, k):
    k = min(n-k,k)
    ans = 1
    for i in range(1, k + 1):
        ans *= (n + 1 - i) * pow(i,MOD-2,MOD)
        ans %= MOD
    return ans

def solve(X: int, Y: int):
    if (X+Y)%3 != 0:
        print(0)
        return

    # (1,2)の移動をa回, (2,1)の移動をb回するとするをそれぞれ何回か決まる
    a = (Y*2-X)//3
    b = (X*2-Y)//3
    print(comb(a+b,a))
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(X, Y)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
MOD = 1000000007  # type: int

# 逆元comb
def comb(n, k):
    k = min(n-k,k)
    ans = 1
    for i in range(1, k + 1):
        ans *= (n + 1 - i) * pow(i,MOD-2,MOD)
        ans %= MOD
    return ans

def solve(X: int, Y: int):
    if X%3 != 0 or Y%3 != 0:
        print(0)
        return

    # (1,2)の移動をa回, (2,1)の移動をb回するとするをそれぞれ何回か決まる
    a = Y*2//3-X//3
    b = X*2//3-Y//3

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

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(X, Y)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

    print(binomial(a+b,a)%mod)
else:
    print(0)

Submission status: Wrong Answer

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

if (2*y-x)%3!=0 or (2*x-y)%3!=0:
    ans=0
else:
    a=(2*y-x)//3
    b=(2*x-y)//3
    n=a+b
    ans=1
    for i in range(min(a,b)):
        ans*=(n-i)
        ans%=(10**9+7)
        ans*=pow(i+1,10**9+5,10**9+7)
print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
x,y= map(int, input().split())
a=min(x,y)
b=max(x,y)
mod=pow(10,9)+7
if b-a>=a or (a-(b-a))%3!=0:
    print(0)

else:
    r=(a-(b-a))//3
    l=((a-(b-a))//3)+(b-a)
    c=1
    d=1
    for i in range(r):
        c=(c*(l+r-i))%mod
        d=(d*(r-i))%mod
    ans=c*pow(d,mod-2,mod)
    print(ans%mod)

Submission status: Wrong Answer

Solution code:
x,y= map(int, input().split())
a=min(x,y)
b=max(x,y)
mod=pow(10,9)+7
if b-a>=a or (a-(b-a))%3!=0:
    print(0)

else:
    r=(a-(b-a))//3
    l=((a-(b-a))//3)+(b-a)
    c=1
    d=1
    for i in range(r):
        c=(c*(l+r-i))%mod
        d=(d*(l-i))%mod
    ans=c*pow(d,mod-2,mod)
    print(ans%mod)

Submission status: Wrong Answer

Solution code:
def combination(n, a):
    mod = pow(10, 9)+7
    x, y = 1, 1
    for i in range(a):
        x = x * (n-i)%mod
        y = y * (a-i)%mod
    return x * pow(y, mod-2, mod)%mod

x, y = map(int, input().split())
n, m = (2*y - x)//3, (2*x - y)//3
if (x + y)%3 != 0 and (n < 0 and m < 0):
    print(0)
else:
    ans2 = combination(n+m, n)
    print(ans2)

Submission status: Wrong Answer

Solution code:
#import numpy as np
def combination(n, a):
    mod = pow(10, 9)+7
    x = 1
    y = 1
    for i in range(a):
        x = x * (n-i)%mod
        y = y * (a-i)%mod
    return x * pow(y, mod-2, mod)%mod

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

if (x + y)%3 != 0:
    print(0)
else:
    '''
    一つだけWAだった
    A = np.matrix([
        [2, 1],
        [1, 2]
        ])
    B = np.matrix([
        [x],
        [y]
        ])
    #ans = np.linalg.inv(A)*B
    ans1 = np.linalg.solve(A,B)
    '''
    n, m = (2*y - x)//3, (2*x - y)//3 
    ans2 = combination(n+m, n)
    print(ans2)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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

if (x + y)%3 != 0:
    print(0)
else:
    A = np.matrix([
        [2, 1],
        [1, 2]
        ])
    B = np.matrix([
        [x],
        [y]
        ])
    #ans = np.linalg.inv(A)*B
    ans1 = np.linalg.solve(A,B)
    n, m = int(ans1[0])//3, int(ans1[1])//3
    ans2 = combination(n+m, n)
    print(ans2)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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

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

A = np.matrix([
    [2, 1],
    [1, 2]
    ])
B = np.matrix([
    [x],
    [y]
    ])
#ans = np.linalg.inv(A)*B
ans1 = np.linalg.solve(A,B)
#print(int(ans[0]), int(ans[1]))
n, m = int(ans1[0]), int(ans1[1])

ans2 =combination(n+m, n)

print(ans2)

Submission status: Wrong Answer

Solution code:
def main():
    mod = 10 ** 9 + 7

    def choose(n, a, mod=mod):
        x, y = 1, 1
        for i in range(a):
            x = x * (n - i) % mod
            y = y * (i + 1) % mod
        return x * pow(y, mod - 2, mod) % mod

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

    q, r = divmod(x + y, 3)
    if r != 0:
        print(0)
        return

    # b:=(+2,+1)
    d = x * 2 - y
    if d % 3 != 0:
        print(0)
        return

    b = d // 3
    if q < b:
        print(0)
        return
    res = choose(q, min(b, q - b), mod)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    mod = 10 ** 9 + 7

    def choose(n, a, mod=mod):
        x, y = 1, 1
        for i in range(a):
            x = x * (n - i) % mod
            y = y * (i + 1) % mod
        return x * pow(y, mod - 2, mod) % mod

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

    q, r = divmod(x + y, 3)
    if r != 0:
        print(0)
        return

    # b:=(+2,+1)
    d = x * 2 - y
    if d % 3 != 0:
        print(0)
        return

    b = d // 3
    res = choose(q, min(b, q - b), mod)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

if Y > X:
    X, Y = Y, X

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

n = 0
m = 0

for n in range(X + 1):
    if (X - n) % 2 != 0:
        continue
    else:
        m = (X - n) // 2
        if 2 * n + m == Y:
            break

if m > n:
    n, m = m, n

print(n, m)

p = 1
q = 1
mod = 10 ** 9 + 7

for i in range(m):
    p *= (n + m - i)
    p %= mod
    q *= (m - i)
    q %= mod

ans = p * pow(q, mod - 2, mod)

print(ans % mod)