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

if (2*X-Y)%3 or (-X+2*Y)%3:
    print(0)
    exit()

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

if x > y:
    tmp = x
    x = y
    y = tmp

ans = 1
for i in range(1, x+1):
    ans *= (i+y)
    ans %= mod
    ans *= pow(i, mod-2, mod)
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
mod = int(1e9+7)
X, Y = map(int, input().split())
if (X+Y)%3:
    print(0)
    exit()
x = (2*X-Y)//3
y = (-X+2*Y)//3
if x > y:
    tmp = x
    x = y
    y = tmp

ans = 1
for i in range(1, x+1):
    ans *= (i+y)
    ans %= mod
    ans *= pow(i, mod-2, mod)
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import math
a = input().split()
x = int(a[0])
y = int(a[1])

ans = 0
m = (2*x-y)/3
n = (2*y-x)/3
if (x+y)%3 != 0:
    ans = 0
elif m<0 or n<0:
    ans = 0
else:
    mn2 = math.factorial(m+n) % (pow(10,9)+7)
    m2 = (1/math.factorial(m)) % (pow(10,9)+7)
    n2 = (1/math.factorial(n)) % (pow(10,9)+7)
    ans = mn2*m2*n2
print(int(ans))

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

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

m = 10**9 + 7

if (x + y) % 3 != 0:
    print(0)
else:
    s = (x + y) // 3
    k = y - s
    l = x - s
    a = 1
    b = 1
    for i in range(k + 1,k + l + 1):
        a = (a * i) % m
    for i in range(1,l + 1):
        b = (b * i) % m
    ans = a * pow(b,m-2,m) % m
    print(ans)

Submission status: Wrong Answer

Solution code:
def nCr(n,r,mod = 10**9+7):
    r = min(n-r,r)
    numer = denom = 1
    for i in range(1,r+1):
        numer = numer * (n+1-i) %mod
        denom = denom * i % mod
    return numer * pow(denom,mod-2,mod) %mod


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


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

count = (x+y)//3
x -= count
y -= count

ans = nCr(x+y, x)
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import reduce
X, Y = map(int, input().split())
if (2*X-Y) < 0 or (2*Y-X) < 0:
    print(0)
    exit()
if (2*X-Y)%3 != 0 or (2*Y-X)%3 != 0:
    print(0)
    exit()
if (2*X-Y)%3 == 0 or (2*Y-X)%3 == 0:
    print(1)
    exit()

a = int((2*X-Y)/3)
b = int((2*Y-X)/3)
total = a+b
def Fac(n,m):
    mul = lambda a, b: a*b
    if n == 1 or n == 0:
        return 1
    else:
        return reduce(mul,range(n-m+1,n+1))
x = min(a,b)
route = Fac(total,x)/Fac(x,x)
print(int(route)%(10**9+7))

Submission status: Wrong Answer

Solution code:
def Factorial(p, q, prime):  # Factorial from p to q
  p = int(p)
  q = int(q)
  res = 1
  for i in range(p, q):
    res = res * i % prime
  return res
 
prime = 10 ** 9 + 7
 
X, Y = map(int, input().split(" "))
 
x = (-1*X + 2*Y) / 3
y = (2*X - Y) / 3
 
if int(x) != x or int(y) != y or min(X, Y) <= 0 or min(x, y) < 0:
  print(0)
else:
  max_val = max(x, y)
  min_val = min(x, y)
  x_y_factorial = Factorial(max_val + 1, min_val + min_val + 1, prime)
  min_factorial = Factorial(1, min_val + 1, prime)
  
  res = 1
  mod = prime - 2
  while mod:
    if mod & 1:
      res = res * min_factorial % prime
    min_factorial = min_factorial ** 2 % prime
    mod = mod >> 1
 
  print(x_y_factorial * res % prime)

Submission status: Wrong Answer

Solution code:
def Factorial(p, q, prime):  # Factorial from p to q
  p = int(p)
  q = int(q)
  res = 1
  for i in range(p, q):
    res = res * i % prime
  return res
 
prime = 10 ** 9 + 7
 
X, Y = map(int, input().split(" "))
 
x = (-1*X + 2*Y) / 3
y = (2*X - Y) / 3
 
if int(x) != x or int(y) != y or min(X, Y) <= 0 or min(x, y) <= 0:
  print(0)
else:
  max_val = max(x, y)
  min_val = min(x, y)
  x_y_factorial = Factorial(max_val + 1, min_val + min_val + 1, prime)
  min_factorial = Factorial(1, min_val + 1, prime)
  
  res = 1
  mod = prime - 2
  while mod:
    if mod & 1:
      res = res * min_factorial % prime
    min_factorial = min_factorial ** 2 % prime
    mod = mod >> 1
 
  print(x_y_factorial * res % prime)

Submission status: Wrong Answer

Solution code:
def Factorial(p, q, prime):  # Factorial from p to q
  p = int(p)
  q = int(q)
  res = 1
  for i in range(p, q):
    res = res * i % prime
  return res
 
prime = 10 ** 9 + 7
 
X, Y = map(int, input().split(" "))
 
x = (-1*X + 2*Y) / 3
y = (2*X - Y) / 3
 
if int(x) != x or int(y) != y or min(X, Y) <= 0:
  print(0)
else:
  max_val = max(x, y)
  min_val = min(x, y)
  x_y_factorial = Factorial(max_val + 1, min_val + min_val + 1, prime)
  min_factorial = Factorial(1, min_val + 1, prime)
  
  res = 1
  mod = prime - 2
  while mod:
    if mod & 1:
      res = res * min_factorial % prime
    min_factorial = min_factorial ** 2 % prime
    mod = mod >> 1
 
  print(x_y_factorial * res % prime)

Submission status: Wrong Answer

Solution code:
def Factorial(p, q, prime):  # Factorial from p to q
  p = int(p)
  q = int(q)
  res = 1
  for i in range(p, q):
    res = res * i % prime
  return res
 
prime = 10 ** 9 + 7
 
X, Y = map(int, input().split(" "))
 
x = (-1*X + 2*Y) / 3
y = (2*X - Y) / 3
 
if int(x) != x or int(y) != y or min(x, y) < 0:
  print(0)
  exit()
else:
  max_val = max(x, y)
  min_val = min(x, y)
  x_y_factorial = Factorial(max_val + 1, min_val + min_val + 1, prime)
  min_factorial = Factorial(1, min_val + 1, prime)
  
  res = 1
  mod = prime - 2
  while mod:
    if mod & 1:
      res = res * min_factorial % prime
    min_factorial = min_factorial ** 2 % prime
    mod = mod >> 1
 
  print(x_y_factorial * res % prime)

Submission status: Wrong Answer

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

def main():
    mod = 10 ** 9 + 7
    x, y = map(int, input().split())
    if (2 * y - x) % 3 != 0:
        print(0)
        return None

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

    print(n,m)

    if n < 0 or m < 0:
        print(0)
    elif n == 0 and m == 0:
        print(0)
    elif n == 0 or m == 0:
        print(1)
    else:
        f = math.factorial
        ans = f(n+m) * modinv(f(n)) * modinv(f(m)) % mod
        print(ans)

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
MOD = int(1e9+7)

def power(b, e):
    res = 1
    while e > 0:
        if e % 2 == 1:
            res = res * b % MOD
        b = b * b % MOD
        e //= 2
    return res

def mod_inverse(n):
    return power(n, MOD-2)

def mul(x, y):
    return (x % MOD) * (y % MOD) % MOD
def multiple(x, y, z):
    return mul(mul(x, y), z)

def nCr(n, r):
    if r == 0:
        return 1
    fac = [1] * (n+1)
    for i in range(1, n+1):
        fac[i] = fac[i-1] * i % MOD
    return multiple(fac[n], mod_inverse(fac[r]), mod_inverse(fac[n-r]))

x, y = map(int, input().split())
if x < 3 or y < 3 or (x+y)%3 != 0 or min(x, y) * 2 < max(x, y):
    print(0)
    exit()
n = (2*x-y) // 3
m = (2*y-x) // 3
print(nCr(n+m, m))

Submission status: Wrong Answer

Solution code:
MOD = int(1e9+7)

def power(b, e):
    res = 1
    while e > 0:
        if e % 2 == 1:
            res *= b
        b = b * b % MOD
        e //= 2
    return res

def mod_inverse(n):
    return power(n, MOD-2)

def multiple(x, y):
    return (x % MOD) * (y % MOD) % MOD

def nCr(n, r):
    if r == 0:
        return 1
    fac = [1] * (n+1)
    for i in range(1, n+1):
        fac[i] = fac[i-1] * i % MOD
    return multiple(multiple(fac[n], mod_inverse(fac[r])), mod_inverse(fac[n-r]))

x, y = map(int, input().split())
if x < 3 or y < 3 or (x+y)%3 != 0 or min(x, y) * 2 < max(x, y):
    print(0)
    exit()
n = (2*x-y) // 3
m = (2*y-x) // 3
print(nCr(n+m, m))

Submission status: Wrong Answer

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

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

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

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 = (n + m)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

a = cmb(n+m, m, mod)

print(a)

Submission status: Wrong Answer

Solution code:
import sys
import math
from itertools import permutations
from itertools import combinations

#input = sys.stdin.readline
sys.setrecursionlimit(10**9)
X, Y = map(int, input().split())

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

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

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 = (n + m)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

a = cmb(n+m, m, mod)

print(a)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

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

def comb_mod(a: int, b: int, mod: int = MOD) -> int:
    b = min(b, a-b)
    res = 1
    for x in range(a-b+1, a+1):
        res = res * x % mod
    for x in range(1, b+1):
        res = res * pow(x, mod-2, mod) % mod
 
    return res

a = np.array([[1, 2], [2, 1]])
a=np.linalg.inv(a)
b = np.array([[x], [y]])
c=np.dot(a,b)
if(c[0]%1!=0. or c[1]%1!=0.):
    print(0)
i=int(c[0])
j=int(c[1])
num=comb_mod(i+j,i)
print(num)

Submission status: Wrong Answer

Solution code:
# editorialを参考にした
from functools import reduce
from operator import mul
import math
import sys
sys.setrecursionlimit(1000000)
X, Y = map(int, input().split())


def choose(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


if (X + Y) % 3 != 0:
    print(0)
else:
    numof21 = (-Y+2*X)//3
    numof12 = (-X + 2 * Y) // 3
    print(numof12, numof21)

    if numof12 < 0 or numof21 < 0:
        print(0)
    else:
        mod = 10**9+7  # 出力の制限
        N = numof12+numof21
        g1 = [1, 1]  # 元テーブル
        g2 = [1, 1]  # 逆元テーブル
        inverse = [0, 1]  # 逆元テーブル計算用テーブル

        for i in range(2, N + 1):
            g1.append((g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod//i)) % mod)
            g2.append((g2[-1] * inverse[-1]) % mod)
        # A = (math.factorial(numof12 + numof21))  # % (10**9+7)
        # B = math.factorial(numof21)  # % (10**9+7)
        # C = math.factorial(numof12)  # % (10 ** 9 + 7)
        # D = (B*C)  # % (10**9+7)
        # ans = (A//D) % (10**9+7)
        ans = choose((numof12+numof21), min(numof12, numof21),mod) % (10**9+7)
        print(ans)

Submission status: Wrong Answer

Solution code:
import math
from functools import lru_cache

# x,y = map(int, input().split(' '))
x, y = 999999, 999999
MOD = 10 ** 9 + 7


# 08        01
# 07          04
# 06      01    06
# 05        03    04
# 04    01    03    01
# 03      02    01
# 02  01    01
# 01    01
# 00ST
#   000102030405060708

# 到達可能地点の座標はx+y%3==0
# 到達可能手数は座標位置についてパスカルの三角形になる


# 到達可能か調べる
if x <= 2 * y and y <= x * 2 and (x + y) % 3 == 0:
    # 段数と位置を調べる
    total = (x + y) // 3
    # kx = 2 * total - x + 1
    # ky = 2 * total - y + 1
    n=x-total
    # print(total, k)

    # nCk 三角数n段目k番目の数は total! / k!(total-k)! であり
    # 回答は nCk / MOD なので
    # total! % MOD * 1/k! % MOD * (total-k)! % MOD と書ける

    fac = [1, 1]
    ifac = [1, 1]
    inv = [0, 1]

    for i in range(2, total + 1):
        fac.append(fac[-1] * i % MOD)
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
        ifac.append((ifac[-1] * inv[-1]) % MOD)

    def c(n, k):
        k = min(k, n-k)
        # if total < k: return 0
        # if total < 0 or k < 0: return 0
        return fac[n] * ifac[k] * ifac[n-k] % MOD

    # print(nck(total - 1, k - 1))

    print(c(total, n))
else:
    print(0)
    exit()

Submission status: Wrong Answer

Solution code:
# editorialを参考にした
import math
X, Y = map(int, input().split())
if (X + Y) % 3 != 0:
    print(0)
else:
    numof21 = (-Y+2*X)//3
    numof12 = (-X + 2 * Y) // 3
    print(numof12, numof21)
    if numof12 < 0 or numof21 < 0:
        print(0)
    else:
        A = (math.factorial(numof12 + numof21))  # % (10**9+7)
        B = math.factorial(numof21)  # % (10**9+7)
        C = math.factorial(numof12)  # % (10 ** 9 + 7)
        D = (B*C)  # % (10**9+7)
        ans = (A//D) % (10**9+7)
        print(ans)

Submission status: Wrong Answer

Solution code:
import math
x,y=map(int,input().split())
ans=1
if (x+y)%3!=0:
  print(0)
else:
  n=int((x+y)/3)
  k=int((2*x-y)/3)
  for i in range(k):
    ans=(ans*(n-i)/(1+i))%(10**9+7)
  print(int(ans))

Submission status: Wrong Answer

Solution code:
fact = [1]
mod = 10**9+7
for i in range(1,10**6 + 1):
    fact.append((fact[-1]*i)%mod)
def ncr(n,r):
    return ((fact[n]) * pow(fact[r],mod-2,mod) * pow(fact[n-r],mod-2,mod))%mod
x,y = map(int,input().split())
a = (2*x - y)//3
b = (2*y -x)//3
ans = 0
if (2*a + b == x) and (2*b + a == y) and a>0 and b>0:
    ans = fact[a+b]*pow(fact[a],mod-2,mod)*pow(fact[b],mod-2,mod)%mod
print(ans%mod)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
fact = [1]
mod = 10**9+7
for i in range(1,10**6 + 1):
    fact.append((fact[-1]*i)%mod)
def ncr(n,r):
    return ((fact[n]) * pow(fact[r],mod-2,mod) * pow(fact[n-r],mod-2,mod))%mod
x,y = map(int,input().split())
a = (2*x - y)//3
b = (2*y -x)//3
ans = 0
if (2*a + b == x) and (2*b + a == y) and a>0 and b>0:
    ans = ncr(a+b,b)
print(ans%mod)

Submission status: Wrong Answer

Solution code:
fact = [1]
mod = 10**9+7
for i in range(1,10**6 + 1):
    fact.append((fact[-1]*i)%mod)
def ncr(n,r):
    return ((fact[n]) * pow(fact[r],mod-2,mod) * pow(fact[n-r],mod-2,mod))%mod
x,y = map(int,input().split())
a = (2*x - y)//3
b = (2*y -x)//3
ans = 0
if (2*a + b == x) and (2*b + a == y) and a>0 and b>0:
    ans = ncr(a+b,b)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
X,Y = map(int, input().split())
border = 1e9+7
x = (2*X-Y)/3
y = (2*Y-X)/3

if not x.is_integer() or not y.is_integer() or (X+Y)%3!=0 or x<0 or y<0:
  print(0)
  exit()
  
x = int(x)
y = int(y)

prime = [2]
for i in range(3,int(math.sqrt(x+y))+1):
  isPrime = True
  for j in prime:
    if i%j==0:
      isPrime = False
      break
  if isPrime:
    prime.append(i)
  
def fact(n):
  arr = []
  temp = n
  for i in prime:
    if temp%i==0:
      cnt=0
      while temp%i==0:
        cnt+=1
        temp //= i
      arr.append((i, cnt))
    if temp == 1:
      break
  return arr

dic = dict()
z = max(x,y)
for i in range(z+1,x+y+1):
  arr = fact(i)
  for j,k in arr:
    dic[j] = dic.get(j,0) + k

z = min(x,y)
for i in range(2,z+1):
  arr = fact(i)
  for j,k in arr:
    dic[j] = dic[j] - k


ans = 1
for i in dic:
  for _ in range(dic[i]):
    ans = (ans*i)%border
    
print(int(ans))

Submission status: Wrong Answer

Solution code:
import cmath
import numpy as np
import sys

INF=1**18
MOD=10**9+7


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

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

N=(x+y)//3
if x<N or y<N:
    print(0)
    exit()

def moP(x,n):
    res=1
    while n>0:
        if n and 1:
            res=res*x%MOD
        x=x*x%MOD
        n//=2
    return res


fa=[1]*(N+1)
re=[1]*(N+1)


for i in range(1, N+1):
    fa[i]=fa[i-1]*i%MOD
    re[i]=moP(fa[i], MOD-2)

def comb(n,k):
    if n==0 or n==k:
        return 1
    return fa[n]*re[k]%MOD*re[n-k]%MOD

K=min(x,y)-N
print(comb(N,K))

Submission status: Wrong Answer

Solution code:
import math
X,Y = map(int, input().split())
border = 1e9+7
x = (2*X-Y)/3
y = (2*Y-X)/3

if not x.is_integer() or not y.is_integer() or (X+Y)%3!=0 or x<0 or y<0:
  print(0)
  exit()
  
x = int(x)
y = int(y)

prime = [2]
for i in range(3,int(math.sqrt(666667))+1):
  isPrime = True
  for j in prime:
    if i%j==0:
      isPrime = False
      break
  if isPrime:
    prime.append(i)
  
def fact(n):
  arr = []
  temp = n
  for i in prime:
    if temp%i==0:
      cnt=0
      while temp%i==0:
        cnt+=1
        temp //= i
      arr.append((i, cnt))
    if temp == 1:
      break
  return arr

dic = dict()
z = max(x,y)
for i in range(z+1,x+y+1):
  arr = fact(i)
  for j,k in arr:
    dic[j] = dic.get(j,0) + k

z = min(x,y)
for i in range(2,z+1):
  arr = fact(i)
  for j,k in arr:
    dic[j] = dic[j] - k


ans = 1
for i in dic:
  for _ in range(dic[i]):
    ans = (ans*i)%border
    
print(int(ans))

Submission status: Wrong Answer

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

i = 2 * X - Y
if i % 3 != 0:
    print('0')
else:
    y = (2 * X - Y) // 3
    x = X - 2 * y
    
    upcount = 1
    downcount = 1
    if x > y:
        for i in range(0, y):
            upcount *= (x + y - i)
            downcount *= (y - i)
    else:
        for i in range(0, x):
            upcount *= (x + y - i)
            downcount *= (x - i)
    count = upcount / downcount 
    count = int(count)
    print(count % (10 ** 9 + 7))

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
x,y = x-n,y-n
if x <= 0 or y <= 0:
    print(0)
    exit()

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

N = x+y
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

a = cmb(x+y,x,mod)
print(a)

Submission status: Wrong Answer

Solution code:

prime = 10**9+7

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

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

n = n // 3
m = m // 3

# (n+m)!/n!m!を求める
# n >= mにする
if n < m:
    n, m = m, n

# (n+m)*...*(n+1)
a = 1
for i in range(n+1, n+m+1):
    a = a * i % prime

# m!
b = 1
for i in range(1, m+1):
    b = b * i % prime

# bの逆数cを求める c = b^p-2
ans = 1
exp = prime - 2
while exp:
    if exp & 1:
        ans = ans*b%prime
    b = b**2%prime
    exp = exp >> 1


print(a*ans%prime)

Submission status: Wrong Answer

Solution code:
import math

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

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

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

if n < 0 or m < 0:
    print(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

print(cmb(n+m,m)%mod)

Submission status: Wrong Answer

Solution code:
import math

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

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

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

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

print(cmb(n+m,m)%mod)

Submission status: Wrong Answer

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

x,y = map(int,input().split())
n = (2*y-x)/3
m = (2*x-y)/3

if n <= 0 or m <= 0:
    print(0)
elif int(n) != n or int(m) != m:
    print(0)
else:
    n = int(n)
    m = int(m)
    mod = 10**9+7 #出力の制限
    N = n+m
    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+m,n,mod)
    print(ans)

Submission status: Wrong Answer

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

x,y = map(int,input().split())
n = (2*y-x)//3
m = (2*x-y)//3

if n <= 0 or m <= 0:
    print(0)
else:
    mod = 10**9+7 #出力の制限
    N = n+m
    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+m,n,mod)
    print(ans)

Submission status: Wrong Answer

Solution code:
X, Y = map(int, input().split())
p = 1
py = 1
if (X*2 - Y)%3 != 0 or (Y*2 - X)%3 != 0:
    print(0)
    exit()
else:
    X, Y = (X*2 - Y)//3, (Y*2 - X)//3
    waru = 1000000007
    for i in range(Y):
        p *= X + 1 + i
    for i in range(Y):
        py *= i+1
    p = (p // py) % waru
    print(p)

Submission status: Wrong Answer

Solution code:
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  assert(p > n)
  # p は素数である必要がある。典型的には 10**9 + 7 とか

  if n < k:
    return 0
  if n < 0 or k < 0:
    return 0

  fac = [1, 1]
  inv = [1, 1]
  finv = [1, 1]
  for i in range(2, n+k+1):
    fac.append(fac[i-1] * i % p)
    inv.append(p - inv[p%i] * (p//i) % p)
    finv.append(finv[i-1] * inv[i] % p)

  return fac[n] * (finv[k] * finv[n-k] % p) % p



#x, y = [int(c) for c in input().split()]
x, y = (999999, 999999)  # => 444826544

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

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

rem = 10**9 + 7
ans = comb(i + j, i, rem)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys


def extgcd(a, b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2] // w[2]
        r2 = w
        w2 = [r[0] - q * w[0], r[1] - q * w[1], r[2] - q * w[2]]
        r = r2
        w = w2
    return [w[0], w[1]]


def mod_inv(a, m):
    x = extgcd(a, m)[0]
    return (m + x % m) % m


def main():
    X, Y = map(int, input().split())
    C = 10**9 + 7

    if (X + Y) % 3 != 0:
        print(0)
        sys.exit()
    cnt = [0, 0]
    if Y / X >= 1:
        (i, j) = (1, 2)
        cnt[0] += 1
    else:
        (i, j) = (2, 1)
        cnt[1] += 1

    while (i, j) != (X, Y):
        if Y * i == X * j:
            i += 3
            j += 3
            cnt[0] += 1
            cnt[1] += 1
        elif Y * i > X * j:
            i += 1
            j += 2
            cnt[0] += 1
        else:
            i += 2
            j += 1
            cnt[1] += 1

        if i > X+1 or j > Y+1:
            print(0)
            sys.exit()

    ans = 1
    for i in range(1, sum(cnt) + 1):
        ans *= i
        ans %= C
    for i in range(1, cnt[0] + 1):
        ans *= mod_inv(i, C)
        ans %= C
    for i in range(1, cnt[1] + 1):
        ans *= mod_inv(i, C)
        ans %= C

    print(ans)


main()

Submission status: Wrong Answer

Solution code:
import sys


def extgcd(a, b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2] // w[2]
        r2 = w
        w2 = [r[0] - q * w[0], r[1] - q * w[1], r[2] - q * w[2]]
        r = r2
        w = w2
    return [w[0], w[1]]


def mod_inv(a, m):
    x = extgcd(a, m)[0]
    return (m + x % m) % m


def main():
    X, Y = map(int, input().split())
    C = 10**9 + 7

    if (X + Y) % 3 != 0:
        print(0)
        sys.exit()
    cnt = [0, 0]
    if Y / X >= 1:
        (i, j) = (1, 2)
        cnt[0] += 1
    else:
        (i, j) = (2, 1)
        cnt[1] += 1

    while (i, j) != (X, Y):
        if Y * i > X * j:
            i += 1
            j += 2
            cnt[0] += 1
        else:
            i += 2
            j += 1
            cnt[1] += 1
        if i > X+1 or j > Y+1:
            print(0)
            sys.exit()

    ans = 1
    for i in range(1, sum(cnt) + 1):
        ans *= i
        ans %= C
    for i in range(1, cnt[0] + 1):
        ans *= mod_inv(i, C)
        ans %= C
    for i in range(1, cnt[1] + 1):
        ans *= mod_inv(i, C)
        ans %= C

    print(ans)


main()

Submission status: Wrong Answer

Solution code:
import sys


def extgcd(a, b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2] // w[2]
        r2 = w
        w2 = [r[0] - q * w[0], r[1] - q * w[1], r[2] - q * w[2]]
        r = r2
        w = w2
    return [w[0], w[1]]


def mod_inv(a, m):
    x = extgcd(a, m)[0]
    return (m + x % m) % m


def main():
    X, Y = map(int, input().split())
    C = 10**9 + 7

    if (X + Y) % 3 != 0:
        print(0)
        sys.exit()
    cnt = [0, 0]
    if Y / X >= 1:
        (i, j) = (1, 2)
        cnt[0] += 1
    else:
        (i, j) = (2, 1)
        cnt[1] += 1

    while (i, j) != (X, Y):
        if Y / X > j / i:
            i += 1
            j += 2
            cnt[0] += 1
        else:
            i += 2
            j += 1
            cnt[1] += 1

        if X < i or Y < j:
            print(0)
            sys.exit()

    ans = 1
    for i in range(1, sum(cnt) + 1):
        ans *= i
        ans %= C
    for i in range(1, cnt[0] + 1):
        ans *= mod_inv(i, C)
        ans %= C
    for i in range(1, cnt[1] + 1):
        ans *= mod_inv(i, C)
        ans %= C

    print(ans)


main()

Submission status: Wrong Answer

Solution code:
import sys


def extgcd(a, b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2] // w[2]
        r2 = w
        w2 = [r[0] - q * w[0], r[1] - q * w[1], r[2] - q * w[2]]
        r = r2
        w = w2
    return [w[0], w[1]]


def mod_inv(a, m):
    x = extgcd(a, m)[0]
    return (m + x % m) % m


def main():
    X, Y = map(int, input().split())
    C = 10**9 + 7

    cnt = [0, 0]
    if Y / X >= 1:
        (i, j) = (1, 2)
        cnt[0] += 1
    else:
        (i, j) = (2, 1)
        cnt[1] += 1

    while (i, j) != (X, Y):
        if Y / X > j / i:
            i += 1
            j += 2
            cnt[0] += 1
        else:
            i += 2
            j += 1
            cnt[1] += 1

        if X < i or Y < j:
            print(0)
            sys.exit()

    ans = 1
    for i in range(1, sum(cnt) + 1):
        ans *= i 
        ans %= C
    for i in range(1, cnt[0] + 1):
        ans *= mod_inv(i, C)
        ans %= C
    for i in range(1, cnt[1] + 1):
        ans *= mod_inv(i, C)
        ans %= C

    print(ans)


main()

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb

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

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

N = (X+Y) // 3

A = X - N
B = Y - N

ans = comb(A+B, A) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:


dvi = 7+1e9

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

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

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

res = n+m

if n<m:
    for i in range(1,n):
        res *= n+m-i
        res //= i+1
else:
    for i in range(1,m):
        res *= n+m-i
        res //= i+1

print(int(res % dvi))

Submission status: Wrong Answer

Solution code:
import math
from math import factorial
from operator import mul
from functools import reduce
 
 
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 ((X + Y) %3!=0):
    print(0)
else :
    min_za = min(X, Y)
    max_za = max(X, Y)
    diff_2 = int((min_za * 2-max_za) / 3)
    diff_1 = max_za - diff_2*2
    sum = diff_1 + diff_2
    if (diff_1 >=0 and diff_2 >=0):
        print(comb(sum,diff_1,10**9+7))
    else:
        print(0)

Submission status: Wrong Answer

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

numna=(y-naname)//3
numyo=naname

mod=10**9+7

fac = [0]*1000000
inv = [0]*1000000
fac[0]=1
fac[1]=1
inv[0]=1
inv[1]=1

def powmod(x,y,m):
	ans=1
	while(y):
		if y%2==1:
			ans*=x
			ans%=m
		x*=x
		x%=m
		y//=2
	return ans

for i in range(2,10**6-5):
	fac[i] = fac[i-1]*i%mod
	inv[i] = powmod(fac[i],mod-1,mod)

def nCr(n,r):
	return fac[n]*inv[r]%mod*inv[n-r]%mod

print(nCr(numna*2+numyo,numna))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

next = lambda x, y: [(a, b) for a, b in [(x+1, y+2), (x+2, y+1)] if a <= X and b <= Y]

def bfs(x0, y0):
	visited = {(x0, y0), }
	que = deque()
	que.append((x0, y0))
	count = 0
	while que:
		x, y = que.popleft()
		if x==X and y==Y:
			count += 1
		for a, b in next(x, y):
			if (a, b) not in visited:
				que.append((a, b))
				visited.add((a, b))
	return count
print(bfs(0, 0))

Submission status: Wrong Answer

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


def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y/2)**2 % mod
    else            : return power(x, y/2)**2 * x % mod

def div(a, b):
    return mul(a, power(b, mod-2))
if X>Y:
    big=X
    small=Y
else:
    big=Y
    small=X


if (small+big)%3!=0:
    print(0)
    exit()
if small*2==big:
    print(small%mod)
    exit()
    
    
diff=big-small
big-=diff*2
small-=diff
if big<0 or big!=small:
    print(0)
    exit()

num=big//3
tmp=1
for i in range(num+diff,num*2+diff):
    tmp=(tmp*(i+1))%mod
bunsi=tmp
bunbo=1
tmp=1
for i in range(num):
    tmp=(tmp*(i+1))%mod
bunbo=pow(tmp,mod-2,mod)
#ans=div(bunsi,bunbo)
ans=bunsi*bunbo
print(ans%mod)