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:
import math
X,Y = map(int,input().split())
def comb(n,k,p):
    if n<0 or k<0 or n<k: return 0
    if n==0 or k==0: return 1
    a=math.factorial(n) %p
    b=math.factorial(k) %p
    c=math.factorial(n-k) %p
    return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
    if b==0: return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p
if (X+Y)%3 != 0:
    print(0)
else:
    n = int((2*Y-X)/3)
    m = int((2*X-Y)/3)
    nm = n+m
    k = min([n,m,nm-n,nm-m])
    print(comb(nm,k,10**9+7))

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
    total //= m
    # print(total)
    # print(nm)
    # tmp = total/nm
    print(total%mod)

Submission status: Time Limit Exceeded

Solution code:
#import sys
MOD = 10 ** 9 + 7
#input = sys.stdin.readline
import math

#import bisect

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
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():
#    h,w,a,b = map(int, input().split())
    x,y = map(int,input().split())
    a=max(x,y)
    b=min(x,y)

    t=a//2
    if b<t:
       ans=0
    elif (b-t)%3==0 and a%2==0:
       aa=a//2
       bb=(b-t)//3*2
       aa-=(b-t)//3
       ans=1
       for i in range(bb):
           ans*=(aa+bb-i)%MOD

       for i in range(bb):
           ans//=(bb-i)%MOD

 #      ans=cmb(aa+bb,bb)

    elif (b-t+1)%3==0 and a%2!=0:
       aa=a//2
       bb=(b-t)//3*2+1
       aa -= (b - t) // 3
       ans=1
       for i in range(bb):
           ans *= (aa+bb - i)%MOD

       for i in range(bb):
           ans //= (bb - i)%MOD

    else:
        ans=0


#    print(ans)
    print(ans%(10**9+7))
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
MAX = 7 * 10**5
fact = [1] * (MAX + 1)
finv = [1] * (MAX + 1)
for i in range(2, MAX + 1):
    fact[i] = fact[i - 1] * i % MOD
    finv[i] = pow(fact[i], MOD - 2, MOD)


def comb(n: int, k: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    return (fact[n] * finv[k] % MOD) * finv[n - k] % MOD


x, y = map(int, input().split())
a = 2 * y - x
b = 2 * x - y

if a < 0 or b < 0:
    ans = 0
elif a % 3 != 0 or b % 3 != 0:
    ans = 0
else:
    a //= 3
    b //= 3
    print(a, b)
    ans = comb(a + b, a)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
MAX = 7 * 10**5
fact = [1 for _ in range(MAX)]
finv = [1 for _ in range(MAX)]
for i in range(2, MAX):
    fact[i] = fact[i - 1] * i % MOD
    finv[i] = pow(fact[i], MOD - 2, MOD)


def comb(n: int, k: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    return (fact[n] * finv[k] % MOD) * finv[n - k] % MOD


x, y = map(int, input().split())
a = 2 * y - x
b = 2 * x - y

if a < 0 or b < 0:
    ans = 0
elif a % 3 != 0 or b % 3 != 0:
    ans = 0
else:
    a //= 3
    b //= 3
    print(a, b)
    ans = comb(a + b, a)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
X,Y = map(int,input().split())
def comb(n,k,p):
    if n<0 or k<0 or n<k: return 0
    if n==0 or k==0: return 1
    a=math.factorial(n) %p
    b=math.factorial(k) %p
    c=math.factorial(n-k) %p
    return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
    if b==0: return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p
if (X+Y)%3 != 0:
    print(0)
else:
    n = int((2*Y-X)/3)
    m = int((2*X-Y)/3)
    nm = n+m
    k = min([n,m])
    print(comb(nm,k,10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
X,Y = map(int,input().split())
 
 
c1 = (2*Y-X)
if c1%3!=0:
  print(0)
 
else:
  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
  
  c1 = c1//3
  c2 = Y-2*c1
  c3 = c1+c2+1
  mod = 10**9+7
  c4 = min(c1,c2)
  x = 1
  y = 1
  for i in range(1,c4+1):
    x = (x * (c3-i)) % mod
    y = (y * i) % mod
    
  result = 1
  for _ in range(mod-2):
    result = (result * y) % mod
    
  result = (result * x) % mod
 
  print(result)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

x, y = map(int, input().split())
a = 2 * y - x
b = 2 * x - y

if a < 0 or b < 0:
    ans = 0
elif a % 3 != 0 or b % 3 != 0:
    ans = 0
else:
    a //= 3
    b //= 3
    # print(a, b)

    MOD = 10**9 + 7
    MAX = a + b + 1
    fact = [1 for _ in range(MAX)]
    finv = [1 for _ in range(MAX)]
    for i in range(2, MAX):
        fact[i] = fact[i - 1] * i % MOD
        finv[i] = pow(fact[i], MOD - 2, MOD)

    def comb(n: int, k: int) -> int:
        if n < k or n < 0 or k < 0:
            return 0
        return (fact[n] * finv[k] % MOD) * finv[n - k] % MOD

    ans = comb(a + b, a)

print(ans)

Submission status: Time Limit Exceeded

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

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**7
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 sum_xy%3!=0:
    print(0)
else:
    ab_sum = sum_xy//3
    a = x-ab_sum
    b = y-ab_sum
    print(cmb(ab_sum,a,inf))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from statistics import mean
from functools import reduce, lru_cache
from itertools import permutations


def main(x, y):
    if (x+y) % 3 != 0:
        return 0

    # ret = reachable((0, 0), (x, y))
    n, m = solve(x, y)
    # print(n, m)

    if n != int(n) or m != int(m):
        return 0

    if n < 0 or m < 0:
        return 0

    # p = n! / (n - r)!
    ret = math.factorial(n+m) // (math.factorial(n) * math.factorial(m))

    return ret % (10**9 + 7)


def solve(x, y):
    return (
        (2*y - x) / 3,
        (2*x - y) / 3
    )


def reachable(current, target):
    if current == target:
        return 1
    elif (current[0]>target[0]) or (current[1]>target[1]):
        return 0
    else:
        return reachable((current[0]+1, current[1]+2), target) + reachable((current[0]+2, current[1]+1), target)


if __name__ == '__main__':
    p = input().split(' ')
    print(main(int(p[0]), int(p[1])))

Submission status: Time Limit Exceeded

Solution code:
import sys

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

MOD = 10**9 + 7

MAX = max(x,y)
MIN = min(x,y)

if (2*MAX - MIN) % 3 != 0 or MAX // MIN > 2:
	print(0)
	sys.exit()

c1 = (2*MAX - MIN) // 3
c2 = MAX - 2*c1

c1 %= MOD
c2 %= MOD

ans = cmb(c1 + c2 , c1)
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
import math
from operator import mul
from functools import reduce
x,y = map(int, input().split())
n = (x+y)//3
r = (2*x-y)//3
mod = 10**9+7

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:
    print(0)
elif 2*x-y<0:
    print(0)
elif -x+2*y<0:
    print(0)
else:
    # print((math.factorial((x+y)//3)//(math.factorial((2*x-y)//3)*math.factorial((2*y-x)//3)))%mod)
    print(combinations_count(n,r)%mod)

Submission status: Time Limit Exceeded

Solution code:
import math

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

if (x+y)%3 != 0:
    ans = 0
else:
    m = (2*x - y) //3
    n = x - 2*m
    if m <0 or n < 0 :
        ans = 0
    else:
        ans = math.factorial(n+m) // (math.factorial(n+m - m) * math.factorial(m))

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

Submission status: Time Limit Exceeded

Solution code:
#import sys

#input = sys.stdin.readline
import math
#import bisect

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True


def main():
#    h,w,a,b = map(int, input().split())
    x,y = map(int,input().split())
    a=max(x,y)
    b=min(x,y)

    t=a//2
    if b<t:
       ans=0
    elif (b-t)%3==0 and a%2==0:
       aa=a//2
       bb=(b-t)//3*2
       aa-=(b-t)//3
       ans=1
       for i in range(bb):
           ans*=aa+bb-i
       ans=ans//(math.factorial(bb))
    elif (b-t+1)%3==0 and a%2!=0:
       aa=a//2
       bb=(b-t)//3*2+1
       aa -= (b - t) // 3
       ans=1
       for i in range(bb):
           ans *= aa +bb- i
       ans=ans//(math.factorial(bb))
    else:
        ans=0


#    print(ans)
    print(ans%(10**9+7))
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

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

MOD = 10**9 + 7

i = x
j = y
if (2*max(x,y) - min(x,y)) % 3 != 0:
	print(0)
	sys.exit()

c1 = (2*max(x,y) - min(x,y)) // 3
c2 = max(x,y) - 2*c1

c1 %= MOD
c2 %= MOD

ans = cmb(c1 + c2 , c1)
print(ans%MOD)

Submission status: Time Limit Exceeded

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

if (x+y)%3!=0:
    print(0)
elif 2*x-y<0:
    print(0)
elif -x+2*y<0:
    print(0)
else:
    print((math.factorial((x+y)//3)//(math.factorial((2*x-y)//3)*math.factorial((2*y-x)//3)))%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
X,Y = map(int,input().split())
def comb(n,r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
if (X+Y)%3 != 0:
    print(0)
else:
    n = int((2*Y-X)/3)
    m = int((2*X-Y)/3)
    if n < 0 or m < 0:
        print(0)
    else:
        print((comb(n+m,min([n,m])))%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from operator import mul
import sys
from scipy import special


input = sys.stdin.readline

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


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

BIG_NUM = 1000000007


if (X + Y) % 3 != 0:
    print(0)
else:
    n = (X - Y * 2) / (-3)
    m = ((2 * X - Y) / 3)
    if n < 0 or m < 0:
        print(0)
    else:
        # print("n:{0},m:{1}".format(n,m))
        print(combinations_count(int(n + m), int(n)) % BIG_NUM)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
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:
from math import factorial

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

if (x + y) % 3 or (x > y * 2) or (x * 2 < y):
  print(0)
else:
  a = (x + y) // 3
  b = (a - abs(x - y)) // 2
  c = 1
  for x in range(a, a-b, -1):
    c *= x
  print(c // factorial(b) % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math
x, y = map(int, input().split())
f = 0
if (x+y)%3 != 0:
	print(f)
else:
	n = int((x+y)/3)
	k = int((math.floor(n/2))- math.floor(abs((x-y)/2)))
	a = int(math.factorial(n) // math.factorial(n - k))%1000000007
	print(a)

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

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

if a.is_integer() and b.is_integer():
    a=int(a)
    b=int(b)
    print(comb(a+b,a,MOD))
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
X,Y = map(int,input().split())
def comb(n,k,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):
  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
if (X+Y)%3 == 0:
    N = (X+Y)//3
    print(comb(N,X-N,10**9+7))
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
def binomial(n, k):
    num = 1
    for i in range(1, min(k, n - k) + 1):
        num = ((num * n) // i) 
        n -= 1
    return num % (10**9 + 7)

x, y = [int(a) for a in input().split()]

n, rn = divmod(2 * x - y, 3)
m, rm = divmod(2 * y - x, 3)

if rn != 0 or rm != 0 or n < 0 or m < 0:
    ans = 0
else:
    a = (2 * x - y) // 3
    b = (2 * y - x) // 3
    ans = binomial(a + b, b)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
import sys

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

if min(X, Y) == 1:
    if max(X, Y) == 2:
        print('1')
    else:
        print('0')
else:

    for i in range(min(X, Y) // 2 + 1):
        if (min(X, Y) - i * 2) * 2 == max(X, Y) - i:
            answer = factorial(min(X, Y) - i) // factorial(i) / factorial(min(X, Y) - i * 2)
            print(round(answer % (10 ** 9 + 7)))
            sys.exit()
    print('0')

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

Submission status: Time Limit Exceeded

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

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**7
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 sum_xy%3!=0:
    print(0)
else:
    ab_sum = sum_xy//3
    a = x-ab_sum
    b = y-ab_sum
    print(cmb(ab_sum,a,inf))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
i8 = np.int64
MOD = 1000000007


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

def com(n, k, fac, finv):
    if n < k:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

def main2():
    stdin = open('/dev/stdin')
    X, Y = map(int, stdin.readline().split())
    a = X + Y
    if a % 3:
        print(0)
    else:
        d = a // 3
        if X < d or Y < d:
            print(0)
        else:
            fac = np.empty(d + 1, i8)
            inv = np.empty(d + 1, i8)
            finv = np.empty(d + 1, i8)
            init(fac, inv, finv)
            ans = com(d, X - d, fac, finv)
            print(ans)

main2()

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

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

# nCr
def nCr(n,r):
  if n<r:
    return 0
  return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

def main():
  x,y=LI()

  if min(x,y)*2<max(x,y):
    return 0

  sm=x+y
  if sm%3!=0:
    return 0

  cnt=sm//3
  ac=cnt//2-((x-y)//2)
  bc=cnt-ac

  # print(ac)
  # print(bc)

  return nCr(cnt,ac)%mod


# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
#D
import numpy as np
import math
def power(x, y, mod):
    if y == 0:
        t = 1
    elif y == 1:
        t = x % mod
    elif y % 2 == 0:
        t = (power(x, int(y/2), mod) ** 2) % mod
    else:
        t = (x * (power(x, int(y/2), mod) ** 2)) % mod
    return t
    
    
def frac_mod(n, mod, f=1):
    for i in range(1, n + 1):
        f = (f * i) % mod
    return f

def ifrac_mod(n, mod, f_inv=1):
    for i in range(n, 1, -1):
        f_inv = (f_inv * power(i, mod-2, mod)) % mod
    return f_inv

def cmb_mod(n, r, mod):
    n_frac = frac_mod(n, mod)
    n_r_ifrac = ifrac_mod(n-r, mod)
    r_ifrac = ifrac_mod(r, mod)
    
    return int((n_frac * n_r_ifrac * r_ifrac) % mod)
mod = 10**9+7
x,y = map(int, input().split())
a = np.array([[1,2], [2,1]])
b = np.array([x,y])
res = np.linalg.solve(a,b)
is_ok = True
if not (res[0].is_integer() and res[1].is_integer()):
    is_ok = False
    ans = 0
x_res = int(res[0])
y_res = int(res[1])
if is_ok:
    ans = cmb_mod(x_res+y_res, x_res, mod)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
input1 = list(map(int,input().split()))

X = input1[0]
Y = input1[1]

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

if Y<X/2:
  print(0)
  exit()

if Y>X*2:
  print(0)
  exit()

s = int((2*X-Y)/3)
t = int((-X+2*Y)/3)

n = s+t
r = min(s,t)

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


ans = comb(n,r,10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
X,Y=map(int,input().split())
x=2*X-Y
y=2*Y-X
over=1
under=1
i=x+y
if x%3!=0 or y%3!=0:
    print(0)
else:
    x=x//3
    y=y//3
    n=x+y
    r=min(x,y)
    for i in range(max(x,y)):
        over*=(n-i)
        under*=(n-r-i)
    ans=over//under
    print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
from inspect import currentframe
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def MI() : return map(int, input().split())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def chkprint(*args) : names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}; print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

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

X, Y = LI()

ans = 0
for i in range(int(X // 2) + 1):
    if 2 * (X - (i * 2)) + i == Y:
        ans += comb((X - (i * 2)) + i, i)
        ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
sys.setrecursionlimit(200000)
MOD = 10 ** 9 + 7


def main():
    X, Y = map(int, input().split())
    if (X + Y) % 3 != 0:
        print(0)
        exit()
    else:
        m = (2 * X - Y) / 3
        n = (2 * Y - X) / 3
        if m < 0 or n < 0:
            print(0)
            exit()
        else:
            mn = math.factorial(m + n)
            a = math.factorial(m)
            b = math.factorial(n)
            print(mn // (a * b) % MOD)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
list = input().split(" ")
x = int(list[0])
y = int(list[1])
k = y + x
p = int((2*x-y)/3)
t = int(k/3)
if k%3 != 0 or y > 2*x or y < x/2:
  print(0)
else:
  combi = []
  for a in range(0,t+1):
      s = 0
      for j in itertools.combinations(range(t),a):
          s+=1
      combi.append(s)
  print(combi[p])

Submission status: Time Limit Exceeded

Solution code:
X,Y=map(int,input().split())
if (X+Y)%3!=0:
  print(0)
else:
  if 2*X<Y or 2*Y<X:
    print(0)
  else:
    p=(2*X-Y)//3
    q=(X+Y)//3
    
    import math
    print(math.factorial(q) //(math.factorial(p) *math.factorial(q- p))%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math

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

#initial: (X,Y) = (0,0)

num = 10**9 + 7
sum = 0
#print(num)
for i in range(X+1):# i は1step回数。２stepを行う回数は(X-i)//2(余りあったらbreak)
    if (X-i)% 2 == 0:
        j = (X-i)//2
        #print("i and j is ", i, j)
        if i * 2 + j  == Y:
            #conbination_num1 = (math.factorial(i + j) / math.factorial(i)) % num
            sum += math.factorial(i + j) / (math.factorial(i) * math.factorial(j)) % num  

print(int(sum))

Submission status: Time Limit Exceeded

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

if (x+y)%3 !=0 or max(x,y)/min(x,y)>2:
    print(0)
    exit()

n =int((x+y)/3)
maxm = round((n+1)/2)
m= n*2 - max(x,y) +1


if m==1:
    print(1)
elif m==2:
    print(int(m))
elif m==3:
  ss = numpy.cumsum(range(1,n))
  print(ss[n-2])
else:  
  ss = range(1,n)
  for i in range(1,m-2):
    ss += numpy.cumsum(ss)
    i+=1
  print(ss[-1]%(10**9+7))

Submission status: Time Limit Exceeded

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


def power_func(a, b, p):
    if b == 0:
        return 1
    if b % 2 == 0:
        d = power_func(a, b//2, p)
        return d*d % p
    if b % 2 == 1:
        return (a*power_func(a, b-1, p)) % p


def comb(n, k, 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


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

if w.is_integer():
    w = int(w)
else:
    print(0)
    sys.exit()

a = min(b, w-b)
ans = comb(w, a, 10**9+7)
print(ans)

Submission status: Time Limit Exceeded

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
    if k < 0 or l <0:
        answer = 0
    else:
        answer = combinations_count(k+l, l) % (10**9 + 7)
else:
    answer = 0

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

mod = 10**9 + 7

stack = deque([(0, 0)])


def dfs(stack):
    ans = 0
    while len(stack) > 0:
        x, y = stack.pop()
        if x == X and y == Y:
            ans += 1
            ans %= mod
        for i, j in ((2, 1), (1, 2)):
            new_x, new_y = x+i, y+j
            if new_x > X or new_y > Y:
                continue
            stack.append((new_x, new_y))

    return ans


ans = dfs(stack)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
x,y = map(int,input().split())
if (x+y)%3 != 0 or min(x,y)*2 < max(x,y):
    ans = 0
else:
    if x > y:
        x,y = y,x
    n = (x+y)//3 + 1
    k = x - (n-1) + 1
    ans = math.factorial(n-1) // (math.factorial(k-1)*math.factorial(n-k))
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

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

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(comb(n+m,n,exact=True))
  ans = int(ans%(10**9+7))
  print(ans)
else:
  print(0)

Submission status: Time Limit Exceeded

Solution code:
from math import *
def calc(k):
    return [ factorial(k)/(factorial(i)*factorial(k-i)) for i in range(k+1)]

x,y = map(int,input().split())
distance = x + y
if distance % 3 != 0:
  ans = 0
elif x/y > 2:
  ans = 0
elif y/x > 2:
  ans = 0
else:
  c = abs(y-x) % 2
  a = int(distance / 3)
  b = int((abs(y-x) - c)/2)

  prev = calc(a)
  if c == 0:
    ans = prev[int(a/2) + b]
  else:
    ans = prev[int((a+1)/2)+b]
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import math
x,y=map(int,input().split())
if (x+y)%3!=0 or x>y*2 or y>x*2:
  print("0")
else:
  z=abs(x-y)
  w=int((x+y)/3)
  k=(w-z)/2
  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
  a=comb(w,k,10**9+7)
  print(a)

Submission status: Time Limit Exceeded

Solution code:
x, y = input().split()
x = int(x)
y = int(y)
xy_sum = x + y
point_num = 0
kimari = 10 ** 9 + 7
if (xy_sum % 3 == 0):
    point_num += ((xy_sum - 1) // 3) ** 2
    point_num += (xy_sum - 1) // 6
    count = 2 ** point_num
    print(count % kimari)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
pos = map(int, input().split())

x, y = sorted(pos)

num_twos = x // 2
rem = x % 2

solution = 0

max_n = 5*10**5

result = max_n*[None]
result[0] = 1
for i in range(1, max_n):
    result[i] = i*result[i-1]
m = 10**9 + 7 - 2


def ncr(n, r):
    return result[n] * result[r]**(m) * result[n-r]**(m)


while not (y == num_twos + (rem*2)):
    num_twos -= 1
    rem += 2

    if y < (num_twos + rem*2):
        print(0)
        exit()

solution = ncr(num_twos + rem, rem)

print(int(solution))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m = map(int,input().split())
d = [[0 for _ in range(m+1)] for _ in range(n+1)]
mod = 1000000007
def fuc():
    que = deque([])
    que.append((0,0))
    d[0][0] = 1
    
    while que:
        p = que.popleft()

        dx = [1,2]
        dy = [2,1]
        for i in range(2):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if nx <= n and ny <= m:
                d[nx][ny] += d[p[0]][p[1]]
                que.append((nx,ny))
    return d[n][m]

print(fuc()%mod)

Submission status: Time Limit Exceeded

Solution code:

from sys import stdin
from itertools import combinations

x,y = map(int, stdin.readline().rstrip().split())


countx = 0
county = 0
while x>0 and y>0:
    if x > y:
        x -= 2
        y -= 1
        countx += 1
    else:
        x -= 1
        y -= 2
        county += 1

if x == 0 and y == 0:
    ans = len(list(combinations(list(range(countx + county)),countx))) % (10**7+7)
    print(ans)
    exit()
else:
    print(0)
    exit()