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:
X,Y=map(int,input().split())
p=10**9+7
a=(-X+2*Y)/3
b=(-Y+2*X)/3
if (X+Y)%3!=0 or a < 0 or b < 0:
  print(0)
else:
  a=(-X+2*Y)//3
  b=(-Y+2*X)//3
  n=1
  for i in range(a+1,a+b+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)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
X,Y=map(int,input().split())
p=10**9+7
a=(-X+2*Y)/3
b=(-Y+2*X)/3
if float(int(a))!=a or float(int(b))!=b or a < 0 or b < 0:
  print(0)
else:
  a=int(a)
  b=int(b)
  n=1
  for i in range(a+1,a+b+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)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

# -*- coding: utf-8 -*-


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret

    def perm(self, n, r):
        """
        nPrの値を返す
        """
        ret = self.f[n] * self.inv[n-r]
        ret %= self.mod
        return ret


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

y = (2*Y-X)/3
x = (2*X-Y)/3
F = FactMod(X+Y, 10**9+7)

if 0 <= x and x == int(x) and 0 <= y and y == int(y):
    ans = F.comb(X+Y, X)
else:
    ans = 0
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

# -*- coding: utf-8 -*-


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret

    def perm(self, n, r):
        """
        nPrの値を返す
        """
        ret = self.f[n] * self.inv[n-r]
        ret %= self.mod
        return ret


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

x = (2*Y-X)/3
y = (2*X-Y)/3
F = FactMod(X+Y, 10**9+7)

if 0 <= x and x == int(x) and 0 <= y and y == int(y):
    ans = F.comb(X+Y, X)
else:
    ans = 0
print(ans)

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()
if abs(a-b) == 0:
    one = tried//2
else:
    one = abs(a-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:
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()
if abs(a-b) == 0:
    one = tried//2
else:
    one = abs(a-b)
n = tried
r = min(one, tried-one)
print(n,r)
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:
MOD = 1000000007
MAX = 2*10**6  # max n

fac = [0 for _ in range(MAX)]  # = n! (mod MOD)
finv = [0 for _ in range(MAX)]  # = 1/r! (mod MOD)
inv = [0 for _ in range(MAX)]  # = 1/r (mod MOD)


# init
def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD


# nCk, n < [0, MAX), k < [0, n]
def COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

def main():
    # input
    x, y = map(int, input().split())
    if (x+y)%3 == 0:
        num = (x+y)//3
        for i in range(num):
            if i + 2*(num-i) == x and 2*i + (num-i) == y:
                move = i
                break
        else:
            print(0)
            return
    else:
        print(0)
        return

    # calc
    COMinit()
    print(COM(num, move))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
MOD = 1000000007
MAX = 10**6  # max n

fac = [0 for _ in range(MAX)]  # = n! (mod MOD)
finv = [0 for _ in range(MAX)]  # = 1/r! (mod MOD)
inv = [0 for _ in range(MAX)]  # = 1/r (mod MOD)


# init
def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD


# nCk, n < [0, MAX), k < [0, n]
def COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

def main():
    # input
    x, y = map(int, input().split())
    if (x+y)%3 == 0:
        num = (x+y)//3
        for i in range(num):
            if i + 2*(num-i) == x and 2*i + (num-i) == y:
                move = i
                break
        else:
            print(0)
            return
    else:
        print(0)
        return

    # calc
    COMinit()
    print(COM(num, move))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math

x,y = map(int, input().split())
# (i,j)->(i+1,j+2) continues a times.
# (i,j)->(i+2,j+1) continues b times.
temp = 2*x-y

a = -1
b = -1
if temp%3==0 and temp>=0:
  b = temp//3
  if x-2*b>=0:
    a = x-2*b

if a==-1 or b==-1:
  print(0)
else:
  #このままではansは非常に大きい数になりメモリ使用量が大きくなる。
  #よって、メモリ使用量削減のために"逆元とフェルマーの小定理"を活用する。
  A = 1
  B = 1
  mod = 10**9+7
  for i in range(min(a,b)):
    A *= a+b-i
    A %= mod
    B *= i+1
    B %= mod
    print(A*pow(B,mod-2,mod)%mod)

Submission status: Wrong Answer

Solution code:
from itertools import permutations, combinations,combinations_with_replacement,product

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

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

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

def combination(n, r):
    r = min(r, n - r)
 
    num = 1
    den = 1
 
    for i in range(1, r + 1):
        num = num * (n + 1 - i) % MOD
        den = den * i % MOD
 
    return num * pow(den, MOD - 2, MOD) % MOD

print(int(combination(m + n, n)) % MOD)

Submission status: Wrong Answer

Solution code:
X,Y=map(int,input().split())
A,B=1,1
mod=10**9+7
if (X+Y)%3 ==0:
    x=(2*Y-X)//3
    y=(2*X-Y)//3
    if min(x,y) !=0:
      for i in range(min(x,y)):
        A*=(x+y-i)
        A%=mod
        B*=(i+1)
        B%=mod
      print(A*pow(B,mod-2,mod)%mod)
    else:
      print(1)
else:
  print(0)

Submission status: Wrong Answer

Solution code:
X,Y=map(int,input().split())
A,B=1,1
mod=10**9+7
if (X+Y)%3 ==0:
    x=(2*Y-X)//3
    y=(2*X-Y)//3
    for i in range(min(x,y)):
      A*=(x+y-i)
      A%=mod
      B*=(i+1)
      B%=mod
    print(A*pow(B,mod-2,mod)%mod)
else:
  print(0)

Submission status: Wrong Answer

Solution code:
import sys


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


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    x, y = list(map(int, readline().split()))
    if (x + y) % 3 != 0 or x <0 or y < 0:
        print(0)
    else:
        c = (x + y) // 3
        for i in range(c+1):
            xv = i * 1 + (c - i) * 2
            yv = i * 2 + (c - i) * 1
            if xv == x and yv == y:
                print(alg_combination_mod(c, i, mod))
                exit()


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
x,y = map(int,input().split())
m = 10**9+7
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
    #[x,y]
    return [w[0],w[1]]
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m
if (2*y-x) % 3 != 0 or (2*x-y) % 3 != 0:
  print(0)
else:
  res = 1
  k,l = (2*y-x)//3,(2*x-y)//3
  for i in range(1,k+l+1):
    res = res*i%m
  for i in range(1,k+1):
    res = res*mod_inv(i,m)%m
  for i in range(1,l+1):
    res = res*mod_inv(i,m)%m
  print(res)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
x, y = map(int, input().split())

ans = 0
cnt = int((x + y) / 3)

if (x + y) % 3 != 0:
    ans = 0
elif x < cnt or x > 2 * cnt:
    ans = 0
else:
    m = int((2 * y - x) / 3) 
    n = cnt - m
    print(m)
    print(n)
    modulo = (10 ** 9) + 7
    fact_numer = 1
    fact_denom = 1
    for i in range(1, n+1):
        fact_numer = (fact_numer * (m + i)) % modulo
        #fact_denom = (fact_denom * i) % modulo
        temp = 1
        for j in range(1, modulo - 2 + 1):
            temp = (temp * i) % modulo
        fact_denom = (fact_denom * temp) % modulo

    fact_numer = fact_numer + modulo * fact_denom
#        print(fac)
    ans = (fact_numer * fact_denom) % modulo

print(ans)

Submission status: Wrong Answer

Solution code:
# D - Knight

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

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

# https://qiita.com/derodero24/items/91b6468e66923a87f39f
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

if a%1 != 0 or b%1 != 0:
    print(0)
else:
    m = 10**9 + 7
    a = int(max(a, b))
    b = int(min(a, b))

    ans = cmb(a+b, b, mod)
    print(ans)

Submission status: Wrong Answer

Solution code:
# D - Knight

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

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

#https://juppy.hatenablog.com/entry/2018/11/09/%E8%9F%BB%E6%9C%AC_python_mod_10%2A%2A9%2B7_%E9%80%86%E5%85%83_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_1
#互いに素なa,bについて、a*x+b*y=1の一つの解
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
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

if a%1 != 0 or b%1 != 0:
    print(0)
else:
    m = 10**9 + 7
    a = int(max(a, b))
    b = int(min(a, b))

    res = 1
    for i in range(1,a+b+1):
        res = res*i%m
    for i in range(1,a+1):
        res = res*mod_inv(i,m)%m
    for i in range(1,b+1):
        res = res*mod_inv(i,m)%m
    print(res)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
x, y = map(int, input().split())

# 10 ** 9 + 7 is prime?

ans = 0
cnt = int((x + y) / 3)

if (x + y) % 3 != 0:
    ans = 0
elif x < cnt or x > 2 * cnt:
    ans = 0
else:
    m = int((2 * y - x) / 3) 
    n = cnt - m
    print(m)
    print(n)
    modulo = (10 ** 9) + 7
    fact_numer = 1
    fact_denom = 1
    for i in range(1, n+1):
        fact_numer = (fact_numer * (m + i)) % modulo
        fact_denom = (fact_denom * i) % modulo
    
    fact_numer = fact_numer + modulo * fact_denom
#        print(fac)
    ans = int(fact_numer/ fact_denom) % modulo

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
X, Y=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
MOD = 10**9 + 7
if (X+Y)%3 != 0:
    print(0)
else:

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

    # print(f"n:{n}, m:{m}")

    if n<0 or m<0:
        print(0)
    else:
        ret = 1
        for i in range(m):
            ret = ret * ((X+Y) - i) % MOD * pow(i + 1, MOD-2, MOD) % MOD
        print(ret)

Submission status: Wrong Answer

Solution code:
x, y = [int(i) for i in input().split()]
if (x+y) % 3 != 0:
  print(0)
a = x - (2*y)
print(3.3%1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
x, y = map(int, input().split())

# 10 ** 9 + 7 is prime?

ans = 0
cnt = int((x + y) / 3)

if (x + y) % 3 != 0:
    ans = 0
elif x < cnt or x > 2 * cnt:
    ans = 0
else:
    m = int((2 * y - x) / 3) 
    n = cnt - m
    modulo = (10 ** 9) + 7
    fact = 1
    for i in range(1, n+1):
        fact = (fact * (m + i) / i) % modulo
    ans = int(fact)

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
x, y = map(int, input().split())

# 10 ** 9 + 7 is prime?

ans = 0
cnt = int((x + y) / 3)

if (x + y) % 3 != 0:
    ans = 0
elif x < cnt or x > 2 * cnt:
    ans = 0
else:
    m = int((2 * y - x) / 3) 
    n = cnt - m
    print(m)
    print(n)
    modulo = (10 ** 9) + 7
    fact = 1
    for i in range(1, n+1):
        fact = (fact * (m + i) / i) % modulo
    ans = int(fact)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


class Solver(object):
    def __init__(self):
        pass

    def solve(self, x: int, y: int):
        if (x + y) % 3 != 0:
            return 0
        A = np.matrix([[1, 2],
                       [2, 1]])
        Y = np.matrix([[x],
                       [y]])
        m, n = np.linalg.solve(A, Y)
        return self.cmb(int(m)+int(n), int(n)) % (10**9 + 7)

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

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

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

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

        return result


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

    solver = Solver()
    print(solver.solve(X, Y))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
X,Y=map(int,input().split())
mult1=1
mult2=1
if (2*Y-X)%3 ==0:
    x=(2*Y-X)//3
    y=(2*X-Y)//3
    for i in range(min(x,y)):
        mult1*=(x+y-i)
        mult2*=min(x,y)-i
    print((mult2//mult1)%(10**9+7))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
# 拡張ユークリッド互除法を用いて逆元を求める
def modinv(a, m):
    b = m; x0 = 1; x1 = 0
    while b:
        q = a//b
        a, b = b, a%b
        x0, x1 = x1, x0 - q*x1
    return x0%m 


x, y = map(int, input().split())
if (x + y)%3 != 0:
    print(0)
else:
    k = (x + y)//3
    if k <= x <= 2*k:
        i = min(x - k, 2*k - x)
        # 結局 コンビネーションkCiに帰着
        MOD = 10**9 + 7
        # まず階乗のmodを求める
        fac = [1]*(k + 1)
        for j in range(2, k + 1):
            fac[j] = fac[j - 1]*j%MOD
        # 次に階乗の逆元を求める
        finv = [0]*(k + 1)
        #finv[k] = pow(fac[k], MOD - 2, MOD) # fac[k]の逆元, フェルマーの小定理
        finv[k] = modinv(fac[k], MOD)
        for j in range(k, min(i, i - k), - 1):
            finv[j - 1] = finv[j]*j%MOD

        print(fac[k] * (finv[i] * finv[k - i] % MOD) % MOD)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
# import numpy as np
#N=int(input().strip())
#x=[0]*N
#y=[0]*N
#
#for i in range(N):
#    x[i],y[i]=list(map(int,input().strip().split()))

import sys

def power_l(x,power): # for mod
    if power==0:
        return 1
    elif power<0:
        print('error')
        sys.exit(1)
    res = 1
    sq = x%mod
    while(power>0):
        if power&1 > 0:
            res*=sq
            res=res%mod
        sq = sq**2 %mod
        power = power >> 1
    return res%mod

def inv(x): # x^(-1)=x^(p-2) mod
    ans = power_l(x,mod-2)
    return ans
##########################
mod = 10**9+7

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

if (X+Y)%3 !=0:
    print(0)
    sys.exit()
m = int((2*X-Y)//3)
n = int(X-2*m)

if m<0 or n<0:
    print(0)
    sys.exit()

# compute m+nCm=(m+n)!/(m!n!)
# make factorial
f=[1]
for i in range(m+n-1):
    f.append((f[i]*(i+2))%mod)

denom = (f[m-1]*f[n-1])%mod

ans=(f[m+n-1] * inv(denom)) %mod
print(ans)

Submission status: Wrong Answer

Solution code:
# import numpy as np
#N=int(input().strip())
#x=[0]*N
#y=[0]*N
#
#for i in range(N):
#    x[i],y[i]=list(map(int,input().strip().split()))

import sys

def power_l(x,power): # for mod
    if power==0:
        return 1
    elif power<0:
        print('error')
        sys.exit(1)
    res = 1
    sq = x%mod
    while(power>0):
        if power&1 > 0:
            res*=sq
            res=res%mod
        sq = sq**2 %mod
        power = power >> 1
    return res%mod

def inv(x): # x^(-1)=x^(p-2) mod
    ans = power_l(x,mod-2)
    return ans
##########################
mod = 10**9+7

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

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

if m<0 or n<0:
    print(0)
    sys.exit()

# compute m+nCm=(m+n)!/(m!n!)
# make factorial
f=[1]
for i in range(m+n-1):
    f.append((f[i]*(i+2))%mod)

denom = (f[m-1]*f[n-1])%mod

ans=(f[m+n-1] * inv(denom)) %mod
print(ans)

Submission status: Wrong Answer

Solution code:
# 拡張ユークリッドアルゴリズム
# (d, x, y): d=ax+by を満たすd, x, yを求める
# aとbが互いに素な整数であればgcd(a,b)=d=1, ax=1 (mod b)
# xは法bの元でaの乗法逆元a^-1になる
def exEuclid(a, b):
    if (b==0):
        return (a, 1, 0)
    else:
        (dd, xx, yy) = exEuclid(b, a % b)
        return (dd, yy, xx - (a//b)*yy)

def mycomb(n, k, p):
    k = min(n-k,k)
    fact=1
    finv=1
    for i in range(k):
        fact=fact*(n-i) % p
        finv=finv*i % p
    (d, x, y) = exEuclid(finv, p)
    return fact*x % p

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

if ((x+y)%3 != 0):
    print(0)
    exit()
else:
    n1 = (-x+2*y)//3
    n2 = (2*x -y)//3
    if( (n1<0) or (n2<0) ):
        print(0)
        exit()
    npath = mycomb(n1+n2, n2, 10**9+7)
    print(npath)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/pypy
from math import factorial as f

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

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

j = (X+Y)/3

mod = pow(10,9)+7
#ans = (f(j) / f(X-j) / f(Y-j)) % mod

nu = reduce(lambda x,y: (x*y)%mod, xrange(max(X-j, Y-j)+1, j+1), 1)
denu = reduce(lambda x,y: (x*y)%mod, xrange(1, min(X-j, Y-j)+1), 1)


ans = (nu * pow(denu, mod-2, mod)) % mod

print str(ans)

Submission status: Wrong Answer

Solution code:
#coding: utf-8
import math
import heapq

MOD = 10**9+7

def combination(n, r):
    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


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

if (X+Y)%3!=0:
    print(0)
else:
    a = 2*X-Y
    b = 2*Y-X
    if a<0 or b<0:
        print(0)
    else:
        print(combination(a+b, a))

Submission status: Wrong Answer

Solution code:
#coding: utf-8
import math
import heapq

MOD = 10**9+7

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


def combination(n, m):
    ans = 1

    for i in range(n, n-m, -1):
        ans=(ans*i)%MOD
    for i in range(2,m+1):
        ans=(ans*modinv(i,MOD))%MOD

    return ans


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

if (X+Y)%3!=0:
    print(0)
else:
    a = 2*X-Y
    b = 2*Y-X
    if a<0 or b<0:
        print(0)
    else:
        print(combination(a+b, a))

Submission status: Wrong Answer

Solution code:
import math
def comb1(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

delta = abs(x - y)
asum = x + y
if asum%3 != 0:
    print(0)
else:
    anum = asum//3
    delta2 = (delta+anum)//2
    X,Y = [abs(delta2), abs(anum-delta2) ]
    ans = comb1(X+Y, Y)%(10**9+7)
    print(ans)

Submission status: Wrong Answer

Solution code:
def kaijou(n, r, mo):
    c = 1
    for i in range(r+1, n+1):
        c *= i
        c %= mo
    return c

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def invmod(a, m):
    g, x, y = xgcd(a, m)
    return x % m

def kaijou_inv(ans, n, mo):
    for i in range(1,n+1):
        ans *= invmod(i, mo)
        ans %= mo
    return ans


x, y = map(int, input().split())
mo = 10**9 + 7
if (x+y) % 3 != 0:
    print(0)
else:
    a = (2*x-y) // 3
    b = (2*y-x) // 3
    te = kaijou(a+b, max(a, b), mo)
    tem = kaijou_inv(te, min(a,b), mo)
    print(tem)

Submission status: Wrong Answer

Solution code:
def kaijou(n, r, mo):
    c = 1
    for i in range(r+1, n+1):
        c *= i
        c %= mo
    return c

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def invmod(a, m):
    g, x, y = xgcd(a, m)
    return x % m

def kaijou_inv(ans, n, mo):
    for i in range(1,n+1):
        ans *= invmod(i, mo)
        ans %= mo
    return ans


x, y = map(int, input().split())
mo = 10**9 + 7
if (2*x-y) % 3 !=0 or (2*y-x) % 3 != 0:
    print(0)
else:
    a = (2*x-y) // 3
    b = (2*y-x) // 3
    te = kaijou(a+b, max(a, b), mo)
    tem = kaijou_inv(te, min(a,b), mo)
    print(tem%mo)

Submission status: Wrong Answer

Solution code:
def kaijou(n, r, mo):
    c = 1
    for i in range(r+1, n+1):
        c *= i
        c %= mo
    return c

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def invmod(a, m):
    g, x, y = xgcd(a, m)
    return x % m

def kaijou_inv(ans, n, mo):
    for i in range(1,n+1):
        ans *= invmod(i, mo)
        ans %= mo
    return ans


x, y = map(int, input().split())
mo = 10**9 + 7
if (2*x-y) % 3 !=0 or (2*y-x) % 3 != 0:
    print(0)
else:
    a = (2*x-y) // 3
    b = (2*y-x) // 3
    te = kaijou(a+b, max(a, b), mo)
    tem = kaijou_inv(te, min(a,b), mo)
    print(tem)

Submission status: Wrong Answer

Solution code:
def extgcd(a,b):
    a0,b0=a,b
    x0,y0=1,0
    x1,y1=0,1

    while b0!=0:
        q = a0 // b0
        r = a0 % b0

        a0,b0=b0,r
        x0,x1=x1,x0-q*x1
        y0,y1=y1,y0-q*y1

    return a0,x0,y0

def mo(x,m):
    return (m+x%m)%m

def inv(a,m):
    g,x,y=extgcd(a,m)
    ans=mo(x,m)
    return ans

def combi_mod(n,k,m):
    mi=min(k,n-k)
    invlist = [1]
    for i in range(1, mi + 1):
        temp = inv(i, m)
        invlist.append(temp)
    ans=1

    for i in range(1,mi+1):
        ans=(ans*(n+1-i)*invlist[i])%m
    ans = ans % m
    return ans

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

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

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

ans=combi_mod(a+b,a,mod)
print(ans)

Submission status: Wrong Answer

Solution code:
x,y=map(int, input().split())
xans=x//2
ans,m,k,j=0,1,1,1
for i in range(1,xans+1):
  if y==(xans-i)*2+i:
    m=1
    for l in range(1,i+1):
      m*=l
    k=1
    for l in range(1,xans-i+1):
      k*=l
    j=1
    for l in range(1,xans+1):
      j*=l
  ans+=j/m/k
if y==2*x:
  ans+=1
ans=ans//1
print(int(ans%1000000007))

Submission status: Wrong Answer

Solution code:
x,y=map(int, input().split())
xans=x//2
ans,m,k,j=0,1,1,1
for i in range(1,xans+1):
  if y==(xans-i)*2+i:
    m=1
    for l in range(1,i+1):
      m*=l
    k=1
    for l in range(1,xans-i+1):
      k*=l
    j=1
    for l in range(1,xans+1):
      j*=l
  ans+=j/m/k
if y==2*x:
  ans+=1
ans=ans//1
print(int(ans%1000007))

Submission status: Wrong Answer

Solution code:
x,y=map(int, input().split())
xans=x//2
ans,m,k,j=0,1,1,1
for i in range(xans+1):
  if y==(xans-i)*2+i:
    m=1
    for l in range(1,i+1):
      m*=l
    k=1
    for l in range(1,xans-i+1):
      k*=l
    j=1
    for l in range(1,xans+1):
      j*=l
  ans+=j/m/k
if y==2*x:
  ans+=1
ans=ans//1
print(int(ans%1000000007))

Submission status: Wrong Answer

Solution code:
x,y=3,3
xans=x//2
ans,m,k,j=0,1,1,1
for i in range(xans+1):
  if y==(xans-i)*2+i:
    m=1
    for l in range(1,i+1):
      m*=l
    k=1
    for l in range(1,xans-i+1):
      k*=l
    j=1
    for l in range(1,xans+1):
      j*=l
  ans+=j/m/k
if y==2*x:
  ans+=1
ans=ans//1
print(int(ans%1000007))

Submission status: Wrong Answer

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

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

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


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

if not(-(-x//2) <= y and y <= x*2):
    print(0)
    exit()

flag = True

count = 0
while flag:
    count += 1
    x += 1
    y -= 1

    if y*2 == x: # yCc
        # print(comb(y, count, 10**9+7))
        print(0)
        exit()
    if y*2 < x: # ない
        print(0)
        exit()

Submission status: Wrong Answer

Solution code:
from sys import stdin
import math
import bisect
import heapq
import numpy as np
from math import factorial
mod = 1000000007
x,y = [int(x) for x in stdin.readline().rstrip().split()]

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

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

def combination(n,r,mod=10**9+7):
    r=min(r,n-r)
    up,down=1,1
    for i in range(r):
        up=up*(n-i)%mod
        down=down*(i+1)%mod
    return up*pow(down,mod-2,mod)%mod

print(combination(a+b,a))

Submission status: Wrong Answer

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

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

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


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

if not(-(-x//2) <= y and y <= x*2):
    print(0)
    exit()

flag = True

count = 0
while flag:
    count += 1
    x += 1
    y -= 1

    if y*2 == x: # yC0
        print(comb(y, count, 10**9+7))
        exit()
    if y*2 < x: # ない
        print(0)
        exit()

Submission status: Wrong Answer

Solution code:
X, Y = map(int, input().split(" "))
count = 0
for i in range(X):
    for j in range(Y):
        if i * 1 + j * 2 == X and i * 2 + j * 1 == Y:
            count = count + i + j
print(count)

Submission status: Wrong Answer

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

mod = 10**9+7 #出力の制限
N = 1000000
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

def cinit():
    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 )

X,Y = map(int, input().split())
maxY = X * 2
if (X+Y)%3 == 0 and (maxY - Y)%3==0:
    cinit()
    num2 = abs(maxY - Y)//3
    num1 = X - num2 * 2
    print(cmb(num1+num2,num2,mod))
else:
    print(0)

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 or x <= 0 or y <= 0:
        print(0)
    else:
        t = (x + y) // 3
        for i in range(t + 1):
            xn = i * 2 + (t - i)
            yn = i + (t - i) * 2
            if xn == x and yn == y:
                print(alg_combination_mod(i + t - i, i, mod))
                exit()


if __name__ == '__main__':
    solve()