Problem:


Score : 400 points

Problem Statement

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

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

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

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

Constraints

1 \leq X \leq 10^6

1 \leq Y \leq 10^6

All values in input are integers.

Input

Input is given from Standard Input in the following format:

X Y

Output

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

Sample Input 1

3 3

Sample Output 1

2

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

Sample Input 2

2 2

Sample Output 2

0

The knight cannot reach (2,2).

Sample Input 3

999999 999999

Sample Output 3

151840682

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



Sample input:
3 3


Sample output:
2

Submission status: Wrong Answer

Solution code:

import sys
x,y=map(int,input().split())
n=(x+y)//3
a,b=0,0
if n*3!=x+y:
	print(0)
	sys.exit()
for i in range(n+1):
	#print(i*2+(n-i),i+(n-i)*2)
	if i*2+(n-i)==x and i+(n-i)*2==y:
		a,b=i,n-i
#a:x+1 y+2
#b:x+2 y+1

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
print(cmb(a+b,a)%(10**9+7))

Submission status: Wrong Answer

Solution code:
from sys import stdin


def input():
    return stdin.readline()[:-1]


def intput():
    return int(input())


def sinput():
    return input().split()


def intsput():
    return map(int, sinput())


mod = 10 ** 9 + 7
def ncr(n, r):
    x = 1
    for i in range(n, r, -1):
        x *= i
        x %= mod
    for i in range(r, 1, -1):
        x *= pow(i, mod - 2, mod)
        x %= mod
    return x

x , y = intsput()

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

if a >= 0 and b >= 0 and a + 2 * b == x and 2 * a + b == y:
    print(ncr(a + b, b))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def com(com_n, com_r):
        return fac[com_n] * inv[com_r] * inv[com_n - com_r] % md

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

    # combinationの準備
    md = 10 ** 9 + 7
    n_max = 10 ** 6
    fac = [1]
    inv = [1] * (n_max + 1)
    k_fac_inv = 1
    for i in range(1, n_max + 1):
        k_fac_inv = k_fac_inv * i % md
        fac.append(k_fac_inv)
    k_fac_inv = pow(k_fac_inv, md - 2, md)
    for i in range(n_max, 1, -1):
        inv[i] = k_fac_inv
        k_fac_inv = k_fac_inv * i % md

    gs, gt = x + y, x - y
    if gs % 3:
        print(0)
        exit()
    step = gs // 3
    if (gt + step) % 2:
        print(0)
        exit()
    n_plus = (gt + step) // 2
    print(com(step, n_plus))

main()

Submission status: Wrong Answer

Solution code:
#%%
x, y = map(int, input().split())
flag = True
a, b = 0, 0
if x > y:
    a += x - y
    x -= (x - y) * 2
    y -= (x - y)
elif y > x:
    a += y - x
    y -= (y - x) * 2
    x -= (y - x)
else:
    pass

if x % 3 != 0:
    flag = False
if x < 0 :
    flag = False
#print(a, b)
a += (x) //3
b += (x) //3

inf = 10 ** 9 + 7

c = 1
d = 1
for i in range(1, a+b+1):
    c *= i
    c %= inf
for i in range(1, a+1):
    d *= i
    d %= inf
for i in range(1, b+1):
    d *= i
    d %= inf

#print(a, b)
#print(c, d)
ans = c * pow(d, inf-2, inf)
ans %= inf

if flag:
    print(ans)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
from sys import stdin


def input():
    return stdin.readline()[:-1]


def intput():
    return int(input())


def sinput():
    return input().split()


def intsput():
    return map(int, sinput())


mod = 10 ** 9 + 7
def ncr(n, r):
    x = 1
    for i in range(n, r, -1):
        x *= i
        x %= mod
    for i in range(r, 1, -1):
        x *= pow(i, mod - 2, mod)
        x %= mod
    return x

x , y = intsput()

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

if a + 2 * b == x and 2 * a + b == y:
    print(ncr(a + b, b))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
inpl = lambda: list(map(int,input().split()))
def inv_mod(a, p):
    p = abs(p)
    a %= p
    stack = []
    p0 = p
    while a > 1:
        d, a, p = p//a, p%a, a
        stack.append(d)
    x, y = 1, 0
    while stack:
        d = stack.pop()
        x, y = y-d*x, x
    return x % p0

def comb_mod(n,k,p):
    ans = 1
    k = min(k,n-k)
    for i in range(k):
        ans = ans * (n-i) * inv_mod(k-i,p) % p
    return ans

MOD = 10**9+7
X, Y = inpl()
if (X+Y) % 3:
    print(0)
    exit()
N = (X+Y)//3
X -= N
Y -= N
Z = X + Y
print(comb_mod(Z,X,MOD))

Submission status: Wrong Answer

Solution code:
x,y = map(int,input().split())
if (x + y) % 3 != 0:
    print(0)
    exit()
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

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

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

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
            result %= (10 ** 9 + 7)

    return result

num = (x + y) // 3
print(cmb(num,min(x,y)-num)%(10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
class Combination:
    '''MOD上の
    計算量：階乗・逆元テーブルの作成O(N)
    nCkを求めるO(1)'''

    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [pow(self.fact[i], MOD - 2, MOD) for i in range(n + 1)]
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD



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

if (x+y) % 3 != 0:
    print(0)
    exit()
    
tmp = (x+y) // 3
k = abs(x-y)
if tmp % 2 == 1:
    if tmp < k:
        print(0)
    else:
        print(comb.combination(tmp, k))
else:
    k = abs(tmp//2 - k)
    if tmp < k:
        print(0)
    else:
        print(comb.combination(tmp, k))

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7         # 問題に合わせて適宜書き換え
list_size = 10**6+100  # 問題に合わせて適宜書き換え

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = ((f_list[i] * (i+2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(-2, -list_size-1, -1):
	f_r_list[i] = ((f_r_list[i+1] * (list_size + 2 + i)) % MOD)

def comb(n,r):
    if r == 0:
        return 1
    return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD

X,Y = map(int,input().split())
if (X+Y) % 3 != 0:
    print(0)
    exit()
N = (X+Y)//3
X -= N
Y -= N
if X < 0 or Y < 0:
    print(0)
    exit()
print(comb(N,X))

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7         # 問題に合わせて適宜書き換え
list_size = 10**6+100  # 問題に合わせて適宜書き換え

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = ((f_list[i] * (i+2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(-2, -list_size-1, -1):
	f_r_list[i] = ((f_r_list[i+1] * (list_size + 2 + i)) % MOD)

def comb(n,r):
    if r == 0:
        return 1
    return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD

X,Y = map(int,input().split())
N = (X+Y)//3
X -= N
print(comb(N,X))

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x)
        else:
            return ModInt(self.x + other)

    __radd__ = __add__
        
    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x)
        else:
            return ModInt(self.x - other)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x)
        else:
            return ModInt(other - self.x)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x)
        else:
            return ModInt(self.x * other)

    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, mod-2,mod))
        else:
            return ModInt(self.x * pow(other, mod - 2, mod))
            
    def __rtruediv(self, other):
        if isinstance(other, self):
            return ModInt(other * pow(self.x, mod - 2, mod))
        else:
            return ModInt(other.x * pow(self.x, mod - 2, mod))
            

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, mod))
        else:
            return ModInt(pow(self.x, other, mod))
            

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))
class BigCombination(object):

    def __init__(self, mod: int=10**9+7, max_n: int=2*(10**6)):
        fac, inv=[1], []
        fac_append, inv_append=fac.append, inv.append

        for i in range(1, max_n+1):
            fac_append(fac[-1] * i % mod)

        inv_append(pow(fac[-1], mod-2, mod))

        for i in range(max_n, 0, -1):
            inv_append(inv[-1] * i % mod)

        self.mod, self.factorial, self.inverse=mod, fac, inv[::-1]

    def get_combination(self, n, r):
        if n < r:
            return 0
        return self.factorial[n] * self.inverse[r] * self.inverse[n-r] % self.mod

    def get_permutation(self, n, r):
        if n < r:
            return 0
        return self.factorial[n] * self.inverse[n-r] % self.mod
def main():
    X,Y = MI()
    if (X+Y)%3 != 0:
        print(0)
        return 
    S = X+Y
    X-=S//3
    Y-=S//3
    B = BigCombination()
    ans = B.get_combination(X+Y,X)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x)
        else:
            return ModInt(self.x + other)

    __radd__ = __add__
        
    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x)
        else:
            return ModInt(self.x - other)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x)
        else:
            return ModInt(other - self.x)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x)
        else:
            return ModInt(self.x * other)

    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, mod-2,mod))
        else:
            return ModInt(self.x * pow(other, mod - 2, mod))
            
    def __rtruediv(self, other):
        if isinstance(other, self):
            return ModInt(other * pow(self.x, mod - 2, mod))
        else:
            return ModInt(other.x * pow(self.x, mod - 2, mod))
            

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, mod))
        else:
            return ModInt(pow(self.x, other, mod))
            

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))
class BigCombination(object):

    def __init__(self, mod: int=10**9+7, max_n: int=10**6):
        fac, inv=[1], []
        fac_append, inv_append=fac.append, inv.append

        for i in range(1, max_n+1):
            fac_append(fac[-1] * i % mod)

        inv_append(pow(fac[-1], mod-2, mod))

        for i in range(max_n, 0, -1):
            inv_append(inv[-1] * i % mod)

        self.mod, self.factorial, self.inverse=mod, fac, inv[::-1]

    def get_combination(self, n, r):
        if n < r:
            return 0
        return self.factorial[n] * self.inverse[r] * self.inverse[n-r] % self.mod

    def get_permutation(self, n, r):
        if n < r:
            return 0
        return self.factorial[n] * self.inverse[n-r] % self.mod
def main():
    X,Y = MI()
    if (X+Y)%3 != 0:
        print(0)
        return 
    S = X+Y
    X-=S//3
    Y-=S//3
    B = BigCombination()
    ans = B.get_combination(X+Y,X)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

X, Y = [int(n) for n in input().split()]

if (X + Y) % 3 != 0:
    ans = 0
else:
    m = int((2*X-Y) / 3)
    n = int((2*Y-X) / 3) 

    if m < 0 or n < 0:
        ans = 0
    else:
        ans = math.comb(m+n, n)

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

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**9
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

X, Y = map(int,input().split())
a=(-X+2*Y)/3
b=(2*X-Y)/3
if a.is_integer()==False or b.is_integer()==False:
    print(0)
else:
    print(cmb(int(a+b),int(b),mod))

Submission status: Time Limit Exceeded

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

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

N=a+b

ans=0

#print(a,b,N)


if (X+Y)%3!=0 or a<0 or b<0:
    ans=0
elif a==0 or b==0:
    ans=1
else:
    NN=1
    aa=1
    for i in range(1,a+1):
        NN*=N+1-i
        aa*=i
    ans=NN//aa

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

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import lru_cache
from operator import mul
from functools import reduce

@lru_cache(maxsize=None)
def for_factorial(n):
    val = 1
    for i in range(2, n + 1):
        val = (val * i)
    return val



x, y = map(int, input().split())
mod = 1000000007
cnt = (x + y) // 3
if (x + y) % 3 != 0:
    print(0)
    exit()
m = min(x, y)
num_2 = m - cnt
num_1 = cnt - num_2
#print(cnt, num_1, num_2)
f_1 = for_factorial(num_1)
f_2 = for_factorial(num_2)
ans = for_factorial(cnt)
#print(ans, f_1, f_2)
f = f_1 * f_2
ans //= f
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = list(map(int,input().split()))
X = a[0]
Y = a[1]
import math
from scipy.special import comb

if (X + Y)%3 == 1:
  print(0)
if (X + Y)%3 == 2:
  print(0)
if (X + Y)%3 == 0:
  n = 2/3*X - 1/3*Y  
  m = -1/3*X + 2/3*Y
  if n < 0:
    print(0)
  elif m < 0:
    print(0)
  else:
    k = n+m
    L = comb(k, n, exact=True)
    print(int(L%(10**9 + 7)))

Submission status: Time Limit Exceeded

Solution code:
X, Y = map(int, input().split())
dp = [[0] * (X + 3) for _ in range(Y + 3)]
mod = 10**9 + 7
dp[0][0] = 1
dp[1][2] = 1
dp[2][1] = 1

for i in range(2, Y+1):
    end = min(X+1, i*2+1)
    for j in range(i-1, end):
        if i-2 > 0 and j-2 > 0:
            dp[i][j] = (dp[i-1][j-2] + dp[i-2][j-1]) % mod

print(dp[Y][X])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
x,y = map(int,input().split())
mod = 10**9+7

def dfs(i,j):
    if i == 0 and j==0:
        return 1
    a = b = 0
    if i-2 >= 0 and j-1 >= 0:
        a = dfs(i-2,j-1)
    if i-1 >= 0 and j-2 >= 0:
        b = dfs(i-1,j-2)
    return (a+b)%mod

print(dfs(y,x))

Submission status: Time Limit Exceeded

Solution code:
x,y = map(int,input().split())
if (2*x - y) % 3 != 0 or (2*y-x) % 3 != 0 or 2 * min(x,y) < max(x,y):
    print(0)
    exit()

mod = 10**9 + 7
n = (x+y) // 3
a = (max(x,y)*2 - min(x,y)) // 3

fact = [1]
finv = [1]
for i in range(1, n+1):
    fact += [(fact[i-1] * i) % mod]
    finv += [pow(fact[i], mod-2, mod)]
print((fact[n]*finv[a]*finv[n-a]) % mod)

Submission status: Time Limit Exceeded

Solution code:
# 73

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

a = 2*y - x
b = 2*x - y

fac_l = [0] * (int((a + b) / 3) + 1)
inv_l = [0] * (int((a + b) / 3) + 1)
finv_l = [0] * (int((a + b) / 3) + 1)


def com_init():
    fac_l[1] = 1
    inv_l[0] = 1
    inv_l[1] = 1
    finv_l[0] = 1
    finv_l[1] = 1
    for i in range(2, a+b+1):
        fac_l[i] = (fac_l[i-1] * i) % MOD
        inv_l[i] = MOD - (inv_l[MOD % i] * int(MOD / i)) % MOD
        finv_l[i] = finv_l[i-1] * inv_l[i]


def ncr(n, r):
    return (((fac_l[n] * finv_l[r]) % MOD) * finv_l[n-r]) % MOD


if a % 3 != 0 or b % 3 != 0:
    print("0")
else:
    a = int(a/3)
    b = int(b/3)

    com_init()
    print(ncr(a+b, a))

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def cmb(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()
a = 2*x - y
b = 2*y - x

if a >= 0 and b >= 0 and a % 3 == 0 and b % 3 == 0:
    a //= 3
    b //= 3
    ans = cmb(a+b, a, 10**9+7)
else:
    ans = 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def cmb(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()
a = 2*x - y
b = 2*y - x

if a >= 0 and b >= 0 and a % 3 == 0 and b % 3 == 0:
    a //= 3
    b //= 3
    ans = cmb(a+b, a, 10**9+7)
else:
    ans = 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc145/tasks/abc145_d
import math
X, Y = list(map(int, input().split()))

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


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

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

MOD = 10 ** 9 + 7
result = math.factorial(n + m) * pow(math.factorial(n), -1,
                                     MOD) * pow(math.factorial(m), -1, MOD) % MOD
print(result)

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7

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

if not (X+Y) % 3:
    m = (2*X - Y)//3
    n = (2*Y - X)//3
    if n >= 0 and m >= 0:
        print(comb(n+m,min(n,m)) % MOD)
    else:
        print(0)
else:
    print(0)

Submission status: Time Limit Exceeded

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

a = max(x,y)
b = min(x,y)
cnt = 0

while a -b-100 >100:
    a -=200
    b -=100
    cnt +=100


while a != b:
    a -= 2
    b -= 1
    cnt +=1

    if a<0 or b <0:
        print(0)
        exit()
if a%3 != 0:
    print(0)
    exit()
else:
    c = a//3

n = (math.factorial(2*c+cnt)%m)*(pow(math.factorial(c+cnt),m-2,m))*(pow(math.factorial(c),m-2,m))
print(n%m)

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())
s=2*x-y
t=2*y-x
if s%3!=0 or s<0 or t%3!=0 or t<0:
  print(0)
else:
  print(comb((s+t)//3,s//3,1000000007))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
X,Y = map(int,input().split())
ans=0
mod=10**9+7
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  
for a in range(Y//2+1):
  b = Y-2*a
  if a+2*b==X:
    ans+=combinations_count(a+b,a)%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

if (x+y) % 3 != 0:
  print(0)
else:
  roots = 0
  itr = int((x+y)/3)
  for seq in itertools.product(['u', 'l'], repeat=itr):
    n_u = seq.count('u')
    _x = n_u + 2 * (itr - n_u)
#    _y = n_u * 2 + (itr - n_u)

    if _x == x:
        roots += 1
      
#    if (_x == x) & (_y == y):
#        roots += 1
        
  print(roots % (pow(10, 9)+7))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

if (x+y) % 3 != 0:
  print(0)
else:
  roots = 0
  itr = int((x+y)/3)
  for seq in itertools.product(['u', 'l'], repeat=itr):
    _x = 0
    _y = 0

    for v in seq:
      if v == 'u':
        _x += 1
        _y += 2
      else:
        _x += 2
        _y += 1
      
      if (_x > x) | (_y > y):
        continue

    if (_x == x) & (_y == y):
      roots += 1

  print(roots % (pow(10, 9)+7))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

if (x+y) % 3 != 0:
  print(0)
else:
  roots = 0
  
  for seq in itertools.product(['u', 'l'], repeat=int((x+y)/3)):
    _x = 0
    _y = 0
    
    for v in seq:
      if v == 'u':
        _x += 1
        _y += 2
      else:
        _x += 2
        _y += 1

    if (_x == x) & (_y == y):
      roots += 1

  print(roots % (pow(10, 9)+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 組合せnCr
def combinations_count(n, r):
    if n < r:
        return 0
    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

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]



# ここから書き始める
x, y = map(int, input().split())
ans = 0
for i in range(x + 1):
    cnt1 = i
    if (x - cnt1) % 2 != 0 or y - 2 * cnt1 != (x - cnt1) // 2:
        continue
    cnt2 = (x - cnt1) // 2
    ans += combinations_count(cnt1 + cnt2, cnt1)
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
x,y = map(int,input().split())
mod = 10**9+7
if (2*x-y)%3!=0 and (2*y-x)!=0:
  print(0)
  exit()
n = (2*x-y)//3
m = (2*y-x)//3
#n+mCm
if n==0 or m==0:
  print(1)
  exit()
def ka(x):
  a = 1
  while x!=1:
    a *= x
    x -= 1
    a%= mod
  return a

ans = (ka(n+m)*pow(ka(m),mod-2,mod)%mod)*(pow(ka(n),mod-2,mod))%mod
print(ans)