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 mod_comb(n, k, p):
    if k > n - k:
        k = n - k
    
    numerator = 1
    denominator = 1
    for i, j in zip(range(n - k + 1, n + 1), range(1, k + 1)):
        numerator = (numerator * i) % p
        denominator = (denominator * j) % p
    
    return (numerator * pow(denominator, p - 2, p)) % p

def solve():
    mod = 10 ** 9 + 7
    X, Y = map(int, input().split())
    if (2 * X - Y) % 3 == 0:
        s = (2 * Y - X) // 3
        t = (2 * X - Y) // 3
        
        print(mod_comb(s + t, s, mod))
    else:
        print(0)

solve()

Submission status: Wrong Answer

Solution code:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

X, Y = map(int, input().split())
if (X+Y)%3!=0:
  print(0)
  exit()
for i in range(X+1):
  n=int((X-i)/2)
  if Y==i*2+n*1:
    print(cmb(i+n,i)%1000000007)
    exit()

Submission status: Wrong Answer

Solution code:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

X, Y = map(int, input().split())
if (X+Y)%3!=0:
  print(0)
  exit()
for i in range(X+1):
  n=int((X-i)/2)
  if Y==i*2+n*1:
    ans=cmb(i+n,i)
    print(ans%1000000007)
    exit()

Submission status: Wrong Answer

Solution code:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

X, Y = map(int, input().split())
if (X+Y)%3!=0:
  print(0)
  exit()
for i in range(X):
  n=int((X-i)/2)
  if Y==i*2+n*1:
    ans=cmb(i+n,i)
    print(ans%1000000007)
    exit()

Submission status: Wrong Answer

Solution code:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

X, Y = map(int, input().split())
for i in range(X):
  if (X-i)%2!=0:
    continue
  n=int((X-i)/2)
  if Y==i*2+n*1:
    ans=cmb(i+n,i)
    print(ans%1000000007)
    exit()

print(0)

Submission status: Wrong Answer

Solution code:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

X, Y = map(int, input().split())
for i in range(X):
  if (X-i)%2!=0:
    continue
  n=int((X-i)/2)
  if Y==i*2+n*1:
    ans=cmb(i+n,i)
    print(ans%1000000007)
    exit()
    
print(X,Y)

Submission status: Wrong Answer

Solution code:
import numpy as np
MOD = 10**9 + 7
def extgcd(a, b):
    r = np.array([1,0,a], dtype=int)
    w = np.array([0,1,b], dtype=int)
    while w[2] != 1:
        q = r[2] // w[2]
        r, w = w, r - q*w
    return w[:2]

def mod_inverse(a, m):
    x, y = extgcd(a, m)
    return (m + x % m) % m

def solve(x, y):
    a = -y + 2*x
    b = 2*y - x
    if a % 3 != 0:
        return 0
    if b % 3 != 0:
        return 0
    a //= 3
    b //= 3
    n, k = a+b, a
    p, q = 1, 1
    for i in range(k):
        p = p * (n-i) % MOD
        q = q * (i+1) % MOD
    return (p * mod_inverse(q, MOD)) % MOD

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

Submission status: Wrong Answer

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


def comb_mod(n, k, mod):
    if k > n or k < n:
        return 0
    fact_n = factorial_mod(n, mod)
    fact_k = factorial_mod(k, mod)
    fact_n_k = factorial_mod(n - k, mod)
    return (fact_n * pow(fact_k, mod - 2, mod) * pow(fact_n_k, mod - 2, mod)) % mod


def main():
    x, y = map(int, input().split())
    MOD = 10 ** 9 + 7
    if (2 * x - y) % 3 != 0 or (2 * y - x) % 3 != 0:
        print(0)
        exit()
    i = (2 * x - y) // 3
    j = (2 * y - x) // 3
    print(comb_mod(i + j, i, MOD))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


def comb_mod(n, k, mod):
    if k > n:
        return 0
    fact_n = factorial_mod(n, mod)
    fact_k = factorial_mod(k, mod)
    fact_n_k = factorial_mod(n - k, mod)
    return (fact_n * pow(fact_k, mod - 2, mod) * pow(fact_n_k, mod - 2, mod)) % mod


def main():
    x, y = map(int, input().split())
    MOD = 10 ** 9 + 7
    if (2 * x - y) % 3 != 0 or (2 * y - x) % 3 != 0:
        print(0)
        exit()
    i = (2 * x - y) // 3
    j = (2 * y - x) // 3
    print(comb_mod(i + j, i, MOD))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math

def main():
    X,Y = map(int,input().split())
    MOD = 10**9+7
    K = (2*X-Y)/3
    L = (2*Y-X)/3
    if K == int(K) and L == int(L):
        A = int(K)+int(L)
        B = min(int(K),int(L))
        num = num_ = 1
        for i in range(1,B+1):
            num = num * (A+1-i) % MOD
            num_ = num_ * i % MOD
        ans = num * pow(num_,MOD-2,MOD) % MOD
        print(ans)

    else:
        print(0)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
x,y = map(int, input().split())
mod = 10**9+7
a = (x + y) //3
n = (2*x-y)//3
m = a-n

def nCr(n,r,mod):
    r = min(r, n-r)
    fact = rial=1
    for i in range(1,r+1):
        fact *= (n+1-i) % mod
        rial *= i %mod
    return fact * pow(rial,mod-2,mod) %mod
    
if (x + y) %3 == 0:
    if 0 < n and 0 < m and (x+y)%3==0:
       
        print(nCr(a,n,mod))
        
    else: 
        print(0)
    
else:
    print(0)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
x,y = map(int, input().split())
def factorial(a,b):
    fact = 1
    for i in range(b):
        fact *= (a-i)
    return fact
    
if (x + y) %3 == 0:
    if (0< (2*y - x)//3) and (2*y - x)%3 == 0 and (0 < (2*x-y)//3) and (2*x-y)%3==0:
        n = int((2*y - x)//3)
        m = int((2*x-y)//3)
        print(n,m)
        ans = int(factorial((n+m),n) / factorial(n,n))
        print(ans%(10**9+7))
    else: 
        print("0")
    
else:
    print("0")

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def main():
    
    x, y = map(int, readline().split())
    if (x+y)%3!=0:
        print(0)
        return
    n = (x+y)//3
    o = cmb(n, min((2*y-x)//3, (2*x-y)//3))
    o = o % (10**9+7)
    print(o)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

xy = input().rstrip().split(" ")
x = int(xy[0])
y = int(xy[1])
if (x + y) % 3 != 0:
    print(0)
else:
    n = int((2 * y - x) / 3)
    m = int((2 * x - y) / 3)
    if n >= 0 and m >= 0:
        ans = (cmb(n + m, n)) / (10 ** 9 + 7)
        print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7

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

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

if not ((2 * X - Y) % 3 == 0 and (2 * Y - X) % 3 == 0 and a > 0 and b > 0):
    print(0)
    exit()

maxf = a + b + 1
f = [1 for _ in range(maxf)]
invf = [1 for _ in range(maxf)]

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

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


def comb(a, b):
    return (f[a + b] * invf[a] * invf[b]) % MOD


print(comb(a, b))

Submission status: Wrong Answer

Solution code:
def extgcd(a, b):
    if b == 0:
        return [1, 0, a]
    x, y, g = extgcd(b, a % b)
    return [y, x - a//b * y, g]


def mod_inverse(a, m):
    x, y, _ = extgcd(a, m)
    return (m + x % m) % m


def mod_comb(n, k, mod):
    mul, div = 1, 1
    for i in range(k):
        mul *= (n-i)
        div *= (i+1)
        mul %= mod
        div %= mod
    return mul * mod_inverse(div, mod) % mod


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

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

al = (X + Y) // 3
ch = (2 * Y - X) // 3
print(mod_comb(al, ch, int(1e9+7)))

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():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    x, y = list(map(int, input().rstrip('\n').split()))
    if (x + y) % 3 == 0:
        cnt = (x + y) // 3
        for i in range(0, cnt + 1):
            if (cnt - i) + i * 2 == x and (cnt - i) * 2 + i == y and cnt - i >= 0:
                print(alg_combination_mod(cnt, i, mod))
    else:
        print(0)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import math
import sys

# スペース区切りの整数の入力
X, Y = map(int, input().split())

#X = 999999
#Y = 999999
BIGCONST = 10**9 + 7

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

def factmod(a, m):
    # a! mod m
    
    tmp = 1
    for i in range(1, a+1):
        tmp *= i
        if tmp > m:
            tmp %= m
            
    tmp %= m
    
    return tmp

def calc(X, Y):
    n_bunshi = 2*X - Y
    m_bunshi = 2*Y - X
    
    if n_bunshi % 3 != 0 or n_bunshi < 0:
        return 0
    
    if m_bunshi % 3 != 0 or m_bunshi < 0:
        return 0
    
    n = n_bunshi // 3
    m = m_bunshi // 3
    
    if n == 0 and m == 0:
        return 0
    else:
        print(n, m)
    
    bunshi = factmod(n+m, BIGCONST)
    work   = bunshi * modinv(math.factorial(n), BIGCONST) % BIGCONST
    answer = work   * modinv(math.factorial(m), BIGCONST) % BIGCONST
    
    #print(bunshi, work, answer)
    
    return answer
 
print(calc(X,Y))

Submission status: Wrong Answer

Solution code:
import math
import sys

# スペース区切りの整数の入力
X, Y = map(int, input().split())

#X = 999999
#Y = 999999
BIGCONST = 10**9 + 7

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

def factmod(a, m):
    # a! mod m
    
    tmp = 1
    for i in range(1, a+1):
        tmp *= i
        if tmp > m:
            tmp %= m
            
    tmp %= m
    
    return tmp

def calc(X, Y):
    n_bunshi = 2*X - Y
    m_bunshi = 2*Y - X
    
    if n_bunshi % 3 != 0 or n_bunshi < 0:
        return 0
    
    if m_bunshi % 3 != 0 or m_bunshi < 0:
        return 0
    
    n = n_bunshi // 3
    m = m_bunshi // 3
    
    if n == 0 and m == 0:
        return 0
    else:
        print(n, m)
    
    bunshi = factmod(n+m, BIGCONST)
    work   = bunshi * modinv(factmod(n, BIGCONST), BIGCONST) % BIGCONST
    answer = work   * modinv(factmod(m, BIGCONST), BIGCONST) % BIGCONST
    
    #print(bunshi, work, answer)
    
    return answer
 
print(calc(X,Y))

Submission status: Wrong Answer

Solution code:
import sys
import math
import numpy as np
# スペース区切りの整数の入力
X, Y = map(int, input().split())

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

def factmod(a, m):
    # a! mod m
    
    tmp = 1
    for i in range(1, a+1):
        tmp *= i
        if tmp > m:
            tmp %= m
            
    tmp %= m
    
    return tmp

def calc(X, Y):
    n_bunshi = 2*X - Y
    m_bunshi = 2*Y - X
    
    if n_bunshi % 3 != 0 or n_bunshi < 0:
        return 0
    
    if m_bunshi % 3 != 0 or m_bunshi < 0:
        return 0
    
    n = n_bunshi // 3
    m = m_bunshi // 3
    
    bunshi = factmod(n+m, BIGCONST)
    work   = bunshi * modinv(n, BIGCONST) % BIGCONST
    answer = work   * modinv(m, BIGCONST) % BIGCONST
    
    # print(bunshi, work, answer)
    
    return answer
 
print(calc(X,Y))

Submission status: Wrong Answer

Solution code:
def Factorial(p, q):  # Factorial from p to q
  p = int(p)
  q = int(q)
  res = 1
  for i in range(p, q+1):
    res *= i
  return res

def Duplicate(l, m):
  l = int(l)
  m = int(m)
  max_val = max(l, m)
  min_val = min(l, m)
  return Factorial(max_val+1, l+m) / Factorial(1,min_val)



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:
  print(0)
else:
  print(int(Duplicate(x, y)) % (10^9 + 7))

Submission status: Wrong Answer

Solution code:
from math import factorial
mod = 10**9+7
def comb(n,k,p):
    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):
    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)
else:
    n = (2*x - y)//3
    m = (2*y - x)//3
    if min(n,m) < 0:
        print(0)
        #exit()
    ans = comb(n+m , n , mod)
    print(ans)

Submission status: Wrong Answer

Solution code:
X,Y = map(int,input().split())
a = (2*Y-X)//3
b = (2*X-Y)//3
if (X+Y)%3 != 0:
    print(0)
elif a < 0 or b < 0:
    print(0)
else:
    akai = 1
    abkai = 1
    
    for i in range(1, a+1):
        akai *= i

    for k in range(a+1, a+b+1):
        abkai *= k

    print(abkai//akai%(10**9+7))

Submission status: Wrong Answer

Solution code:
X,Y = map(int,input().split())
a = (2*Y-X)//3
b = (2*X-Y)//3
if (X+Y)%3 != 0:
    print(0)
elif a < 0 or b < 0:
    print(0)
else:
    akai = 1
    abkai = 1
    
    for i in range(1, a+1):
        akai *= i
    akai %= 10**9+7
    for k in range(a+1, a+b+1):
        abkai *= k
    abkai %= 10**9+7
    print(abkai//akai%(10**9+7))

Submission status: Wrong Answer

Solution code:
X,Y = map(int,input().split())
a = (2*Y-X)//3
b = (2*X-Y)//3
if (X+Y)%3 != 0:
    print(0)
elif a < 0 or b < 0:
    print(0)
else:
    akai = 1
    abkai = 1
    
    for i in range(1, a+1):
        akai *= i
    akai %= 10**9+7
    for k in range(a+1, a+b+1):
        abkai *= k
    abkai %= 10**9+7
    print(abkai//akai)

Submission status: Wrong Answer

Solution code:
def multiple_of_n(x, y, n=3):
    return (x - y) % n == 0

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

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

mod = 10 ** 9 + 7

x, y = map(int, input().split())
if multiple_of_n(2 * x, y) and multiple_of_n(2 * y, x):
    vertical = (2 * y - x) // 3
    horizontal = (2 * x - y) // 3
    total = vertical + horizontal
    g1, g2, inverse = make_inv(mod, total)
    print(combination(g1, g2, inverse, total, horizontal, mod))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
def multiple_of_n(x, y, n=3):
    return (x - y) % n == 0

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

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

mod = 10 ** 9 + 7

x, y = map(int, input().split())
if multiple_of_n(2 * x, y) and multiple_of_n(2 * y, x):
    vertical = (2 * y - x) // 3
    horizontal = (2 * x - y) // 3
    total = vertical + horizontal
    g1, g2, inverse = make_inv(mod, total)
    combination(g1, g2, inverse, total, horizontal, mod)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
def multiple_of_n(x, y, n=3):
    return (x - y) % n == 0

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

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

mod = 10 ** 9 + 7

x, y = map(int, input().split())
if multiple_of_n(2 * x, y) and multiple_of_n(2 * y, x):
    vertical = (2 * y - x) // 3
    horizontal = (2 * x - y) // 3
    total = vertical + horizontal
    g1, g2, inverse = make_inv(mod, total)
    combination(g1, g2, inverse, total, horizontal, mod)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7

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

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

def nCr(n, r, mod):
    r = min(r, n-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

print(n, m)
if n >= 0 and m >= 0:
    print(nCr(n + m, n, MOD))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7

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

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

def nCr(n, r, mod):
    r = min(r, n-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

if n > 0 and m > 0:
    print(nCr(n + m, n, MOD))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7

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

def nCr(n, r, mod):
    r = min(r, n-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

if n > 0 and m > 0:
    print(nCr(n + m, n, MOD))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
p = 10**9+7
 

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

def kai(x, p):
    a = 1
    for i in range(1, x + 1):
        a *= i
        a %= p
    return a
 
 
def comb(a, b, p):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= kai(a, p)
    c *= pow(kai(b, p), p - 2, p)
    c *= pow(kai(a - b, p), p - 2, p)
    return c % p
 
print(comb(n + m, n, p))

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7
 
x, y = map(int, input().split())
n = int((2 * x - y) / 3)
m = int(x - 2 * n)

def nCr(n, r, mod):
    r = min(r, n-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

print(nCr(n + m, n, MOD))

Submission status: Wrong Answer

Solution code:
X, Y = map(int, input().split())
import math
a = 2*Y -X
b = 2*X -Y
if a % 3 == 0 and b % 3 == 0 and a > 0 and b > 0:
  k = a // 3
  l = b // 3
  c = max(k, l)
  d = min(k, l)
  sita = math.factorial(d)
  ue = 1
  for i in range(c + 1, c + d + 1):
    ue = ue * i
  total = ue // sita
  print(total % (7 + 10 ** 9))
else:
  print(0)

Submission status: Wrong Answer

Solution code:
X, Y = map(int, input().split())
import math
a = 2*Y -X
b = 2*X -Y
if a % 3 == 0 and b % 3 == 0 and a > 0 and b > 0:
  k = a // 3
  l = b // 3
  ue = math.factorial(k+l)
  sita_1 = math.factorial(k)
  sita_2 = math.factorial(l)
  total = ue // (sita_1 * sita_2)
  print(total % (7 + 10 ** 9))
else:
  print(0)

Submission status: Wrong Answer

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

mod = 10**9 + 7

# import math
# def comb(n,r):
#     return (math.factorial(n)//(math.factorial(n-r)*math.factorial(r)))

# def comb(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

def comb_mod(n, r, mod):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    else:
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, n + 1):
            fac.append(fac[-1] * i % mod)
            inv.append(-inv[mod % i] * (mod // i) % mod)
            finv.append((finv[-1] * inv[-1]) % mod)
        return int(fac[n] * finv[r] * finv[n - r] % mod)


# def comb(n,r,mod):
# 	'''
# 	return nCr
# 	O(min{n-r, r})
# 	'''
# 	a=1
# 	b=1
# 	r = min(r,n-r)
# 	for i in range(r):
# 		a = a*(n-i)%mod
# 		b = b*(i+1)%mod
# 	return a*pow(b,mod-2,mod)%mod

if (x+y)%3!=0:
    print(0)
    exit()
else:
    n = int((2/3)*x - (1/3)*y)
    m = int((2/3)*y - (1/3)*x)
    if n>=0 and m>=0:
        print(comb_mod(n+m,m,mod))
        exit()
    else:
        print(0)
        exit()

Submission status: Wrong Answer

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

mod = 10**9 + 7

# import math
# def comb(n,r):
#     return (math.factorial(n)//(math.factorial(n-r)*math.factorial(r)))

def comb(n,r,mod):
	'''
	return nCr
	O(min{n-r, r})
	'''
	a=1
	b=1
	r = min(r,n-r)
	for i in range(r):
		a = a*(n-i)%mod
		b = b*(i+1)%mod
	return a*pow(b,mod-2,mod)%mod

if (x+y)%3!=0:
    print(0)
    exit()
else:
    n = int((2/3)*x - (1/3)*y)
    m = int((2/3)*y - (1/3)*x)
    if n>=0 and m>=0:
        print(comb(n+m,m,mod))
        exit()
    else:
        print(0)
        exit()

Submission status: Wrong Answer

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

mod = 10**9 + 7

# import math
# def comb(n,r):
#     return (math.factorial(n)//(math.factorial(n-r)*math.factorial(r)))

def comb(n,r,mod):
	'''
	return nCr
	O(min{n-r, r})
	'''
	a=1
	b=1
	r = min(r,n-r)
	for i in range(r):
		a = a*(n-i)%mod
		b = b*(i+1)%mod
	return a*pow(b,mod-2,mod)%mod

if (x+y)%3!=0:
    print(0)
    exit()
else:
    n = (2/3)*x - (1/3)*y
    m = (2/3)*y - (1/3)*x
    if n>=0 and m>=0:
        print(comb(int(n+m),int(m),mod))
        exit()
    else:
        print(0)
        exit()

Submission status: Wrong Answer

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

mod = 10**9 + 7

# import math
# def comb(n,r):
#     return (math.factorial(n)//(math.factorial(n-r)*math.factorial(r)))

def comb(n,r,mod):
	'''
	return nCr
	O(min{n-r, r})
	'''
	a=1
	b=1
	r = min(r,n-r)
	for i in range(r):
		a = a*(n-i)%mod
		b = b*(i+1)%mod
	return a*pow(b,mod-2,mod)%mod

if (x+y)%3!=0:
    print(0)
    exit()
else:
    n = (2/3)*x - (1/3)*y
    m = (2/3)*y - (1/3)*x
    print(comb(int(n+m),int(m),mod))
    exit()

Submission status: Wrong Answer

Solution code:
a,b = map(int, input().split())
tried = (a + b)//3
p = 10**9 +7

if a < tried or b < tried or (a+b)%3 != 0:
    print(0)
    quit()
one = int((2 * a -  b)/3)
print(one)
n = tried
r = min(one, tried-one)
n_fac = 1
r_fac = 1
n_r_fac = 1

for i in range(2,n+1):
    n_fac *= i
    n_fac %= p
for i in range(2,r+1):
    r_fac *= i
    r_fac %= p
for i in range(2,n-r+1):
    n_r_fac *= i
    n_r_fac %= p
r_fac_inverse = pow(r_fac, p-2, p)
n_r_fac_inverse = pow(n_r_fac, p-2, p)

print((n_fac * r_fac_inverse * n_r_fac_inverse)%p)

Submission status: Wrong Answer

Solution code:
a,b = map(int, input().split())
tried = (a + b)//3
p = 10**9 +7

if a < tried or b < tried or (a+b)%3 != 0:
    print(0)
    quit()
one = int((2/3)* a - (1/3)* b)
n = tried
r = min(one, tried-one)
n_fac = 1
r_fac = 1
n_r_fac = 1

for i in range(2,n+1):
    n_fac *= i
    n_fac %= p
for i in range(2,r+1):
    r_fac *= i
    r_fac %= p
for i in range(2,n-r+1):
    n_r_fac *= i
    n_r_fac %= p
r_fac_inverse = pow(r_fac, p-2, p)
n_r_fac_inverse = pow(n_r_fac, p-2, p)

print((n_fac * r_fac_inverse * n_r_fac_inverse)%p)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def nCr(n, r):
    if n - r < r:
        return nCr(n, n - r)
    if r == 0:
        return 1

    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    for i in range(2, int(n ** 0.5) + 2):
        if primes[i]:
            for j in range(i * 2, n + 1, i):
                primes[j] = False
    primes = [i for i, b in enumerate(primes) if b]

    factors1 = defaultdict(lambda: 0)
    for p in primes:
        num = n
        while p <= num:
            factors1[p] += num // p
            num //= p

    factors2 = defaultdict(lambda: 0)
    for p in primes:
        num = r
        while p <= num:
            factors2[p] += num // p
            num //= p

    factors3 = defaultdict(lambda: 0)
    for p in primes:
        num = n - r
        while p <= num:
            factors3[p] += num // p
            num //= p

    value = 1
    for p in factors1:
        value *= p ** (factors1[p] - (factors2[p] + factors3[p]))

    return value


X, Y = map(int, input().split())
if (2 * Y - X) % 3 != 0 or (2 * X - Y) % 3 != 0:
    print(0)
else:
    a = (2 * X - Y) // 3
    b = (2 * Y - X) // 3
    n = a + b
    print(nCr(n, a) % (10 ** 9 + 7))

Submission status: Wrong Answer

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

def cnb(n,k,p):
  if k>n:
    return 0
  c,d=1,1
  for i in range(k+1,n+1):
    c = (c*i)%p
  for i in range(1,k+1):
    d = (d*i)%p
  return (c*pow(d,p-2,p))%p

p=10**9+7
ans=0
if X > 2*Y or Y > 2*X:
  pass
elif (X+Y)%3:
  pass
else:
  ans=cnb((X+Y)//3,(2*Y-X)//3,p)

print(ans)

Submission status: Wrong Answer

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

def cnb(n,k,p):
  if k>n:
    return 0
  c,d=1,1
  for i in range(k+1,n+1):
    c = (c*i)%p
  for i in range(1,k+1):
    d = (d*i)%p
  return (c*pow(d,p-2,p))%p

p=10**9+7
if (X+Y)%3 != 0 or X > 2*Y or Y > 2*X:
  print(0)
else:
  ab=(X+Y)//3
  print(cnb(ab,X-ab,p))

Submission status: Wrong Answer

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

def cnb(n,k,p):
  if k>n:
    return 0
  if n-k>k:
    k=n-k
  c,d=1,1
  for i in range(k+1,n+1):
    c = (c*i)%p
  for i in range(1,k+1):
    d = (d*i)%p
  return (c*pow(d,p-2,p))%p

p=10**9+7
if (X+Y)%3!=0 or X > 2*Y or Y > 2*X:
  print(0)
else:
  ab=(X+Y)//3
  print(cnb(ab,X-ab,p))

Submission status: Wrong Answer

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

def cnb(n,k,p):
  if k>n:
    return 0
  c,d=1,1
  for i in range(k+1,n+1):
    c = (c*i)%p
  for i in range(1,k+1):
    d = (d*i)%p
  return (c*pow(d,p-2,p))%p

p=10**9+7
if (X+Y)%3!=0 or X > 2*Y or Y > 2*X:
  print(0)
else:
  ab=(X+Y)//3
  print(cnb(ab,X-ab,p))

Submission status: Wrong Answer

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

def cnb(n,k,p):
  if k>n:
    return 0
  c,d=1,1
  for i in range(k+1,n+1):
    c = (c*i)%p
  for i in range(1,k+1):
    d = (d*i)%p
  return (c*pow(d,p-2,p))%p

p=10**9+7
if (X+Y)%3!=0 or X > 2*Y or Y > 2*X:
  print(0)
else:
  ab=(X+Y)//3
  a=(-X+2*Y)//3
  print(cnb(ab,a,p))

Submission status: Wrong Answer

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