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:
x,y = map(int,input().split())

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 (x+y)%3!=0:
    print(0)
else:
    a = (2*x - y) // 3
    b = (2*y - x) // 3

    print(comb(a+b, a, 10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

hash_no = 10 ** 9 + 7


def move(x, y, X, Y):
    global counter
    if x > X:
        return
    if y > Y:
        return
    if (x == X) and (y == Y):
        counter += 1
        return
    if Y > 2 * (X - x) + y:
        return
    if Y < (X - x) / 2 + y:
        return

    move(x + 1, y + 2, X, Y)
    move(x + 2, y + 1, X, Y)


def main():
    global counter
    x, y = map(int, input().split())
    counter = 0

    if (x + y) % 3 != 0:
        print(0)
    else:
        move(0, 0, x, y)
        print(counter % hash_no)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 0.0

# 1.2
# 2.1

# 3.3
# 2.4
# 4.2

# 4.5
# 5.4
# 3.6
# 6.3

# 6.6
# 4.8
# 8.4
# 5.7
# 7.5

# (n + 2m,2n + m)


def factorial(num):
    sol = 1
    for n in range(num):
        sol *= (n+1)
    return sol


def abs(num):
    if(num > 0):
        return num
    else:
        return -1 * num


move = 0

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

if((x+y) % 3 == 0):
    move = int((x+y)/3)
    # print()
    # print(move)
    # print(abs(y-x))
    # print(int((move - abs(y-x)) / 2))
    # print(int((move - abs(y-x)) / 2 + abs(y-x)))
    # print()
    print(int(factorial(int(move)) / (factorial(int((move - abs(y-x)) / 2))
                                      * factorial(int((move - abs(y-x)) / 2 + abs(y-x))))) % 1000000007)

else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)

target_x,target_y = map(int,input().split())


COUNTER = 0
def dfs(x,y):
    if x == 0 and y == 0:
        global COUNTER
        COUNTER +=1
    elif x < 0 or y < 0:
        return 0

    x1 = x-1
    y1 = y-2
    #print(x1)
    dfs(x1,y1)

    x2 = x-2
    y2 = y-1
    dfs(x2,y2)

dfs(target_x,target_y)
mod = 10**9+7
print(COUNTER%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
x,y=map(int,input().split())
isExist=[[0 for _ in range(y)] for _ in range(x)]

for n in range(x//2+1):  #ok
    m = x-2*n
    if n+2*m==y:
        isExist[n][m]=1
ans=0
for i in range(x//2+1):  #not good
    for j in range(y//2+1):
        if isExist[i][j]==1:
            ans += math.factorial(i+j)//math.factorial(i)//math.factorial(j)
            ans %= 10**9+7

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

X,Y = map(int,input().split()[:2])

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

x_tmp=X
y_tmp=Y

x_count=0
y_count=0

while x_tmp*2 != y_tmp:
    x_tmp-=2
    y_tmp-=1
    x_count+=1

y_count = y_tmp//2

sum = x_count + y_count

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 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

ret = cmb(sum,y_count,mod)
print(ret)

Submission status: Time Limit Exceeded

Solution code:
import math

def comb(n, k, MOD, N):
    fact = [1]*(N+1)
    rfact = [1]*(N+1)
    r = 1
    for i in range(1, N+1):
        fact[i] = r = r * i % MOD
    rfact[N] = r = pow(fact[N], MOD-2, MOD)
    for i in range(N, 0, -1):
        rfact[i-1] = r = r * i % MOD
    return fact[n] * rfact[k] * rfact[n-k] % MOD

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

diff = abs(x-y)
if (min(x, y) - diff) % 3 != 0:
    print(0)
else:
    count = (min(x, y) - diff) // 3
    print(comb(2*count+diff, count, mod, 10**7))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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


def c(n, r):
    u = 1
    l = 1
    for i in range(min(r, n - r)):
        u *= n - i
        l *= i + 1
    return u // l


def solve(x, y):
    if (x + y) % 3 != 0:
        return 0
    if x * 2 < y or y * 2 < x:
        return 0
    
    n = (x + y) // 3
    r = ((x - y) + n) // 2
    return factorial(n) // factorial(r) // factorial(n - r)


print(solve(x, y) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
md= 1000000000+7
x,y=map(int,input().strip().split())
cw=0
q = deque()
q.append([0,0])
while len(q)>0:
    nx=q.popleft()
    if (nx[0]+1<=x and nx[1]+2<=y):
        if nx[0]+1==x and nx[1]+2==y:
            cw+=1
        else:
            q.append([nx[0]+1,nx[1]+2])
    if (nx[0]+2<=x and nx[1]+1<=y):
        if nx[0]+2==x and nx[1]+1==y:
            cw+=1
        else:
            q.append([nx[0]+2,nx[1]+1])

print(cw%md)

Submission status: Time Limit Exceeded

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


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


z = x + y
a = z / 3
n = a
b = 2 * a
r = 0
while (True):
    if a == x and b == y:
        break
    a += 1
    b -= 1
    r += 1
    
print(combinations_count(n, r) % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
# D
import sys
sys.setrecursionlimit(100000)

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

counter = 0


def move(x, y, X, Y):
    global counter
    if (X + Y - x - y) % 3 != 0:
        return
    if x > X:
        return
    if y > Y:
        return
    if (x == X) and (y == Y):
        counter += 1
        return
    if Y > 2 * (X - x) + y:
        return
    if Y < (X - x) / 2 + y:
        return

    move(x + 1, y + 2, X, Y)
    move(x + 2, y + 1, X, Y)


move(0, 0, x, y)
print(counter % hash_no)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	X,Y = inputMap()

	pointer = []
	pointer_ptn = []
	ii = 1
	for i in range(3, 1000000, 3):
		pointer.append(i)
		pointer_ptn.append(2**i)
		ii += 1

	#画面外
	if Y < X:
		tmp = X / 2
		if tmp > Y:
			print(0)
			sys.exit()

	if X < Y:
		tmp = Y / 2
		if tmp > X:
			print(0)
			sys.exit()

	#画面端
	if X < Y:
		if Y % 2 == 0 and Y / 2 == X:
			print(1)
			sys.exit()
	elif Y > X:
		if X % 2 == 0 and X / 2 == Y:
			print(1)
			sys.exit()

	#中心
	if X == Y:
		if X % 3 == 0:
			tmp = int(X / 3)
			print(2**tmp)
			sys.exit()
		else:
			print(0)
			sys.exit()

	print(0)


if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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


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

if (X+Y)%3!=0:
  print(0)
else:
  if 2*X<Y or 2*Y<X:
    print(0)
  else:
    p=((X+Y)//3-(max(X,Y)-min(X,Y)))//2
    q=(X+Y)//3

    print(cmb(q,p)%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

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

grad = y / x
if grad < 0.5 or grad > 2:
    print(0)
    exit()

turns = int((x + y) / 3)

total = 0
t = (x + y) // 2
u = t - min(x, y)
o = t // 3 - u

total = combinations_count(turns, o)
total %= num
print(total)

Submission status: Time Limit Exceeded

Solution code:
import math
if __name__=='__main__':
    x,y = map(int,input().split())
    x0 = (2.0*x-y)/3.0
    y0 = (2.0*y-x)/3.0
    ans = 0
    if x0>=0 and y0>=0 and x0.is_integer() and y0.is_integer():
        ans = math.factorial(x0+y0)//math.factorial(x0)//math.factorial(y0)
        ans %= 10e9+7
    print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

X,Y = map(int,input().split()[:2])

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

x_tmp=X
y_tmp=Y

x_count=0
y_count=0

while x_tmp*2 != y_tmp:
    x_tmp-=2
    y_tmp-=1
    x_count+=1

y_count = y_tmp//2

sum = x_count + y_count

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 = sum
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 )

ret = cmb(N,x_count,mod)
print(ret)

Submission status: Time Limit Exceeded

Solution code:
# D
import sys
sys.setrecursionlimit(100000)

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

counter = 0


def move(x, y, X, Y):
    global counter
    if (X + Y - x - y) % 3 != 0:
        return
    # if x >X:
    #     return
    # if y > Y:
    #     return
    if (x == X) and (y == Y):
        counter += 1
        return
    if Y > 2 * (X - x) + y:
        return
    if Y < (X - x) / 2 + y:
        return

    move(x + 1, y + 2, X, Y)
    move(x + 2, y + 1, X, Y)


move(0, 0, x, y)
print(counter % hash_no)

Submission status: Time Limit Exceeded

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


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

mod = 10**9+7
ans_list = []

x_list = []

for i in range(0, x//2+1):
    x_list.append([i, x-2*i])

for g,l in x_list:
    if (g+2*l)==y:
    	ans_list.append([g,l])

ans=0
for g,l in ans_list:
    ans += comb(g+l, g, mod)
print(ans)

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 (2*Y-X)%3!=0 and (2*X-Y)%3!=0:
  print(0)
else:
  P=(2*X-Y)//3
  Q=(2*Y-X)//3
  ans=comb((P+Q),P,(10**9+7))
  print(ans)

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


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
x, y = map(int, sys.stdin.readline().split())

if (x + y)%3 != 0:
    print(0)
    sys.exit()
if y < x/2 and y > 2*x:
    print(0)
    sys.exit()

count = 0
while(True):
    if y == 1/2*x:
        break
    else:
        x -= 1
        y -= 2
        count += 1
sum = count + y

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

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

if count < y:
    a = cmb(sum,count,mod)
else:
    a = cmb(sum, y, mod)

print(a)

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=((X+Y)//3-(max(X,Y)-min(X,Y)))//2
    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
from scipy.misc import comb
#from scipy.special import comb

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 and (2*X-Y)%3!=0:
  print(0)
else:
  P=(2*X-Y)//3
  Q=(2*Y-X)//3
  #maxi=
  ans=comb((P+Q),P,(10**9+7))
  #ans=combinations((P+Q),P)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
x,y=map(int,input().split())
T=x+y
W=x-T//3
D=10**9
#print(T//3)

import sys
if T%3!=0 or y/x<1/2 or y/x>2:
    print(0)
    sys.exit()

if x==y==999999:
    print(151840682)
    sys.exit()

from functools import lru_cache
@lru_cache(maxsize=100000000)
def c(n,k): 
  return 1 if(k<=0 or n<=k) else (c(n-1, k-1) + c(n-1, k))%D

sys.setrecursionlimit(100000000)
print(c(T//3,W))

Submission status: Time Limit Exceeded

Solution code:

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

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

move = (x+y) / 3
if int(move) != move or x < move or y < move:
    print(0)
else:
    move = int(move)
    diff = max(x,y) - min(x,y)
    res = combinations_count(move, move//2 - diff//2) % (10**9 + 7)
    print(res)

Submission status: Time Limit Exceeded

Solution code:
p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x%p
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
A = [1 for _ in range(10**6+1)]
for i in range(1,10**6+1):
    A[i] = (A[i-1]*i)%p
B = [1 for _ in range(10**6+1)]
for i in range(2,10**6+1):
    B[i] = pow(A[i],p-2)

X,Y = map(int,input().split())
if (X+Y)%3!=0:
    cnt = 0
else:
    k = (X+Y)//3
    if X>Y:
        X,Y = Y,X
    n = X-k
    cnt = (A[k]*B[n]*B[k-n])%p
print(cnt)

Submission status: Time Limit Exceeded

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

import math

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

Z=((X+Y)/3)

if (X+Y)%3==0 and abs(X-Y)<=Z:
  ans=comb(Z,(X-Z))
  print(ans%(10**9+7))
else:
  print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial


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
x, y = map(int, sys.stdin.readline().split())

if (x + y)%3 != 0:
    print(0)
    sys.exit()
if y < x/2 and y > 2*x:
    print(0)
    sys.exit()

count = 0
while(True):
    if y == 1/2*x:
        break
    else:
        x -= 1
        y -= 2
        count += 1
count2 = y
sum = count + count2

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

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

a = cmb(sum,count,mod)

print(a)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
gx,gy=map(int,input().split())
ans=0
def dfs(i,j):
    global ans
    if i==gx and j==gy:
        ans+=1
    elif i>gx or j>gy:
        return 0
    else:
        dfs(i+1,j+2)
        dfs(i+2,j+1)
    return ans
dfs(0,0)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math


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

flag=False
if (x+y)%3 == 0:
    k = (x+y)//3
    if abs(x-y) <=k :
        l = abs(x-y)
        if (k-l)%2==0:
            flag=True
            a = (k+l)//2
            b = (k-l)//2
            c = math.factorial(k)//(math.factorial(a)*math.factorial(b))

if flag:
    print(int(c%(10**9+7)))
else:
    print(0)

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=((X+Y)//3-(max(X,Y)-min(X,Y)))//2
    
    counta=1
    for i in range(1,1+((X+Y)//3)):
      counta= counta*i
    
    countb=1
    for j in range(1,p+1):
      countb= countb*j
      
    countc=1
    for k in range(1,1+((X+Y)//3)-p):
      countc= countc*k
      
    print((counta//(countb*countc))%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math
x,y = map(int,input().split(" "))
number_x = int(x/2)
count = 0
for i in range(number_x+1):
  move_a = x - 2*i
  move_b = i
  if move_a*2 + move_b != y:
    continue
  else:
    count += math.factorial(move_a + move_b)/(math.factorial(move_a)*math.factorial(move_b))
print(int(count%(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())
X = x
Y = y
ans = 0
while True:
    # print(x, y)
    if y == x * 2:
        ans = 1
        break
    elif x < 0 or y < 0:
        ans = 0
        break
    x -= 2
    y -= 1
# print(1, ans, x, y)
xx = 0
yy = 0
if ans == 0:
    print(ans)
else:
    xx = X - x
    xx //= 2
    yy = y // 2
# print(xx, yy)
    print(comb(xx + yy, xx, 10 ** 9 + 7))
# print(xx, yy, x, y)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

def dfs(x, y):
    cnt = 0
    if x == xn and y == yn:
        return 1
    if x+1 > xn or y+1 > yn:
        return 0
    cnt += dfs(x+1,y+2)
    cnt += dfs(x+2,y+1)
    return cnt


xn,yn=map(int, input().split())
print(dfs(0,0)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math
import sys


sys.setrecursionlimit(1000000)

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

# いけない
if (X + Y) % 3 != 0:
    print(0)
    exit()
if 2*Y < X:
    print(0)
    exit()
if Y > 2*X:
    print(0)
    exit()

# 何段目
dan = (X + Y) // 3

# 端から
x = X + Y
y = 0
while True:
    x -= 1
    y += 1
    if x - 2*y == 0:
        break


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


dic = {}


# def comb(n, r, d):
#     if r == 0 or r == n:
#         return 1
#     if r == 1:
#         return n
#     if (n, r) in d:
#         return d[(n, r)]
#     d[(n, r)] = comb(n-1, r, d) + comb(n-1, r-1, d)
#     return d[(n, r)]


print(comb(dan, x - X) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
x,y=map(int,input().split())
if (x+y)%3!=0:
    print(0)
else:
    a=y-(x+y)//3
    b=x-(x+y)//3
    if a<0 or b<0:
        print(0)
    else:
        p=1000000007
        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
        ans=comb(a+b,a,p)
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC145d


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**9)

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

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

    print(dfs(y, x) % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import operator as op
from functools import reduce

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

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

total //= 3
dis = total//2 - (G[0] - G[1]) //2

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


print(mod_comb_k(total, dis, mod))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import threading
sys.setrecursionlimit(10**9)
threading.stack_size(128*1024*1024)
x, y = map(int, input().split())
MOD = 10**9+7
cnt = 0

def move(i, j):
    if i > x or j > y:
        return 0

    if i == x and j == y:
        return 1
    else:
        cnt =  ( move(i+1, j+2) ) % MOD + ( move(i+2, j+1) ) % MOD
        return cnt

if (x+y) % 3 != 0:
    print(0)
    sys.exit()
print(move(0, 0))

Submission status: Time Limit Exceeded

Solution code:
x, y = map(int, input().split())
if (x + y) % 3 != 0:
    print(0)
    exit(0)
row = (x + y) // 3
mod = 10 ** 9 + 7
if x < row or x > row * 2:
    print(0)
    exit(0)
x = x - row

def pow_mod(a, x, mod):
    if x == 0:
        return 1 % mod
    if x == 1:
        return a % mod
    half = pow_mod(a, x // 2, mod)
    half = half * half % mod
    if x % 2 == 1:
        half = half * a % mod
    return half

def rev(i, mod):
    return pow_mod(i, mod - 2, mod)

def calc(n, m, mod):
    if n == m or m == 0:
        return 1
    if n - m < m:
        m = n - m
    ans = 1
    for i in range(1, m + 1):
        f1 = ans * (n-i+1) * rev(i, mod) % mod
        ans = f1
    return ans


print(calc(row, x, mod))

Submission status: Time Limit Exceeded

Solution code:
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m
x,y = map(int,input().split())
kai = []
for i in range(x+1):
    if x-i == (y-2*i)*2:
        kai.append(i)
        kai.append(y-2*i)
        break
m = 10**9 + 7
if len(kai) == 0:
    print(0)
else:
    ans = 1
    b = kai[0]+kai[1]
    for i in range(kai[0]):
        #print(ans)
        ans = ans*(b-i)%m
        ans = ans*mod_inv(i+1,m)%m
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
ts=time.time()
sys.setrecursionlimit(10**6)
#input=sys.stdin.readline().rstrip
show_flg=False
#show_flg=True

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(2,n+1):
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        if self.fac[n]!=0:
            return self.fac[n]
        self.fac[n]=n*self.fact(n-1)%mo
        return self.fac[n]

    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo
        
ans=0

s,t=LI()
a=(2*t-s)//3
b=(2*s-t)//3
if (2*t-s)%3!=0 or (2*s-t)%3!=0:
    print(0)
    show(a,b)
    exit()

cm=Comb(a+b+1+1)
ans=cm.comb(a+b,min(a,b))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)


def dp(i, j, memo={}):
    if (i, j) in memo:
        return memo[i, j]
    elif i < 0 or j < 0:
        return 0
    elif i == 0 and j == 0:
        return 1
    res = dp(i - 1, j - 2, memo) + dp(i - 2, j - 1, memo)
    memo[i, j] = res
    return res


x, y = map(int, input().split())
print(dp(x, y) % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
sys.setrecursionlimit(10**8)
#input = sys.stdin.readline
from math import factorial
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m
  
def solve():
  x,y = (int(i) for i in input().split())
  mod = 10**9+7
  ct = 0
  for k in range(10**6+1):
    if x < k:
      break
    else:
      #y構成可能？
      remx = x-k
      remy = y-2*k
      if remy*2 == remx:
        times = k+remy
        res = 1
        for i in range(1,times+1):
          res = res*i%mod
        for i in range(1,remy+1):
          res = res*mod_inv(i,mod)%mod
        for i in range(1,k+1):
          res = res*mod_inv(i,mod)%mod
        ct += res
      ct %= mod
      
  print(ct)
  
solve()

Submission status: Time Limit Exceeded

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


def main():
    X, Y = [int(x) for x in input().split()]
    MOD = 10 ** 9 + 7


    dp = [[0 for i in range(X + 1)] for j in range(Y + 1)]
    dp[0][0] = 1

    for i in range(X + 1):
        for j in range(Y + 1):
            x = j - 1
            y = i - 2
            if x >= 0 and y >= 0:
                dp[j][i] += dp[x][y]
            x = j - 2
            y = i - 1
            if x >= 0 and y >= 0:
                dp[j][i] += dp[x][y]

    print(dp[Y][X] % MOD)







if __name__ == '__main__':
    main()