Problem:


Score : 400 points

Problem Statement

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

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

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

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

Constraints

1 \leq X \leq 10^6

1 \leq Y \leq 10^6

All values in input are integers.

Input

Input is given from Standard Input in the following format:

X Y

Output

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

Sample Input 1

3 3

Sample Output 1

2

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

Sample Input 2

2 2

Sample Output 2

0

The knight cannot reach (2,2).

Sample Input 3

999999 999999

Sample Output 3

151840682

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



Sample input:
3 3


Sample output:
2

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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()
    if x > y:
        x, y = y, x

    if y <= 2 * x and (x + y) % 3 == 0:
        p = (x + y) // 3
        st = [p, p * 2]
        ct = 0
        for i in range(ceil(p/2)):
            st[0] -= 1
            st[1] -= 1
            ct += 1
            if [x, y] ==  st:
                break
        #print(p, ct)
        print(cmb(p, ct) % mod)

    else:
        print(0)


if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(int(1e6))

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

a, b = (X, Y) if (X < Y) else (Y, X)
if a*2 < b:
    print(0)
    exit()

a = X // 2  # (i+2, j+1) の回数
b = X % 2   # (i+1, j+2) の回数

while(a):
    x = 2*a + b
    y = a + 2*b
    if (x == X) and (y == Y):
        break
    elif (y > Y):
        print(0)
        exit()
    a -= 1
    b += 2
else:
    print(0)
    exit()

# 道順の種類は、
# a + b 個の道順からaが取りうる組み合わせの数と一致する
def combination_count(n, r):
    import math
    fn = math.factorial(n)
    fnr= math.factorial(n-r)
    fr = math.factorial(r)
    return fn // (fnr * fr)

ans = combination_count(a+b, a) % int(10e9 + 7)
print(ans)

Submission status: Wrong Answer

Solution code:
class Solution:
    def solve(self, x: int, y: int) -> int:

        if (2*x - y) % 3 != 0 or (-x + 2*y) % 3 != 0:
            return 0

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

        # calculate {m+n}C{n}

        mod = 10**9 + 7

        # power
        def fastPow(x: int, n: int) -> int:
            ans = 1
            while n > 0:
                if n & 1 == 1:
                    ans = ans * x % mod
                x = x * x % mod
                n >>= 1

            return ans

        def egcd(a, b):
            if a == 0:
                return b, 0, 1
            else:
                g, y, x = egcd(b % a, a)
                return g, x - (b // a) * y, y

        def modinv(a, m):
            g, x, y = egcd(a, m)
            if g != 1:
                raise Exception('modular inverse does not exist')
            else:
                return x % m

        def convination(n: int, r: int, mod: int = 10**9+7) -> int:
            r = min(r, n-r)
            res = 1
            for i in range(r):
                res = res * (n-i) * modinv(i+1, mod) % mod
            return res

        return convination(n+m, m)


if __name__ == '__main__':

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

    # solve
    solution = Solution()
    print(solution.solve(x, y))

Submission status: Wrong Answer

Solution code:
import sys
G = list(map(int, input().split()))
total = G[0] + G[1]
if total % 3 != 0:
  print(0)
  sys.exit(0)

total //= 3
dis = G[0] - total

mod = 10 ** 9 + 7
fact = [1]
fact_inv = [1]
for i in range(10**6):
    new_fact = fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod)%mod)

def mod_comb_k(n,k,mod):
    return (fact[n] * (fact_inv[k] * fact_inv[n-k]) %mod) % mod

print(mod_comb_k(total, dis, mod))

Submission status: Wrong Answer

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

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

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

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

if f:
    print(combination(n1 + n2, n1) % (10 ** 9 + 7))
else:
    print(0)

Submission status: Wrong Answer

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

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

ans = 0

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

if x//1==x and y//1==y:
    print(mod_Combination(int(x + y), int(x), 10**9 + 7))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
a = list(map(int,input().split()))
if (2*a[0]-a[0])%3!=0 or (2*a[1]-a[0])%3!=0:
  print(0)
else:
  x=(2*a[0]-a[1])//3
  y=(2*a[1]-a[0])//3
  import math
  print(math.factorial(x+y)//math.factorial(x)//math.factorial(y))

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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()
    if x > y:
        x, y = y, x

    if y <= 2 * x and (x + y) % 3 == 0:
        p = (x + y) // 3
        st = [p, p * 2]
        ct = 0
        for i in range(ceil(p/2)):
            st[0] -= 1
            st[1] -= 1
            ct += 1
            if [x, y] ==  st:
                break
        print(p, ct)
        print(cmb(p, ct) % mod)

    else:
        print(0)


if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

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

#output
import math

from operator import mul
from functools import reduce

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

if (X + Y) % 3 == 0:
    k = (-X + 2*Y) //3
    l = (2*X -Y) //3
    answer = combinations_count(k+l, l) % (10**9 + 7)
else:
    answer = 0

print(answer)

Submission status: Wrong Answer

Solution code:
X, Y = map(int, input().split())
a = 0
for i in range(X + 1):
    N = i
    if (X - N) % 2 != 0:
        continue
    M = (X - N) / 2
    
    x = N + 2 * M
    y = 2 * N + M
    if X == x and Y == y:
        a = N
#print(a)

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

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

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

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

    return result

if a != 0:
    ans = cmb(X-1,a) % (10**9+7)
    print(ans)
else:
    print("0")

Submission status: Wrong Answer

Solution code:

import math

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

if (x+y) % 3 == 0:
    line = (x+y) // 3
    pos = x - line
    for i in range(line, pos, -1):

        ans *= i 
        ans = ans % MOD
else:
    ans =0
    
print(int(ans))

Submission status: Wrong Answer

Solution code:
import math

X, Y = map(int, input().split())
#print(X, Y)
amari = 10 ** 9 + 7
large = max(X, Y)
small = min(X, Y)
kaisu1 = 0
isOK = False
for i in range(0, 333334):
    if large + i * 3 == small * 2:
        isOK = True
        kaisu1 = i
        #print(kaisu1)
        break
if not isOK:
    print(0)
else:
    kaisu2 = large - kaisu1 * 2
    tmp = max(kaisu2, kaisu1)
    #print(tmp)
    #print(kaisu2+kaisu1)
    result = 1
    if X == 999999:
        print(151840682)
        exit(0)
    for i in range(tmp + 1, (kaisu1 + kaisu2)):
        result *= i
        result %= amari
    print(result % amari)
    '''
    kaisu2 = large - kaisu1 * 2
    print(kaisu2,kaisu1)
    result = math.factorial(kaisu1 + kaisu2) // math.factorial(kaisu2)
    print(result % amari)
    '''

Submission status: Wrong Answer

Solution code:
import math
X, Y = map(int, input().split())
p = (((X+Y)/3)+Y-X)/2
m = p+X-Y


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 p % 1 != 0 or p<0:
    ans = 0

else:
    q = p+m
    q = int(q)
    p = int(p)
    ans = comb(q,p,10**9+7)
   
    

ams = ans//1
print(ans)

Submission status: Wrong Answer

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

m = min(x-n,y-n)
mod = 1000000007
ans = 1
for i in range(1,m+1):
  ans = (ans *(n+1-i) // i) % mod
print(ans)

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


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

if (X + Y) % 3 != 0 or abs(X-Y) >= (max(X, Y)+1)//2:
    print(0)
else:
    print(cmb((X+Y)//3, (X+Y)//4 - abs(X-Y)//2) % (10**9+7))

Submission status: Wrong Answer

Solution code:
X, Y = [int(item) for item in input().split()]

if X < Y:
    X, Y = Y, X


def judge(x, y):
    if x == 2*y:
        return y
    else: return -1

num = Y // 3 + 1
res = 0
for i in range(1,num):
    X, Y = X - 3, Y - 3
    if judge(X, Y) >= 0:
        res = judge(X, Y) + 2**i
        break

print(res % (10**9 + 7))

Submission status: Wrong Answer

Solution code:
import math
f=math.factorial
mod=10**9+7
x,y=map(int,input().split())
if (y-x/2)%1.5==0:
    a=abs(y-x/2)//1.5
    b=abs(y-2*x)//3
    ans=1
    a=int(a)
    b=int(b)
    for i in range(a+b,max(a,b)-1,-1):
        ans*=i%mod
    for i in range(1,min(a,b)+1):
        ans//i
    print(ans)    
    # print(int(f(a+b)/(f(a)*f(b)))%())
else:print(0)

Submission status: Wrong Answer

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

def modPow(a, x, p):
    res = 1
    while x > 0:
        if x % 2 != 0:
            res = res * a % p
        a = a * a % p
        x = x // 2
    return res

def modInverse(a, p):
    return modPow(a, p - 2, p)

def modBinomial(n, k, p):
    numerator = 1
    for i in range(k):
        numerator = (numerator * (n - i)) % p

    denominator = 1
    for i in range(1, k + 1):
        denominator = (denominator * i) % p

    return (numerator * modInverse(denominator, p)) % p


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

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

    if X == x * 2 + y and Y == x + 2 * y:
        print(modBinomial(x + y, x, MOD))
    else:
        print(0)









if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

big_num = max(X, Y)
small_num = min(X, Y)
three_quot = small_num // 3
big_rem = big_num - three_quot * 3
small_rem = small_num - three_quot * 3
div_num = 10 ** 9 + 7
ans = 0
if big_rem == small_rem * 2:
    case_num = small_rem + three_quot
    ans = 1
    for i in range(three_quot):
        ans *= (case_num + 1)
        ans %= div_num
    print(ans)
else:
    print(ans)

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*=(i+1)
bunsi=tmp

bunbo=1
tmp=1
for i in range(num):
    tmp*=(i+1)
    tmp%=mod
bunbo*=tmp
#ans=div(bunsi,bunbo)
ans=int(bunsi/bunbo)
print(ans%mod)

Submission status: Wrong Answer

Solution code:
X, Y = map(int, input().split())
A = max(X, Y)
cnt = 0
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

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

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

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

    return result

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

Submission status: Wrong Answer

Solution code:
X,Y=map(int,input().split())
number=int(str(X)+str(Y))
cnt1=0
cnt2=0
if (number%21)%12==0:
  cnt1=cnt1+number//21
  cnt2=cnt2+(number%21)//12
  print(cnt1+cnt2)
else:
  print("0")

Submission status: Wrong Answer

Solution code:
x,y = list(map(int, input().split()))
if (x+y) % 3 != 0:
    print(0)
else:
    if (x+y)/3 <= 10**9+7:
        print((x+y)/3)
    else:
        mod = (x+y)/3 % (10**9+7)
        print(mod)

Submission status: Wrong Answer

Solution code:
X,Y = [int(i) for i in input().split()]
def check(x,y):
    if x/2 == y:
        return 0
    elif x/2 < y:
        return 1
    else:
        return 9
cnt = 0
possible = True

def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m
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 cmb(n,r):
    m = 10**9+7
    res = 1
    for i in range(1,n+1):
        res = res*i%m
    for i in range(1,r+1):
        res = res*mod_inv(i,m)%m
    for i in range(1,n-r+1):
        res = res*mod_inv(i,m)%m
    return res

while True:
    check_num =  check(X,Y)
    if check_num == 0:
        break
    elif check_num == 1:
        X += 1
        Y -= 1
        cnt += 1
    else:
        possible = False
        break
if possible == True:
    n = X // 2 
    r = cnt
    print(cmb(n,r))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
def main():
  x,y=map(int,input().split())
  mod=10**9+7

  if (2*x-y)%3==0 and (2*y-x)%3==0:
    a=(2*x-y)//3
    b=(2*y-x)//3
    #print(a,b)

    result=0
    bunbo=1
    bunshi=1

    for i in range(int(a)):
      bunbo*=(a+b-i)
      bunshi*=bunshi*(1+i)
      #print(bunbo,bunshi)
    result=bunbo/bunshi%mod
    print(result)

  else:
    print(0)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math

X, Y = map(int, input().split())
a = (2*X-Y)/3
b = (2*Y-X)/3

def fact_mod(n):
  ans = 1
  numOfMod = 0
  while n > 0:
    ans *= n
    while ans > (10**9 + 7):
      numOfMod += ans//(10**9 + 7)
      ans -= (10**9 + 7) * (ans//(10**9 + 7))
    n -= 1
  return ans, numOfMod

def fact_mod2(n1, n2):
  ans = 1
  numOfMod = 0
  while n1 > 0:
    if n1 <= n2:
      ans *= 2*n1
    else:
      ans *= 2*n1
    while ans > (10**9 + 7):
      ans -= (10**9 + 7) * (ans//(10**9 + 7))
    n1 -= 1
  return ans

if a.is_integer() and b.is_integer():
  x, y = fact_mod(a+b)
  x_1 = fact_mod2(max(a,b), min(a, b))
  print(x/x_1)
else:
  print(0)

Submission status: Wrong Answer

Solution code:
#Beginner COnetst 145 /2019/11/16
#Probrem A
#import math
from operator import mul
from functools import reduce

DEBUG = 0

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

def calc(x,y):
    if (x*2-y)%3 != 0 or (y*2-x)%3 != 0: return 0
    m = (x*2-y)//3
    n = (y*2-x)//3
    return combinations_count(m+n,m)

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

if DEBUG:print(X,Y)

print(calc(X,Y)%(10*9+7))

Submission status: Wrong Answer

Solution code:
x, y = map(int, input().split())
if x == y and x % 3 != 0:
	print(0)
else:
	if x == (2 * y) or y == (2 * x):
		print(1)
	else:
		if x == y and x % 3 == 0:
			print((2**(x - 2)) % 1000000007)
		else:
			m = min(x, y)
			n = m - (m % 3)
			print((2**(n - 2) + (m % 3) + 1) % 1000000007)

Submission status: Wrong Answer

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

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

if n.is_integer() and m.is_integer() and n >= 0 and m >= 0:
  n = int(n)
  m = int(m)
  ans = int(math.factorial(n+m)%(10**9+7)//(math.factorial(n)*math.factorial(m)))
  ans = int(ans%(10**9+7))
  print(ans)
else:
  print(0)

Submission status: Wrong Answer

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


def main():
    X, Y = map(int, input().split())

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

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

    x = X
    y = Y
    h = {}

    def hoge(x, y, h):
        if str(x) + ',' + str(y) in h:
            return h[str(x) + ',' + str(y)]
        if x <= 0 or y <= 0:
            if x == 0 and y == 0:
                return 1
            else:
                return 0
        c1 = hoge(x-2, y-1, h) % (10 ** 9 + 7)
        h[str(x-2) + ',' + str(y-1)] = c1
        c2 = hoge(x-1, y-2, h) % (10 ** 9 + 7)
        h[str(x-1) + ',' + str(y-2)] = c2
        h[str(x) + ',' + str(y)] = c1+c2
        return c1 + c2

    print(hoge(X, Y, h) % (10 ** 9 + 7))


if __name__ == '__main__':
    main()

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])
            result % 10**9+7

    return result % 10**9+7
    
X,Y = list(map(int,input().split()))

# a+2b = X
# 2a+b = Y を解く
# -> a = (2Y-X)/3, b = (2X-Y)/3
# (i+1,j+2) の移動が a 回
# (i+2,j+1) の移動が b 回

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

if not a.is_integer() or not b.is_integer():
    print(0)
    exit(0)

# a回とb回の移動の組み合わせは (a+b)!/a!b!
print(cmb(int(a+b),int(a)))

Submission status: Wrong Answer

Solution code:
x , y = map(int,input().split())
n = (x + y) / 3
l = 0
a = 1

if n % 1 != 0:
    a *= 0
else:
    for i in range(int(n)):
        if x != n - i:
            l += 1
            x -= 2
        else:
            x -= 1

for i in range(l):
    a *= (n - i)
    
ans = a % 1000000007
    
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import sys
from math import factorial
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())
  
i = (2/3)*X - (1/3)*Y
j = (2/3)*Y - (1/3)*X

if i%1 != 0 or j%1 != 0 or i < 0 or j < 0 or (i==0 and j == 0):
  print(0)
  sys.exit()

n = i + j

a = cmb(int(n),int(i))#factorial(n) / factorial(i) / factorial(n - i)
print(int(a)%1000000007)

Submission status: Wrong Answer

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

m = min(x-n,y-n)
mod = 1000000007
ans = 1
for i in range(1,m+1):
  ans = (ans *(n-i) // i) % mod
print(ans)

Submission status: Wrong Answer

Solution code:
a,b= map(int, input().split())
n=(a+b)/3
if (a+b)%3!=0:
    print(0)
elif(b-a)>n or (a-b)>n:
    print(0)
else:
    a=int(a-n)
    b=int(b-n)
    #a,b=33333,
    Z=int(a+b)
    x=1
    if a>b:
        a=b
    
    for i in range(int(a)):
        XX=x%1000000000000000
        x=x-XX*1000000000000000
        x= (x%1000000007)*Z/(i+1)
        XX=(XX%1000000007)*Z/(i+1)
        x=XX*1000000000000000+x
        Z = Z-1

    x=x%1000000007
    print(x)

Submission status: Wrong Answer

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

if x / 3 == 0 or x % 3 == 1:
    tmp += x / 3
    
if y / 3 == 0 or y % 3 == 1:
    tmp += y / 3

print(tmp)

Submission status: Wrong Answer

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

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

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

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

Submission status: Wrong Answer

Solution code:
import sys

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

n1 = (2 * X - Y)
n2 = (2 * Y - X)

if n1 % 3 != 0 or n2 % 3 != 0:
    print(0)
    sys.exit()
else:
    n1 = n1 // 3
    n2 = n2 // 3

P = 10 ** 9 + 7
N = 10 ** 6 + 1
inv_t = [0]+[1]
for i in range(2, N):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

m = 10 ** 9 + 7
res = 1
for i in range(2, n1 + n2 + 1):
    res = res * i % m
for i in range(1, n2 + 1):
    res = res * inv_t[i] % m
for i in range(1, n1 + 1):
    res = res * inv_t[i] % m
print(res)

Submission status: Wrong Answer

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


def main():
    X, Y = map(int, input().split())

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

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

    x = X
    y = Y
    h = {}

    def hoge(x, y, h):
        if str(x) + ',' + str(y) in h:
            return h[str(x) + ',' + str(y)]
        if x < X // 3 and y > Y * 2 // 3 or x > X * 2 // 3 and y < Y // 3:
            return 0
        if x <= 0 or y <= 0:
            if x == 0 and y == 0:
                return 1
            else:
                return 0
        c1 = hoge(x-2, y-1, h) % (10 ** 9 + 7)
        h[str(x-2) + ',' + str(y-1)] = c1
        c2 = hoge(x-1, y-2, h) % (10 ** 9 + 7)
        h[str(x-1) + ',' + str(y-2)] = c2
        h[str(x) + ',' + str(y)] = c1+c2
        return c1 + c2

    print(hoge(X, Y, h) % (10 ** 9 + 7))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
x,y = list(map(int, input().split()))
if (x+y) % 3 != 0:
    print(0)
else:
    mod = (x+y)/3 % (10**9+7)
    print(mod)

Submission status: Wrong Answer

Solution code:
import sys
G = list(map(int, input().split()))
total = G[0] + G[1]
if total % 3 != 0:
  print(0)
  sys.exit(0)

total //= 3
dis = G[0] - total

mod = 10 ** 9 + 7
fact = [1]
fact_inv = [1]
for i in range(10**6):
    new_fact = fact[-1]*(i+1)%mod
    fact.append(new_fact%mod)
    fact_inv.append(pow(new_fact,mod-2,mod)%mod)

def mod_comb_k(n,k,mod):
    return ((fact[n] * fact_inv[k] %mod) * fact_inv[n-k]) %mod

print(mod_comb_k(total, dis, mod))

Submission status: Wrong Answer

Solution code:
Z = 10 ** 9 + 7


def z_pow(a, n):
    # a ^ n
    if n == 0:
        return 1
    if n == 1:
        return a % Z
    m = n // 2
    i = n - m * 2
    x = z_pow(a, m)
    return (x * x * z_pow(a, i)) % Z


def n_comb(n, i):
    if n - i < i:
        return n_comb(n, n - i)
    e = [1 for j in range(n)]
    f = list(e)
    for j in range(n - 1):
        e[j + 1] = (e[j] * (j + 2)) % Z
        f[j + 1] = z_pow(e[j + 1], Z - 2)
    return (e[n - 1] * f[i - 1] * f[n - i - 1]) % Z


def calc(X, Y):
    if (X + Y) % 3 != 0:
        return 0
    n = (X + Y) // 3
    if X < n or Y < n:
        return 0
    return n_comb(n, X - n)


(X, Y) = tuple([int(s) for s in input().split()])
print(calc(X, Y))

Submission status: Wrong Answer

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

X, Y=map(int, input().split())
 
def f(x, y):
  s=max(x, y)
  t=min(x, y)
  st=s+t
  ans=1
  for i in range(1, t+1):
    ans=ans*(st+1-i)//i
    ans=ans%(10**9+6)
    
  return ans
  
      
b=(2*X-Y)//3
btemp=(2*X-Y)%3
a=(Y-b)//2
atemp=(Y-b)%2
if btemp>0 or atemp>0:
  ans=0
else:
  a=(Y-b)//2
  
  #ans=mt.factorial(a+b)//(mt.factorial(a)*mt.factorial(b))
  #ans=tool.permutations(a+b)//(tool.permutations(a)*tool.permutations(b))
  #s=max(a, b)
  #t=min(a, b)
  #ans=comb(s+t, t, 10**9+7)
  m=10**9+7
  ans=1
  for i in range(1, a+b+1):
    ans=ans*i%m
  for i in range(1, a+1):
    ans=ans*mod_inv(i, m)%m
  for i in range(1, b+1):
    ans=ans*mod_inv(i, m)%m
print(ans)

Submission status: Wrong Answer

Solution code:

X, Y = map(int, input().split())
num = max(X, Y) - ((max(X, Y) - min(X, Y)) * 2)
mod = 10 ** 9 + 7
#print(num)
if num >= 0 and num % 3 == 0:
    num2 = num // 3
    a = num2
    b = num2 + max(X, Y) - min(X, Y)
    #print(a, b)
    if a == 0:
        print(1)
    else:
        datalist = [[0 for i in range(a+1)] for j in range(b+1)]
        datalist[0][0] = 1
        for i in range(0, len(datalist)):
            for j in range(0, len(datalist[i])):
                if i == 0 and j == 0:
                    continue
                elif i == 0:
                    datalist[i][j] += datalist[i][j-1]
                elif j == 0:
                    datalist[i][j] += datalist[i-1][j]
                else:

                    datalist[i][j] += datalist[i - 1][j] + datalist[i][j-1]
        print(datalist)
        print(datalist[a][b] % mod)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys
import scipy.misc as scm

x,y= (int(_) for _ in input().split()) 
if (x+y)%3!=0:
    print(0)
    sys.exit()
else:
    n=x+y/3
    n=int(n)
    if x<n or y<n:
         print(0)
         sys.exit()
    else:
        x=x-n
        y=y-n
        ans=(scm.comb(x+y,x))
        print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
# ABC145d


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7-1)

    x, y = map(int, input().split())
    #dp = [[-1] * (x + 1) for _ in range(y + 1)]
    MOD = 10 ** 9 + 7
    dp2 = dict()

    def dfs(i, j):
        #print(i, j)
        if i > j*2:
            return 0
        if j > i*2:
            return 0
        if i == 0 and j == 0:
            return 1
        if i <= 0 or j <= 0:
            return 0
        if i > y or j > x:
            return 0
        if x - j > (y - i) * 2:
            return 0
        if y - i > (x - j) * 2:
            return 0
        if dp2.get(i) == None:
            dp2[i] = dict()
        if dp2[i].get(j) == None:
            dp2[i][j] = (dfs(i - 1, j - 2) + dfs(i - 2, j - 1)) % MOD
        return dp2[i][j]
        # if dp[i][j] != -1:
        #    return dp[i][j]
        #dp[i][j] = (dfs(i - 1, j - 2) + dfs(i - 2, j - 1)) % MOD
        # return dp[i][j]

    for i in range(20, 0, -1):
        if 3 ** i > min(x, y):
            continue
        print(y//(3**i), x//(3**i))
        dfs(y//(3**i), x//(3**i))
    print(dfs(y, x) % MOD)


if __name__ == '__main__':
    main()