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 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 (2*y-x)%3!=0 or (2*x-y)%3!=0:
    print(0)
else:
    k=(2*y-x)//3
    l=(2*x-y)//3
    a = comb(k+l,l,10**9+7)
    print(a)

Submission status: Time Limit Exceeded

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

mod = 10**9+7 #出力の制限
N = 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 )


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

if (2*y-x)%3!=0 or (2*x-y)%3!=0:
    print(0)
else:
    k=(2*y-x)//3
    l=(2*x-y)//3
    a = cmb(k+l,l,mod)
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

if m < 0 or n < 0 or (x+y)%3 != 0:
	print(0)
else:
	print(math.factorial(m+n) // (math.factorial(m+n - n) * math.factorial(n)) % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

X, Y = map(int, input().split())
que = deque([])
que.append((0,0))

ans = 0
while que:
	x_now, y_now = map(int, que.pop())
	if x_now == X and y_now == Y:
		ans+=1
		continue
	next = [(x_now+1, y_now+2), (x_now+2, y_now+1)]
	for p in next:
		if p[0] > X or p[1] > Y:
			continue
		que.appendleft(p)
		
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math
X, Y = map(int, input().split())
MOD = 10**9 + 7

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

def solve():
    a = (2*Y-X) / 3
    b = (2*X-Y) / 3
    if a.is_integer() and b.is_integer() and a >= 0 and b >= 0:
        ans = combinations_count(a+b, min(a, b))
        print(ans%MOD)
    else:
        print(0)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
X, Y = map(int,input().split())
ans = 0
start = [0, 0]
move = [[1, 2], [2, 1]]
queue = deque()
queue.append(start)
while queue:
  x, y = queue.popleft()
  for i in range(len(move)):
    nextX = x + move[i][0]
    nextY = y + move[i][1]
    #print(i,nextX, nextY)
    if nextX == X and nextY == Y:
      ans += 1
    if nextX < X and nextY < Y:
      queue.append([nextX, nextY])
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7

def combi(m,n):
    child = 1
    mom = 1
    while n != 0:
        child *= m
        child %= mod
        mom *= n
        mom %= mod
        m -= 1
        n -= 1
    return (child*modpow(mom,mod-2))%mod

def bi(x):
    o = []
    while x != 0:
        o.append(x%2)
        x //= 2
    return o

def modpow(m,n):
    o = bi(n)
    p = [m]
    leo = len(o)
    while leo > len(p):
        a = p[-1]
        p.append(a*a%mod)
    b = 1
    for i in range(leo):
        if o[i] == 1:
            b *= p[i]
            b %= mod
    return b

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

A = (-1) * X +   2  * Y
B =   2  * X + (-1) * Y

if A % 3 or B % 3:
    print(0)
    exit()

A //= 3
B //= 3

print(combi(A+B,min(A,B)))

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7

def combi(m,n):
    child = 1
    mom = 1
    while n != 0:
        child *= m
        child %= mod
        mom *= n
        mom %= mod
        m -= 1
        n -= 1
    return (child*modpow(mom,mod-2))%mod

def modpow(m,n):
    if n == 0:
        return 1
    a = modpow(m,n//2)
    b = m if n % 2 else 1
    b *= a
    b %= mod
    b *= a
    b %= mod
    return b

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

A = (-1) * X +   2  * Y
B =   2  * X + (-1) * Y

if A % 3 or B % 3:
    print(0)
    exit()

A //= 3
B //= 3

print(combi(A+B,min(A,B)))

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7

def combi(m,n):
    child = 1
    mom = 1
    while n != 0:
        child *= m
        child %= mod
        mom *= n
        mom %= mod
        m -= 1
        n -= 1
    return (child*modpow(mom,mod-2))%mod

def modpow(m,n):
    if n == 0:
        return 1
    if n % 2:
        return ((modpow(m,n//2)**2)*m)%mod
    else:
        return (modpow(m,n//2)**2)%mod

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

A = (-1) * X +   2  * Y
B =   2  * X + (-1) * Y

if A % 3 or B % 3:
    print(0)
    exit()

A //= 3
B //= 3

print(combi(A+B,min(A,B)))

Submission status: Time Limit Exceeded

Solution code:
# 逆元
# a^n mod を計算する
def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res

# a^{-1} mod を計算する
def modinv(a, mod):
    return modpow(a, mod - 2, mod)


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

mod = 10 ** 9 + 7

if (x + y) % 3 == 0 and min(x, y) * 2 >= max(x, y):
    a = (2 * y - x) // 3
    b = (2 * x - y) // 3
    x = 1
    for i in range(2, a + b + 1):
        x = x * i % mod
    for i in range(2, a + 1):
        x = x * modinv(i, mod) % mod
    for i in range(2, b + 1):
        x = x * modinv(i, mod) % mod
    print(x)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
X, Y = map(int, input().split())
if (2*X-Y) < 0 or (2*Y-X) < 0:
    print(0)
    exit()
if (2*X-Y)%3 != 0 or (2*Y-X)%3 != 0:
    print(0)
    exit()
if (2*X-Y)/3 == 0 or (2*Y-X)/3 == 0:
    print(1)
    exit()

a = int((2*X-Y)/3)
b = int((2*Y-X)/3)
total = a+b
def Fac(n,m):
    mul = lambda a, b: a*b
    if n == 1 or n == 0:
        return 1
    else:
        return reduce(mul,range(n-m+1,n+1))
x = min(a,b)
route = Fac(total,x)/Fac(x,x)
print(int(route)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
X, Y=list(map(int,(input().split())))
m=10**9+7
N=(X+Y)//3
bikkuri=[1 for i in range(N+2)]
gyaku=[1 for i in range(N+2)]
for i in range(1, N+1):
    bikkuri[i+1] =((i+1)*bikkuri[i])%m
    gyaku[i+1] = pow(bikkuri[i+1], m-2, m)
def comb(n, r):
    return (bikkuri[n]*gyaku[r]*gyaku[n-r])%m
if (X+Y)%3==1 or (X+Y)%3==2:
    print(0)
else:
    if X<N or Y<N:
        print(0)
    else:
        print(comb((X-N)+(Y-N), Y-N))

Submission status: Time Limit Exceeded

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

def main():
    mod = 10 ** 9 + 7
    x, y = map(int, input().split())
    if (2 * y - x) % 3 != 0:
        print(0)
        return None

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

    if n < 0 or m < 0:
        print(0)
    elif n == 0 and m == 0:
        print(0)
    elif n == 0 or m == 0:
        print(1)
    else:
        ans = math.factorial(n+m) % mod
        ans = ans * modinv(math.factorial(n)) % mod
        ans = ans * modinv(math.factorial(m)) % mod
        print(ans)

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
from numpy.linalg import solve
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:
    left = [[1, 2],
            [2, 1]]
    right = [x, y]
    n, m = map(int, solve(left, right))
    if n < 0 or m < 0:
        print(0)
    else:
        total = n + m
        print(cmb(total, min(n, m)) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import cmath
import numpy as np
import sys

INF=1**18
MOD=10**9+7


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

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

N=(x+y)//3
if x<N or y<N:
    print(0)
    exit()

def moP(x,n):
    res=1
    while n>0:
        if n & 1:
            res=res*x%MOD
        x=x*x%MOD
        n>>=1
    return res


fa=[1]*(N+1)
re=[1]*(N+1)


for i in range(1, N+1):
    fa[i]=fa[i-1]*i%MOD
    re[i]=moP(fa[i], MOD-2)

def C(n,k):
    if n==0 or n==k:
        return 1
    return fa[n]*re[k]%MOD*re[n-k]%MOD

K=min(x,y)-N
print(C(N,K))

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb

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

i = 2 * X - Y
if i % 3 != 0:
    print('0')
else:
    y = (2 * X - Y) // 3
    x = X - 2 * y
    result = comb((x + y), x, exact = True) % (10 ** 9 + 7)
    print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys

x, y = map(int, input().split())
n, m = (-x + 2 * y) // 3, (2 * x - y) // 3
if (x + y) % 3 != 0 or n < 0 or m < 0:
	print(0)
	sys.exit()

modi = int(1e9) + 7
fmax = int(1e6) * 2 + 1
fact = [1] * fmax
inv = [1] * fmax
ifact = [1] * fmax
for i in range(2, fmax):
	fact[i] = fact[i - 1] * i % modi
	inv[i] = modi - inv[modi % i] * (modi // i) % modi
	ifact[i] = ifact[i - 1] * inv[i] % modi

cnt = fact[n + m] * ifact[n] * ifact[m]
ans = int(cnt) % modi

print(ans)

Submission status: Time Limit Exceeded

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

p = [[0 for i in range(Y+2)]for j in range(X+2)]
waru = 1000000007

p[0][0]=1

for y in range(Y):
    for x in range(X):
        p[x+1][y+2] += p[x][y] % waru
        p[x+2][y+1] += p[x][y] % waru

print(p[X][Y] % waru)

Submission status: Time Limit Exceeded

Solution code:
import sys


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


def main():
    X, Y = map(int, input().split())
    C = 10**9 + 7

    if (X + Y) % 3 != 0:
        print(0)
        sys.exit()
    cnt = [0, 0]
    if Y / X >= 1:
        (i, j) = (1, 2)
        cnt[0] += 1
    else:
        (i, j) = (2, 1)
        cnt[1] += 1

    while (i, j) != (X, Y):
        if Y * i > X * j:
            i += 1
            j += 2
            cnt[0] += 1
        else:
            i += 2
            j += 1
            cnt[1] += 1

    ans = 1
    for i in range(1, sum(cnt) + 1):
        ans *= i
        ans %= C
    for i in range(1, cnt[0] + 1):
        ans *= mod_inv(i, C)
        ans %= C
    for i in range(1, cnt[1] + 1):
        ans *= mod_inv(i, C)
        ans %= C

    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys


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


def main():
    X, Y = map(int, input().split())
    C = 10**9 + 7

    if (X + Y) % 3 != 0:
        print(0)
        sys.exit()
    cnt = [0, 0]
    if Y / X >= 1:
        (i, j) = (1, 2)
        cnt[0] += 1
    else:
        (i, j) = (2, 1)
        cnt[1] += 1

    while (i, j) != (X, Y):
        if Y / X > j / i:
            i += 1
            j += 2
            cnt[0] += 1
        else:
            i += 2
            j += 1
            cnt[1] += 1

    ans = 1
    for i in range(1, sum(cnt) + 1):
        ans *= i
        ans %= C
    for i in range(1, cnt[0] + 1):
        ans *= mod_inv(i, C)
        ans %= C
    for i in range(1, cnt[1] + 1):
        ans *= mod_inv(i, C)
        ans %= C

    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb

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

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

N = (X+Y) // 3

A = X - N
B = Y - N

ans = comb(A+B, A, exact=True) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = pow(10, 9) + 7

N = pow(10, 6)

fact = [0]*N
inv = [0]*N

fact[0] = inv[0] = 1
inv[1] = fact[1] = 1
for i in range(2, N):
	fact[i] = (i*fact[i-1])%mod
	inv[i] = pow(fact[i], mod-2, mod)

def ncr(n, r):
	return (fact[n]*inv[r]*inv[n-r])%mod

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

if (X + Y)%3 != 0:
	print(0)
else:
	m = (2*Y - X)//3
	n = (X - m)//2
	if n < 0 or m < 0:
		print(0)
	else:
		ans = ncr(n+m, n)
		print(ans)

Submission status: Time Limit Exceeded

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

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

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

solve()

Submission status: Time Limit Exceeded

Solution code:
x, y = map(int, input().split())
# m + 2n = x
# 2m + n = y

def mod_inv(a,m):
    r = [1,0,a]
    w = [0,1,m]
    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 (m+w[0]%m)%m

def mCn(m, n):
    res = 1
    for i in range(1,m+1):
        res = res*i%mod
    for i in range(1,n+1):
        res = res*mod_inv(i,mod)%mod
    for i in range(1,m-n+1):
        res = res*mod_inv(i,mod)%mod
    return res
 
if (-x+2*y>=0) and (2*x-y>=0) and ((-x+2*y)%3==0) and ((2*x-y)%3==0):
    m = int((-x+2*y)/3)
    n = int((2*x-y)/3)
    mod = 10**9+7
    # res = math.factorial(m+n)/(math.factorial(m)*math.factorial(n)) % mod
    res = mCn(m+n, m)
    print(res)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7

def cmb(n, r, mod):
    a, b = 1, 1
    for i in range(n, n - r, -1):
        a = a * i
    for i in range(r, 1, -1):
        b = b * i
    return a // b % mod
        


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

if not (X+Y) % 3 == 0:
    print(0)
else:
    n = (Y - 2*X) // -3
    m = X - (2 * n)
    if n < 0 or m < 0:
        print(0)
    else:
        print(cmb(n+m, n, mod))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys

x, y = map(int, input().split())
if (x + y) % 3 != 0:
    print(0)
    sys.exit()

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

if a < 0 or b < 0:
    print(0)
    sys.exit()

#(a+b)! / a!*b!
def combi(c, num):
    result = 1
    for i in range(num):
        result *= (c-i)
    return result
    
out = combi(a+b, a) // combi(a, a)

print(out)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial

x, y = map(int, input().split())
n, m = (-x + 2 * y) // 3, (2 * x - y) // 3
if (x + y) % 3 != 0 or n < 0 or m < 0:
	print(0)
	sys.exit()

cnt = factorial(n + m) // factorial(n) // factorial(m)
ans = int(cnt) % (int(1e9) + 7)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# bfs (ムリ)
from collections import deque

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

cnt = 0
que = deque([(0, 0)])
while len(que) > 0:
	(tar_x, tar_y) = que.pop()
	(new_x1, new_y1) = (tar_x + 1, tar_y + 2)
	(new_x2, new_y2) = (tar_x + 2, tar_y + 1)
	# print((tar_x, tar_y))

	if (new_x1, new_y1) == (x, y):
		cnt += 1
	if (new_x2, new_y2) == (x, y):
		cnt += 1

	if new_x1 < x and new_y1 < y:
		que.append((new_x1, new_y1))
	if new_x2 < x and new_y2 < y:
		que.append((new_x2, new_y2))

ans = cnt % (int(1e9) + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys

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

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

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

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

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

Submission status: Time Limit Exceeded

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

n_bunshi = 2*X - Y

if n_bunshi % 3 != 0 or n_bunshi < 0:
    print("0")
    sys.exit()

m_bunshi = 2*Y - X
if m_bunshi % 3 != 0 or m_bunshi < 0:
    print("0")
    sys.exit()

n = n_bunshi // 3
m = m_bunshi // 3

n = int(n)
m = int(m)
bunshi = math.factorial(n+m)
bunbo_n = math.factorial(n)
bunbo_m = math.factorial(m)
constant = 10**9 + 7
#print(n,m, constant)
answer0 = bunshi // bunbo_n // bunbo_m
#print(math.log(answer0))
answer = answer0 % constant
print(answer)

Submission status: Time Limit Exceeded

Solution code:
def knight(x, y):
    mod = 10 ** 9 + 7
    x, y = min(x, y), max(x, y)

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

    move = (x + y) // 3
    right = 2 * move - y
    up = move-right

    ans = 1
    for i in range(1, move + 1):
        ans *= i
        ans %= mod
    for i in range(1, right + 1):
        ans *= pow(i, mod - 2, mod)
        ans %= mod
    for i in range(1, up + 1):
        ans *= pow(i, mod - 2, mod)
        ans %= mod
    return ans


if __name__ == "__main__":
    x, y = map(int, input().split())
    ans = knight(x, y)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
mod = 10**9+7
def comb(n,k,p):
    if n<0 or k<0 or n<k:
        return 0
    if n==0 or k==0:
        return 1
    a = factorial(n)%p
    b = factorial(k)%p
    c = factorial(n-k)%p
    return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p

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

x,y = map(int,input().split())
if (x+y)%3 != 0:
    print(0)
else:
    n = (2*x - y)//3
    m = (2*y - x)//3
    if min(n,m) < 0:
        print(0)
        exit()
    ans = comb(n+m , n , mod)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    p = 1000000007
    xy = input().split(' ')
    x = int(xy[0])
    y = int(xy[1])

    m = 2*x-y
    n = 2*y-x

    if m<0 or n<0:
        return 0
    if m%3!=0 or n%3!=0:
        return 0
    m //= 3
    n //= 3

    k = m if m <= n else n
    l = n+m

    s = 1
    for i in range(k):
        s *= (l-i)
        s //= (i+1)
    
    return s%p

if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

Solution code:
import math

def combination(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
eps = 10**9 + 7

x, y = map(int, input().split())
if (2 * x - y) % 3 != 0 or (2 * y - x) % 3 != 0:
    print(0)
elif 2 * y - x < 0 or 2 * x - y < 0:
    print(0)
else:
    vertical = (2 * y - x) // 3
    horizontal = (2 * x - y) // 3
    total = vertical + horizontal
    print(int(combination(total, horizontal) % eps))

Submission status: Time Limit Exceeded

Solution code:
def m(n,r):
    d=1
    c=1
    for i in range(r):
        d*=(n-i)
        c*=(i+1)
    return(int(d/c))

n=[int(i) for i in input().split()]
a=sum(n)
if a%3 != 0:print(0)

else:
    b=int(a/3)
    if b==1:
        print(1)
    else:
        c=n[0]-b
        d=n[1]-b
        if c<0 or d<0: print(0)

        else:
            if c==d:
                c=int(b/2)
            d=m(b,min(c,d))
            print(d%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

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

def rec(i,j):
    if(i==0 and j==0):
        return 1
    elif(i<0 or j<0):
        return 0
    else:
        return rec(i-1,j-2)+rec(i-2,j-1)
ans=rec(x,y)
print(int(ans%(1e+9+7)))

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

if a==-1 or b==-1:
  print(0)
else:
  ans = math.factorial(a+b)/(math.factorial(a)*math.factorial(b))
  print(int(ans%(10**9+7)))

Submission status: Time Limit Exceeded

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

def inv_mod(a, p=MOD):
    def inv_mod_sub(a, p):
        if a == 1:
            return 1, 0
        else:
            d, r = p//a, p%a
            x, y = inv_mod_sub(r, a)
            return y-d*x, x
    if p < 0: p = -p
    a %= p
    return inv_mod_sub(a,p)[0] % p

def comb_mod(n, k):
    if k < 0 or k > n:
        return 0
    else:
        return f_mod[n]*f_mod_inverse[k]*f_mod_inverse[n-k] % MOD

if (2*y-x) % 3 != 0 or (2*x-y) % 3 != 0:
  print(0)
else:
  k,l = (2*y-x)//3,(2*x-y)//3
  f_mod=[1]*(10**6)
  f_mod_inverse=[1]*(10**6)
  for i in range(1,10**6):
    f_mod[i]=f_mod[i-1]*i%MOD
    f_mod_inverse[i]=f_mod_inverse[i-1]*inv_mod(i)%MOD
  print(comb_mod(k+l,l))

Submission status: Time Limit Exceeded

Solution code:
def modpow(a, b, mod=1):
    ret = 1
    while b > 0:
        if b % 2 == 1:
            ret = ret * a % mod
        a = a * a % mod
        b //= 2
    return ret


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

if (2 * X - Y) % 3 != 0 or (2 * Y - X) % 3 != 0:
    print(0)
elif (2 * X - Y) // 3 < 0 or (2 * Y - X) // 3 < 0:
    print(0)
else:
    A, B = (2 * X - Y) // 3, (2 * Y - X) // 3
    ans = 1
    for n in range(A + B, A, -1):
        ans = ans * n % MOD
    for n in range(1, B + 1):
        ans = ans * modpow(n, MOD - 2, MOD) % MOD
    print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
import itertools
X, Y=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
MOD = 10**9 + 7
from math import factorial
# a = factorial(n+m) / factorial(n) / factorial(m)
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

# a = cmb(n, r)

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
X, Y=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき

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

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

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

    if n<0 or m<0:
        print(0)
    else:
        print(len(list(itertools.combinations(range(n+m), n))) % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
x,y=map(int,input().split())
if (x+y)%3 : 
	print(0)
else:
	if 3*min(x,y)<x+y :
		print(0)
	else:
		m=int((2*y-x)/3)
		n=int((2*x-y)/3)
		tu=1
		mau=1
		for i in range(m+1,m+n+1) :
			tu=tu*i
			mau=mau*(i-m)
		res=int(tu/mau)
		print(res%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math
x,y=map(int,input().split())
if (x+y)%3 : 
	print(0)
else:
	if 3*min(x,y)<x+y :
		print(0)
	else:
		m=int((2*y-x)/3)
		n=int((2*x-y)/3)
		mod=1000000007
		tu=1
		mau=1
		for i in range(m+1,m+n+1) :
			tu=tu*i
			mau=mau*(i-m)
		mau=int(math.pow(mau,mod-2))
		print(tu*mau%mod)

Submission status: Time Limit Exceeded

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

if (x+y)%3 : 
	print(0)
else:
	if 3*min(x,y)<x+y :
		print(0)
	else:
		m=int((2*y-x)/3)
		n=int((2*x-y)/3)
		mod=1000000007
		tu=1
		mau=1
		for i in range(m+1,m+n+1) :
			tu=tu*i%mod
		for i in range(2,n+1) :
			mau=mau*i%mod
		mau=mau**(mod-2)
		mau=mau%mod
		print(tu*mau%mod)

Submission status: Time Limit Exceeded

Solution code:
# 法Pの下での組み合わせ数 nCk を求める
# MAX: nの最大値

P = (10**9)+7

fac=[]
inv=[]
finv=[]

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

def COMinit(MAX):
    global fac, inv, finv
    fac=[1 for _ in range(MAX)]
    inv=[1 for _ in range(MAX)]
    finv=[1 for _ in range(MAX)]
    #print('len(fac): {}'.format(len(fac)))
    #print(MAX)
    for i in range(2,MAX):
        #print(i)
        fac[i] = fac[i-1]*i % P
        (d, x, y) = exEuclid(i, P)
        inv[i] = x
        finv[i] = finv[i-1]*inv[i] % P

def COM(n, k):
    if(n<k):
        return 0
    elif ( (n<0)or(k<0)):
        return 0
    else:
        return fac[n]*(finv[n-k]*finv[k] % P) % P

####

#print('x, y:')
x, y = list(map(int,input().split()))
MAX = (x+y)//3 +1  # (X+Y)/3より大きい整数 1 <= X, Y <= 10**6
COMinit(MAX)

if ((x+y)%3 != 0):
    print(0)
    exit()
else:
    n1 = (-x+2*y)//3
    n2 = (2*x -y)//3
    if (n1<0):
        print(0)
        exit()
    elif(n2<0):
        print(0)
        exit()
    else:
        npath = COM(n1+n2, n1)
        print(npath)

Submission status: Time Limit Exceeded

Solution code:
# 法Pの下での組み合わせ数 nCk を求める
# MAX: nの最大値

MAX = (10**6)*2//3 +1  # (X+Y)/3より大きい整数 1 <= X, Y <= 10**6
P = (10**9)+7

fac=[1 for _ in range(MAX)]
inv=[1 for _ in range(MAX)]
finv=[1 for _ in range(MAX)]

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

def COMinit():
    global fac, inv, finv
    #print('len(fac): {}'.format(len(fac)))
    #print(MAX)
    for i in range(2,MAX):
        #print(i)
        fac[i] = fac[i-1]*i % P
        (d, x, y) = exEuclid(i, P)
        inv[i] = x
        finv[i] = finv[i-1]*inv[i] % P

def COM(n, k):
    if(n<k):
        return 0
    elif ( (n<0)or(k<0)):
        return 0
    else:
        return fac[n]*(finv[n-k]*finv[k] % P) % P

####

COMinit()
#print('x, y:')
x, y = list(map(int,input().split()))

if ((x+y)%3 != 0):
    print(0)
    exit()
else:
    n1 = (-x+2*y)//3
    n2 = (2*x -y)//3
    if (n1<0):
        print(0)
        exit()
    elif(n2<0):
        print(0)
        exit()
    else:
        npath = COM(n1+n2, n1)
        print(npath)

Submission status: Time Limit Exceeded

Solution code:
import math

def comb(n, k, m):
  nf  = math.factorial(n)   % m
  kf  = math.factorial(k)   % m
  nkf = math.factorial(n-k) % m
  return nf * pow_mod(kf*nkf%m, m-2, m) % m

def pow_mod(a, b, m):
  if b == 0:
    return 1
  elif b%2 == 0:
    d = pow_mod(a, b//2, m) % m
    return d * d % m 
  else:
    d = pow_mod(a, (b-1)//2, m)
    return  d * d * a % m

tmp = list(map(int, input().split()))
x = tmp[0]
y = tmp[1]

ans = 0
mod = 10**9 + 7

if (x + y) % 3 != 0:
  ans = 0
else:
  n = (x + y) // 3
  if min(x, y) < n:
    ans = 0
  elif min(x,y) == n:
    ans = 1
  else:
    r = min(x, y) - n
    ans = comb(n, r, mod)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

def comb(n, k, m):
  nf  = math.factorial(n)   % m
  kf  = math.factorial(k)   % m
  nkf = math.factorial(n-k) % m
  return nf * pow_mod(kf*nkf%m, m-2, m) % m

def pow_mod(a, b, m):
  if b == 0:
    return 1
  elif b%2 == 0:
    return pow_mod(a, b//2, m) ** 2 % m 
  else:
    return pow_mod(a, b-1, m) * a % m

tmp = list(map(int, input().split()))
x = tmp[0]
y = tmp[1]

ans = 0
mod = 10**9 + 7

if (x + y) % 3 != 0:
  ans = 0
else:
  n = (x + y) // 3
  if min(x, y) < n:
    ans = 0
  elif min(x,y) == n:
    ans = 1
  else:
    r = min(x, y) - n
    ans = comb(n, r, mod)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

def comb(n, k, m):
  nf  = math.factorial(n)   % m
  kf  = math.factorial(k)   % m
  nkf = math.factorial(n-k) % m
  return nf * pow_mod(kf, m-2, m) * pow_mod(nkf, m-2, m) % m

def pow_mod(a, b, m):
  if b == 0:
    return 1
  elif b%2 == 0:
    return pow_mod(a, b//2, m) ** 2 % m 
  else:
    return pow_mod(a, b-1, m) * a % m

tmp = list(map(int, input().split()))
x = tmp[0]
y = tmp[1]

ans = 0
mod = 10**9 + 7

if (x + y) % 3 != 0:
  ans = 0
else:
  n = (x + y) // 3
  if min(x, y) < n:
    ans = 0
  elif min(x,y) == n:
    ans = 1
  else:
    r = min(x, y) - n
    ans = comb(n, r, mod)

print(ans)

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
factX = factY = factN = 1
for i in range(2,n+1):
    factN *= i % MOD
    if i == x: factX = factN
    if i == y: factY = factN

inv_t = [0]+[1]
for i in range(2,max(factX,factY)+1):
    inv_t += [inv_t[MOD % i] * (MOD - int(MOD / i)) % MOD]

# print(x,y,n)
# print(factN)
# print(inv_t[x],inv_t[y])

c = factN * inv_t[factX] * inv_t[factY]
c %= MOD
print(c)

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
factX = factY = factN = 1
for i in range(1,n+1):
    factN *= i
    if i == x: factX = factN
    if i == y: factY = factN
c = factN // factX // factY
print(c%MOD)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
x,y=map(int,input().split())
if (x+y)%3!=0:
  print(0)
  exit()
if (2*y-x)/3<0 or (2*x-y)/3<0:
  print(0)
else:
  print(factorial((x+y)//3)//factorial((2*x-y)//3)//factorial((2*y-x)//3))