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: Time Limit Exceeded

Solution code:

def framod(n,mod,a=1):
    for i in range(1,n+1):
        a *= i % mod
    return a
def power(n,r,mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n, 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



def main(X,Y,mod):
    if (X+Y)%3 != 0:
        print(0)
    else:
        #n枚とm枚
        n = int((2*X-Y)/3)
        m = int((2*Y-X)/3)

        if n < 0 or m < 0:
            print(0)
        elif n == 0 or m == 0:
            print(1)
        elif n >= m:
             #n+mCmを計算
             print(comb(n+m,m,mod))
        else:
            #n+mCnを計算
            print(comb(n+m,n,mod))


X,Y  = map(int,input().split())
mod = 10**6 + 7
main(X,Y,mod)

Submission status: Time Limit Exceeded

Solution code:
import scipy
from scipy.misc import comb

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

if ((x+y)%3 != 0) or ((2*x-y)%3 != 0):
  print("0")
  exit()
  
m = (2*x-y)//3
n = x-2*m

if n < 0:
  print("0")
  exit()

print(scipy.misc.comb(m+n, n, exact=True)%(10**9+7) )

Submission status: Time Limit Exceeded

Solution code:
import math

def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  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):
  """a^b mod 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:
    ans = 0
else:

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

    

    ans = comb(a+b, b, 1000000007)

    # answer = (a+b)! / a!b! mod 10^9+7

    
print(ans)

# 999999 999999

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
x,y = map(int,input().split())

goal = [x,y]
now = [0,0]
queue = deque([now])
cnt = 0

while queue:
	a,b = queue.popleft()
	if [a,b]==goal:
		cnt += 1
		continue
	for j,k in ([1,2],[2,1]):
		if a+j > x or b+k > y:
			continue
		queue.append([a+j,b+k])

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

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb

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

def A(i, j):
    if 0.5*i <= j and j <= 2*i and (i+j)%3==0:
        n, m = (2*j-i)//3, (2*i-j)//3
        return comb(n+m,m, exact=True)%((10**9)+7)
    else:
        return 0

print(A(x, y))

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

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

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

def A(i, j):
    if 0.5*i <= j and j <= 2*i and (i+j)%3==0:
        n, m = (2*j-i)//3, (2*i-j)//3
        return combinations_count(n+m,m)%((10**9)+7)
    else:
        return 0

print(A(x, y))

Submission status: Time Limit Exceeded

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

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def A(i, j):
    if 0.5*i <= j and j <= 2*i and (i+j)%3==0:
        n, m = (2*j-i)//3, (2*i-j)//3
        return combinations_count(n+m,m)%((10**9)+7)
    else:
        return 0

print(A(x, y))

Submission status: Time Limit Exceeded

Solution code:
import math
MOD = 10**9+7
x, y = map(int, input().split())
if (x+y)%3 != 0 or 3*x < x+y or 3*y < x+y:
    print(0)
    exit()
n = (x+y)//3
x -= n
y -= n
c = math.factorial(n) // math.factorial(x) // math.factorial(y)
print(c%MOD)

Submission status: Time Limit Exceeded

Solution code:
def main(X,Y):
    if (X+Y)%3 != 0:
        print(0)
    else:
        n = (2*X-Y)/3
        m = (2*Y-X)/3
        if n < 0 or m < 0:
            print(0)
        elif n == 0 or m == 0:
            print(1)
        else:
            top = 1
            bot = 1
            n = int(n)
            m = int(m)
            for i in range(n):
                top *= (n + m) - i
                bot *= n - i
            w = (10**9)+7
            result = (top/bot) % w
            result = int(result)
            print(result)

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

Submission status: Time Limit Exceeded

Solution code:
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 n < 0 or m < 0:
        print(0)
    elif n == 0 or m == 0:
        print(1)
    else:
        top = 1
        bot = 1
        n = int(n)
        m = int(m)
        for i in range(n):
            top *= (n + m) - i
            bot *= n - i

        result = (top/bot) % ((10**9)+7)
        result = int(result)
        print(result)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial


dest = list(map(int, input().split()))

p = (2, 1)
q = (1, 2)
num_p = 0
num_q = 0

while dest[0] and dest[1]:
    if dest[0] >= dest[1]:
        dest[0] -= p[0]
        dest[1] -= p[1]
        num_p += 1
    else:
        dest[0] -= q[0]
        dest[1] -= q[1]
        num_q += 1

if dest == [0, 0]:
    print((factorial(num_p + num_q) // factorial(num_q) // factorial(num_p)) % (10**9 + 7))
else:
    print(0)

Submission status: Time Limit Exceeded

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

mod=10**9+7
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 (X+Y)%3 != 0:
      print(0)
      exit()
 
n,x,y=0,X,Y
while x != y*2:
      x-=1
      y-=2
      n+=1

m=((X+Y)//3)-n

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

ans = nCr(n+m,n,mod)
print(ans)

Submission status: Time Limit Exceeded

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

#nCr and Mod
def nCr(n, r, mod=10**9+7):
    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
mod = 10 ** 9 + 7

if (X+Y)%3 != 0:
      print(0)
      exit()
 
n,x,y=0,X,Y
while x != y*2:
      x-=1
      y-=2
      n+=1
m=((X+Y)//3)-n

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

ans = nCr(n+m,n,mod)
print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

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

    result=0.0
    bunbo=1
    bunshiA=set([])

    for i in range(min(a,b)):
      bunbo=bunbo*(a+b-i)
      temp=min(a,b)-i
      bunshiA.add(temp)
      for item in list(bunshiA):
        if bunbo%item==0:
          bunbo=bunbo//item
          bunshiA.discard(item)

    bunshi=1
    for item in bunshiA:
      bunshi=bunshi*item
      
    result=bunbo//bunshi%mod
    print(int(result))

  else:
    print(0)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce
x, y = map(int, input().split())
ans = 0
xtwo = 0
ytwo = 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
if x < y:
    x, y = y, x
if x % 2 == 0:
    dy = y - x // 2
    if dy >= 0 and dy % 3 == 0:
        xtwo = x // 2 - dy // 3
        ytwo = 2 * dy // 3
        ans = combinations_count(xtwo + ytwo, ytwo)
    else:
        ans = 0
else:
    dy = y - (x - 1) // 2
    if dy >= 0 and dy % 3 == 2:
        xtwo = (x - 1) // 2 - (dy - 2) // 3
        ytwo = 2 * (dy + 1) // 3 - 1
        ans = combinations_count(xtwo + ytwo, ytwo)
    else:
        ans == 0

ans %= 10 ** 9 + 7

print(ans)

Submission status: Time Limit Exceeded

Solution code:
p=int(1e9+7)
def qp(x,y):
  re=1
  while y:
    if y&1: re*=x;re%=p
    x*=x;x%=p
    y>>=1
  return re
fac=[1]
for i in range(1,int(1e6+10)):
  fac.append(fac[-1]*i%p)
inv=[1]
for i in range(1,int(1e6+10)):
  inv.append(inv[-1]*qp(i,p-2)%p)
def C(x,y):
  return fac[y]*inv[x]%p*inv[y-x]%p
X,Y=map(int,input().split())
if (2*X-Y)%3!=0:
  print(0)
  exit(0)
b=(2*X-Y)//3
a=X-2*b
if a<0 or b<0:
  print(0)
  exit(0)
print(C(a,a+b))

Submission status: Time Limit Exceeded

Solution code:
import math
M = 10**9+7
X,Y = map(int,input().split())
if (X+Y)/3 != (X+Y)//3:
    print(0)
    exit()
n = (X+Y)//3
r = Y-n
if r<0 or r>n:
    print(0)
    exit()
#互いに素な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

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
print(res)

Submission status: Time Limit Exceeded

Solution code:
import math
#ABC共通 
abc = input()
abc_list = abc.split(' ')
 
#問題用変数
abc_intlist = []
 
#inputを整数化
for c1 in abc_list:
  abc_intlist.append(int(c1))
 
#以下処理
tesuu = (abc_intlist[0]+abc_intlist[1])//3
diff = max(abc_intlist)-min(abc_intlist)
k = (tesuu-diff)/2
 
if (tesuu-diff)%2==1:
  print(0)
elif k<0:
  print(0)
elif (abc_intlist[0]+abc_intlist[1])%3 != 0:
    print(0)
else:
    maa = int(max([tesuu-k,k]))
    mk = int(tesuu - maa)
    calc=1
    for c1 in range(mk):
        calc = calc*(tesuu-c1)
    #calc = int(calc)
    print((calc//math.factorial(mk))%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial
from fractions import Fraction
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
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()))
MOD = 10**9 + 7

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
   
x, y = MAP()
tx = 2*x-y
ty = 2*y-x
if tx < 0 or ty < 0 or tx%3 != 0 or ty%3 != 0:
    print(0)
else:
    X = tx//3
    Y = ty//3
    print(combinations_count(X+Y, X)%MOD)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import math

MOD = 10**9+7  # type: int

def combi_count(n, r):
    return math.factorial(int(n)) // (math.factorial(int(r)) * math.factorial(int(n - r)))

def solve(X: int, Y: int):
    a = (2*Y - X)/3
    b = (2*X - Y)/3
    if ((2*Y - X)%3 != 0) and ((2*X - Y)%3 != 0):
        ans = 0
    else:
        if (a<0) or (b<0):
            ans = 0
        else:
            ans = combi_count(a+b, min(a, b))
    print(int(ans%MOD))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(X, Y)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

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

    result=0.0
    bunbo=1
    bunshi=1

    for i in range(min(a,b)):
      bunbo=bunbo*(a+b-i)
      temp=1+i
      
      if bunbo%temp==0:
        bunbo=bunbo//temp
      else:
        bunshi=bunshi*(1+i)
      while bunbo%2==0 and bunshi%2==0:
        bunbo=bunbo//2
        bunshi=bunshi//2
      while bunbo%3==0 and bunshi%3==0:
        bunbo=bunbo//3
        bunshi=bunshi//3
      while bunbo%5==0 and bunshi%5==0:
        bunbo=bunbo//5
        bunshi=bunshi//5
      while bunbo%7==0 and bunshi%7==0:
        bunbo=bunbo//7
        bunshi=bunshi//7
      while bunbo%11==0 and bunshi%11==0:
        bunbo=bunbo//11
        bunshi=bunshi//11
      while bunbo%13==0 and bunshi%13==0:
        bunbo=bunbo//13
        bunshi=bunshi//13
      while bunbo%17==0 and bunshi%17==0:
        bunbo=bunbo//17
        bunshi=bunshi//17
      #print(bunbo,bunshi)
      
    result=bunbo//bunshi%mod
    print(int(result))

  else:
    print(0)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

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

    result=0.0
    bunbo=1
    bunshi=1

    for i in range(min(a,b)):
      bunbo=bunbo*(a+b-i)
      temp=1+i
      
      if bunbo%temp==0:
        bunbo=bunbo//temp
      else:
        bunshi=bunshi*(1+i)
      while bunbo%2==0 and bunshi%2==0:
        bunbo=bunbo//2
        bunshi=bunshi//2
      while bunbo%3==0 and bunshi%3==0:
        bunbo=bunbo//3
        bunshi=bunshi//3
      while bunbo%5==0 and bunshi%5==0:
        bunbo=bunbo//5
        bunshi=bunshi//5
      #print(bunbo,bunshi)
      f=fractions.gcd(bunbo,bunshi)
      bunbo=bunbo//f
      bunshi=bunshi//f
      
    result=bunbo//bunshi%mod
    print(int(result))

  else:
    print(0)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
x,y=map(int,input().split())
if (x+y)%3!=0:
  print(0)
  sys.exit()
n=(x+y)//3
fac=[1 for i in range(n+1)]#fac[i]=i!. fac[0]=1
for i in range(1,n+1):
  fac[i]=fac[i-1]*i

print(fac[n]//fac[x-n]//fac[y-n])

Submission status: Time Limit Exceeded

Solution code:
# n ^ m (繰り返し二乗法) (mod p)
def power_mod(n, m, p):
    if m == 0:
        return 1
    if m % 2 == 0:
        d = power_mod(n, m // 2, p)
        return (d * d) % p
    else:
        return (n * power_mod(n, m - 1, p)) % p


# a ^ (p-2) ≡ a^(-1) (mod p)
def gyakugenn(a, p):
    return power_mod(a, p - 2, p)


# nCk (mod p)
# n!/(n-k)!k!
def mod_comb(n, k, p):
    rep = 1
    for i in range(1, n + 1):
        rep = rep * i % p
    for i in range(1, k + 1):
        rep = rep * gyakugenn(i, p) % p
    for i in range(1, n - k + 1):
        rep = rep * gyakugenn(i, p) % p
    return rep


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

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

if x < 0 or y < 0:
    print(0)
    exit()

if x < y:
    x, y = y, x

p = 10 ** 9 + 7
print(mod_comb(x + y, y, p))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  q = min(k, n-k)
  a=factorial(n) %p
  b=factorial(q) %p
  c=factorial(n-q) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod 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  = list(map(int, input().split()))
n = int((2*Y-X)/3)
m = int((2*X-Y)/3)
#if (X+Y)%3==0 and n>0 and m>0:
if (2*X-Y)%3==0 and (2*Y-X)%3==0 and (2*X-Y)>=0 and (2*Y-X)>=0 :
    print(comb(n+m, m, 10**9+7))
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import math
MOD = 10**9 + 7 #　素数
x, y = map(int, input().split())

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

if x == 0 or y == 0:
    print(0)
    exit()

X = max(x,y)
Y = min(x,y)

all_move = (X+Y)//3
diff = (X-Y)
Y_move = (all_move - diff)//2

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 inv_mod(a,mod):
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod

def cmb_mod_p(n, r, mod): # nCr mod p
    if n<0 or r<0 or n<r:
        return 0

    res = 1
    for i in range(1,n+1):
        res = res*i%mod
    for i in range(1,r+1):
        res = res*inv_mod(i,mod)%mod
    for i in range(1,n-r+1):
        res = res*inv_mod(i,mod)%mod

    return res

print(cmb_mod_p(all_move, Y_move,MOD))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  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):
  """a^b mod 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  = list(map(int, input().split()))
n = int((2*Y-X)/3)
m = int((2*X-Y)/3)
#if (X+Y)%3==0 and n>0 and m>0:
if (2*X-Y)%3==0 and (2*Y-X)%3==0 and (2*X-Y)>=0 and (2*Y-X)>=0 :
    print(comb(n+m, m, 10**9+7))
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import operator as op
from functools import reduce

m = 10**9 + 7

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

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

if max(x,y) > 2 *min(x,y):
    print(0)
elif (x+y) % 3 == 0:
    k = (x+y)//3
    n = (2*x-y)//3
    print(int(ncr(k,n)) % m)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import math
m = 10**9 + 7
def nCr(n,r):
    f = math.factorial
    return f(n) // f(r) // f(n-r)

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

if max(x,y) > 2 *min(x,y):
    print(0)
elif (x+y) % 3 == 0:
    k = (x+y)//3
    n = (2*x-y)//3
    print(nCr(k,n) % m)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
def fact(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact
def combinations_count(n, r):
    return fact(n) // (fact(n - r) * fact(r))

ab = input().split()
a, b = int(ab[0]), int(ab[1])
sum=a+b
if sum % 3==0:
	n=int(sum/3)
	m=b-n
	print(int(combinations_count(n, m))%(10**9+7))
else:
	print("0")

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from itertools import combinations

INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())

sys.setrecursionlimit(10**9)
mod = 10**9 + 7


def main():
    X, Y = MAP()
    if (X + Y) % 3 != 0:
        print(0)
        sys.exit()

    s = (2*X - Y)/3
    t = (2*Y - X)/3
    if s != int(s) or t != int(t) or s < 0 or t < 0:
        print(0)
        sys.exit()

    s = int(s)
    t = int(t)
    print(len(list(combinations(range(s+t), s))))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from operator import mul
from functools import reduce
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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**9
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 )

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=int(cmb(x+y, x,mod))
        print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from operator import mul
from functools import reduce
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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= (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
        xy=[x,y]
        ans=int(cmb(x+y, x))
        print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
# 2019-11-16 21:01:15(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
from scipy.misc import comb # float
# import numpy as np 


mod = 10 ** 9 + 7

def main():
    x, y = [int(x) for x in sys.stdin.readline().split()]
    # n(+1, +2), m(+2, +1)
    n, m = (2 * y - x) / 3, (2 * x - y) / 3

    if n != abs(int(n)) or m != abs(int(m)):
        print(0)
        sys.exit()
    else:
        n, m = int(n), int(m)
        ans = comb(n+m, n, exact=True) % mod
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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
        xy=[x,y]
        ans=int(combinations_count(x+y, min(xy)))
        print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
def mp(a,n,mod):
    if n==1:
        return a%mod
    aq=(mp(a,n//2,mod))**2
    ar=a**(n%2)
    return (((aq)%mod)*ar)%mod


def s_comb(n,k):
    s=1
    r=min(k,n-k)
    p=10**9+7
    for c in range(r):
        s=(s*(n-c)*mp(c+1,p-2,p))%p
    return s

x,y=map(int,input().split())
if (x+y)%3!=0 or 2*y<x or 2*x<y:
    print(0)
else:
    r=int(min(2*y-x,2*x-y)/3)
    print(s_comb(int((x+y)/3),r))

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7

a = (2 * Y - X) / 3
b = (2 * X - Y) / 3
if a < 0 or b < 0 or (X + Y) % 3 != 0:
    print(0)
    sys.exit()

a = int(a)
b = int(b)
N = a + b
f = [1]
invf = [1]
for i in range(1,a+b+1):
    f.append((f[-1] * i) % mod)
    invf.append(pow(f[i], mod-2, mod))
ans = f[a+b] * (invf[a] * invf[b] % mod) % mod
print(ans)

Submission status: Time Limit Exceeded

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:
  print(0)
else:
  a=int((2*x-y)/3)
  b=int((2*y-x)/3)
  if a>=0 and b>=0:
    print(cmb(a+b,b)%(10**9+7))
  else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
X ,Y = map(int, input().split())
n = 2 * Y - X
m = 2 * X - Y
r = 1
if n % 3 != 0:
    r = 0
elif m % 3 != 0:
    r = 0
elif m < 0:
    r = 0
elif n < 0:
    r = 0
else:
    nn = min(n,m) // 3
    mm = max(n,m) // 3
    for i in range(nn):
        r = r * (mm + i + 1) // (i+1)
print(r % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def factorial(x):
  a = 1
  for i in range(1, x+1):
    a *= i
  return a           #階乗の計算
mod = 10**7 + 9
X, Y = map(int, input().split())
if (2*X - Y)%3 == 0 and (2*Y - X)%3 == 0:
  a = factorial((2*X-Y)//3)
  b = factorial((2*Y-X)//3)
  c = factorial((2*X-Y)//3 + (2*Y-X)//3)
  print((c//(a*b))%mod)
else:
  print(0)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
X, Y = map(int,input().split())
if (X+Y)%3!=0:
    print(0)
else:
    itr=(X+Y)//3
    x_mx=itr*2
    if itr<=X and X<=x_mx and itr<=Y and Y<=x_mx and X+Y==itr+x_mx:
        c=X-itr
        n=factorial(itr)
        r=factorial(c)
        n_r=factorial(itr-c)
        f=(n//(r*n_r))%(10**9+7)
        print(f)
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
[x,y]=list(map(int,input().split()))
if ((x%3)+(y%3))%3!=0:
	print(0)
else:
	dansu=int((x+y)/3)
	r=y-dansu
	if r>dansu-r:
		r=dansu-r
	mod=1000000007
	d=1
	rr=1
	nr=1
	for i in range(1,dansu+1):
		d=d*(i%mod)
	for i in range(1,r+1):
		rr=rr*(i%mod)
	for i in range(1,dansu-r+1):
		nr=nr*(i%mod)
	rr2=rr*rr
	nr2=nr*nr
	rrinv=1
	nrinv=1
	modd=mod
	mod2=[]
	while modd>0:
		mod2.append(modd%2)
		modd=modd//2
	for i in range(len(mod2)-1):
		if mod2[i]==1:
			rrinv=rrinv*(rr2**(len(mod2)-i-1))
			nrinv=nrinv*(nr2**(len(mod2)-i-1))
	rrinv*=rr
	nrinv*=nr
	kotae=int((d%mod)*(rrinv%mod)*(nrinv%mod))
	kotae=int(kotae%(10**9+7))
	
	print(kotae)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from math import factorial

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

for i in range(0,x//2+1):
    if 2*x-3*i == y:
        cnt += factorial(x-i)//(factorial(x-2*i)*factorial(i))
        break

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from math import factorial

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

for i in range(0,x//2+1):
    if (x-2*i)*2+i == y:
        cnt += factorial(x-i)//(factorial(x-2*i)*factorial(i))

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

Submission status: Time Limit Exceeded

Solution code:
[x,y]=list(map(int,input().split()))
if ((x%3)+(y%3))%3!=0:
	print(0)
else:
	dansu=int((x+y)/3)
	r=y-dansu
	if r>dansu-r:
		r=dansu-r
	mod=1000000007
	d=1
	rr=1
	nr=1
	for i in range(1,dansu+1):
		d=d*i
	for i in range(1,r+1):
		rr=rr*i
	for i in range(1,dansu-r+1):
		nr=nr*i
	
	kotae=int((d%mod)*pow(rr,mod-2,mod)*pow(nr,mod-2,mod))
	kotae=int(kotae%(10**9+7))
	
	print(kotae)

Submission status: Time Limit Exceeded

Solution code:
[x,y]=list(map(int,input().split()))
if ((x%3)+(y%3))%3!=0:
	print(0)
else:
	dansu=int((x+y)/3)
	r=y-dansu
	if r>dansu-r:
		r=dansu-r
	mod=1000000007
	d=1
	rr=1
	nr=1
	for i in range(1,dansu+1):
		d=d*(i%mod)
	for i in range(1,r+1):
		rr=rr*(i%mod)
	for i in range(1,dansu-r+1):
		nr=nr*(i%mod)
	
	kotae=int((d%mod)*pow(rr,mod-2,mod)*pow(nr,mod-2,mod))
	kotae=int(kotae%(10**9+7))
	
	print(kotae)

Submission status: Time Limit Exceeded

Solution code:
[x,y]=list(map(int,input().split()))
if ((x%3)+(y%3))%3!=0:
	print(0)
else:
	dansu=int((x+y)/3)
	r=y-dansu
	mod=1000000007
	d=1
	rr=1
	nr=1
	for i in range(1,dansu+1):
		d=d*(i%mod)
	for i in range(1,r+1):
		rr=rr*(i%mod)
	for i in range(1,dansu-r+1):
		nr=nr*(i%mod)
	
	kotae=int((d%mod)*pow(rr,mod-2,mod)*pow(nr,mod-2,mod))
	kotae=int(kotae%(10**9+7))
	
	print(kotae)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

#互いに素な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

X, Y = map(int, input().split())
if (X + Y) % 3 != 0:
    print(0)
    exit()
time = (X+Y) // 3
diff = X - Y
if abs(diff) > time:
    print(0)
    exit()
x_time = (time+diff) // 2
res = 1
for i in range(1,time+1):
    res = res*i%MOD
for i in range(1,x_time+1):
    res = res*mod_inv(i,MOD)%MOD
for i in range(1,time-x_time+1):
    res = res*mod_inv(i, MOD)%MOD
print(res)
#print(mod_combination(time, x_time, MOD))

Submission status: Time Limit Exceeded

Solution code:
import math
tmp = input().split()
X = int(tmp[0])
Y = int(tmp[1])

mod = 10 ** 9 + 7

if (X + Y) % 3 != 0:
    print(0)
else:
    n = (2 * Y - X) / 3
    m = Y - 2 * n
    if n < 0 or m < 0:
        print(0)
        exit()
    n %= mod
    m %= mod
    total=1
    for i in range(int(n + m), int(n), -1):
        total *= i

    m = math.factorial(m)

    total //= m
    print(total%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
tmp = input().split()
X = int(tmp[0])
Y = int(tmp[1])

mod = 10 ** 9 + 7

if (X + Y) % 3 != 0:
    print(0)
else:
    n = (2 * Y - X) / 3
    m = Y - 2 * n
    if n < 0 or m < 0:
        print(0)
        exit()
    n %= mod
    m %= mod
    total = math.factorial(n+m)
    n = math.factorial(n)
    m = math.factorial(m)

    total //= n*m
    print(total%mod)

Submission status: Time Limit Exceeded

Solution code:
[x,y]=list(map(int,input().split()))
if ((x%3)+(y%3))%3!=0:
	print(0)
else:
	dansu=int((x+y)/3)
	r=y-dansu
	mod=1000000007
	d=1
	rr=1
	nr=1
	for i in range(1,dansu+1):
		d=d*(i%mod)
	for i in range(1,r+1):
		rr=rr*(i%mod)
	for i in range(1,dansu-r+1):
		nr=nr*(i%mod)
	
	kotae=int((d%mod)*((rr**(mod-2))%mod)*((nr**(mod-2))%mod))
	kotae=int(kotae%(10**9+7))
	
	print(kotae)

Submission status: Time Limit Exceeded

Solution code:
[x,y]=list(map(int,input().split()))
if ((x%3)+(y%3))%3!=0:
	print(0)
else:
	dansu=int((x+y)/3)
	r=y-dansu
	mod=1000000007
	d=1
	rr=1
	nr=1
	for i in range(1,dansu+1):
		d=d*(i%mod)
	for i in range(1,r+1):
		rr=rr*(i%mod)
	for i in range(1,dansu-r+1):
		nr=nr*(i%mod)
	
	kotae=int(d*(rr**(mod-2))*(nr**(mod-2)))
	kotae=int(kotae%(10**9+7))
	
	print(kotae)

Submission status: Time Limit Exceeded

Solution code:
import math
tmp = input().split()
X = int(tmp[0])
Y = int(tmp[1])

mod = 10 ** 9 + 7

if (X + Y) % 3 != 0:
    print(0)
else:
    n = (2 * Y - X) / 3
    m = Y - 2 * n
    if n < 0 or m < 0:
        print(0)
        exit()
    total = math.factorial(n + m)
    n = math.factorial(n)
    m = math.factorial(m)
    total //= n * m
    # total //= m
    # print(total)
    # print(nm)
    # tmp = total/nm
    print(total%mod)