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:
# -*- coding: utf-8 -*-
a, b= map(int, input().split())

t = [a,b]

r = 0
t_r = []
for i in range(int(10**6/2)):

    l = [i, i*2]

    if l[0] > t[0] or  l[1] > t[1]:
        break

    for j in range(int(10**6/2)):

        l2 = [i + j*2, i*2 + j]
        if l2[0] > t[0] or  l2[1] > t[1]:
            break

        if l2 == t:
            t_r.append([i,j])
            break



for l in t_r:
    r += l[0] + l[1]
print(r)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce
import sys
def f(n,r):
  r = min(n-r,r)
  if r == 0: 
    return 1
  else:
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
x, y= map(int, input().split())
a=min(x,y)
b=max(x,y)
if b-a>a:
  print(0)
  exit()
else:
  if (2*a-b)%3!=0:
    print(0)
    exit()
  m=int((2*a-b)/3)
  print(f(a-m,m))

Submission status: Time Limit Exceeded

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

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

if n.is_integer() and m.is_integer() and n >= 0 and m >= 0:
  n = int(n)
  m = int(m)
  ans = int(math.factorial(n+m)//(math.factorial(n)*math.factorial(m)))
  ans = int(ans%(10**9+7))
  print(ans)
else:
  print(0)

Submission status: Time Limit Exceeded

Solution code:
class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv


def solve(a, b):
    n = a + b
    r = min(a, b)
    comb = Combination(10000000)
    return comb(n, r)


def main(x, y):
    if (2 * x - y) % 3 != 0 or (2 * y - x) % 3 != 0:
        return 0
    a = (2 * x - y) // 3
    b = (2 * y - x) // 3
    return solve(a, b)


if __name__ == '__main__':
    x, y = map(int, input().split())
    print(main(x, y))

Submission status: Time Limit Exceeded

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

if 2*x-y>=0 and 2*y-x>=0 and x%3==-y%3:
    n=(2*x-y)//3
    m=(2*y-x)//3
    ans = math.factorial(m+n)//math.factorial(m)
    ans //= math.factorial(n)
    ans %= 10**9+7
else:
    ans=0
print(ans)

Submission status: Time Limit Exceeded

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

def co (i, j):
  if i == 0 or j == 0:
    return 1
  else:
    return (co(i-1, j) + co(i, j-1)) % (10**9+7) 

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

ans = 0

if (x + y) % 3 != 0:
  ans = 0
else:
  mp = (x + y) // 3
  if min(x, y) < mp:
    ans = 0
  else:
    xi = x - mp
    yi = y - mp
    ans = co(xi, yi)

print(ans)

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())
ans = 0
mod = 10 ** 9 + 7
if X > Y:
    X, Y = Y, X
##Yのほうが大きいとして考える
if not (X + Y) % 3 == 0 or Y > 2 * X:
    ans = 0
else:
    n = (X + Y) // 3
    d = Y - X
    a = 2*n - X
    ans = comb(n, a, mod)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC145d


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7-1)

    x, y = map(int, input().split())
    #dp = [[-1] * (x + 1) for _ in range(y + 1)]
    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 i > y or j > x:
            return 0
        if x - j > (y - i) * 2:
            return 0
        if y - i > (x - j) * 2:
            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][j] != -1:
        #    return dp[i][j]
        #dp[i][j] = (dfs(i - 1, j - 2) + dfs(i - 2, j - 1)) % MOD
        # return dp[i][j]

    for i in range(20, 0, -1):
        if 3 ** i > min(x, y):
            continue
        #print(y//(3**i), x//(3**i))
        dfs(y//(3**i), x//(3**i))
    print(dfs(y, x) % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

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

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

x_tmp=X+1
y_tmp=Y+2

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 - 1

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,x_count,mod)
print(ret)

Submission status: Time Limit Exceeded

Solution code:
X,Y = list(map(int,input().rstrip().split()))
    
if (2*Y-X)%3 == 0:
    a = (2*Y-X)//3
    b = Y-2*a

    a_kaijo = 1
    for i in range(1,a+1):
        a_kaijo *= i
    b_kaijo = 1
    for i in range(1,b+1):
        b_kaijo *= i
    total_kaijo = 1
    for i in range(1,a+b+1):
        total_kaijo *= i
    print(total_kaijo//(a_kaijo*b_kaijo))
    
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
a, b= map(int, input().split())

t = [a,b]

r = 0
t_r = []
for i in range(int(10**6/2)):

    l = [i, i*2]

    if l[0] > t[0] or  l[1] > t[1]:
        break

    for j in range(int(10**6/2)):

        l2 = [i + j*2, i*2 + j]
        if l2[0] > t[0] or  l2[1] > t[1]:
            break

        if l2 == t:
            t_r.append([i,j])



for l in t_r:
    r += l[0] + l[1]
print(r)

Submission status: Time Limit Exceeded

Solution code:
x,y=map(int,input().split())
cnt=0
dp=[[0 for i in range(x+1)]for i in range(2)]
a=10**9+7
if x>1:
    dp[1][2]=1
if y>1:
    dp[0][1]=1

for i in range(y+1):
    if i<3:
        continue
    for j in range(x,-1,-1):
        if i%2==0:
            if dp[1][j-2]!=0 or dp[0][j-1]!=0:
                dp[0][j]=(dp[1][j-2]+dp[0][j-1])%a
            else:
                dp[0][j]=0
                
        else:
            if dp[0][j-2]!=0 or dp[1][j-1]!=0:
                dp[1][j]=(dp[0][j-2]+dp[1][j-1])%a
            else:
                dp[1][j]=0
if y%2==0:
    print(dp[0][x])
else:
    print(dp[1][x])

Submission status: Time Limit Exceeded

Solution code:
x,y=map(int,input().split())
X=(2/3)*x-(1/3)*y
Y=-(1/3)+(2/3)*y
if X<0 or Y<0 :
  print(0)
elif (x%3==0 and y%3==0) or (x%3==1 and y%3==2) or (x%3==2 and y%3==1):
  X=int(X)
  Y=int(Y)
  Xkai=1
  Ykai=1
  XYkai=1
  for i in range(1,X+1):
    Xkai=(Xkai*i)%(10**9+7)
  for i in range(1,Y+1):
    Ykai=(Ykai*i)%(10**9+7)
  for i in range(1,X+Y+1):
    XYkai*=(XYkai*i)%(10**9+7)
  C=XYkai/(Xkai*Ykai)
  D=C%(10**9+7)	
  print(int(D))
else:
  print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys


def power_func(a, b, p):
    if b == 0:
        return 1
    if b % 2 == 0:
        d = power_func(a, b//2, p)
        return d*d % p
    if b % 2 == 1:
        return (a*power_func(a, b-1, p)) % p
    
    
def comb(n, k, p):
    from math import factorial
    if n < 0 or k < 0 or n < k:
        return 0
    if n == 0 or k == 0:
        return 1
    a = factorial(n) % p
    b = factorial(k) % p
    c = factorial(n-k) % p
    return (a*power_func(b, p-2, p)*power_func(c, p-2, p)) % p


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

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

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# n+2m=i
# 2n+m=j
# (4n+2m=2j)
# n=(2j-i)/3
# m=(2i-j)/3
# n+m C n (n+m)!/n!/m!

MOD = 10**9+7
MAX = (10**6)*2+5
fac = [0]*MAX
inv = [0]*MAX
finv = [0]*MAX
def COMinit():
    fac[0]=1
    fac[1]=1
    finv[0]=1
    finv[1]=1
    inv[1]=1
    for i in range(2,MAX):
        fac[i] = fac[i-1]*i%MOD
        inv[i] = MOD - inv[MOD%i]*(MOD//i)%MOD
        finv[i] = finv[i-1]*inv[i]%MOD
def COM(n,k):
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD

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

Submission status: Time Limit Exceeded

Solution code:
import math
X,Y = list(map(int, input().split()))
cnts = [0,0]
while X>0 and Y>0:
    if X <= Y:
        cnts[1] += 1
        X -= 1
        Y -= 2
    else:
        cnts[0] += 1
        X -= 2
        Y -= 1
        
if X == 0 and Y == 0:
    i = cnts[0]
    j = cnts[1]
    print(math.factorial(i+j)//(math.factorial(i)*math.factorial(j)) % (10**9 + 7))
else:
    print(0)

Submission status: Time Limit Exceeded

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

if (2*x-y)%3 != 0 or (-x+2*y)%3 != 0:
  print(0)
  exit()
  
a = ((2*x-y)//3)%mod
b = ((-x+2*y)//3)%mod


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,min(a,b))%mod)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(100000)

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


x, y = map(int, input().split())
# (2n+m) + (n+2m) = (x,y) が入るパターンを配列化
ptn = []
count = 0

# 配列総当たり
for n in range((x // 2) + 1):
    m = x - 2 * n
    if(y == n + 2 * m):
            ptn.append([m, n])

for cl in ptn:
    if(cl[0] > cl[1]):
        count += cmb(cl[0] + 1, cl[1])
    else:
        count += cmb(cl[1] + 1, cl[0])

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

Submission status: Time Limit Exceeded

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

x,y= (int(_) for _ in input().split()) 
if (x+y)%3!=0:
    print(0)
    sys.exit()
else:
    n=(x+y)/3
    n=int(n)
    if x<n or y<n:
         print(0)
         sys.exit()
    else:
        x=x-n
        y=y-n
        ans=(combinations_count(x+y,x))
        print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from math import factorial
def main():
  x, y = map(int, input().split())
  a = (-x+2*y)/3
  b = (2*x-y)/3
  if a == int(a) and b ==int(b) and a >= 0 and b >= 0:
    a = int(a)
    b = int(b)
    z = (10**9+7)
    l = (int(factorial(a+b)))
    m = int(factorial(a))
    n = int(factorial(b))
    print((l//(m*n))%z)
  else:
    print(0)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

X,Y = map(int,input().split()[: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,x_count,mod)
print(ret)

Submission status: Time Limit Exceeded

Solution code:
import math

def main():
    # 計算しやすくするため、必ずX目標を大きくする
    X, Y= [int(x) for x in input().split()]
    if X < Y:
        X, Y = Y, X
    
    # 移動回数
    temp = X + Y
    if temp % 3 != 0:
        print(0)
        return
    
    count = temp // 3

    # Y軸が移動回数よりも小さい場合、絶対に移動できない
    if Y < count:
        print(0)
        return
    diff = abs(X - count * 2)
    a = count - diff
    b = diff
    ans = math.factorial(a + b) // math.factorial(a) // math.factorial(b)
    print(ans % (10**9 + 7))

if __name__ == "__main__":
    # print(timeit.timeit(lambda: main(), number=1))
    main()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())

if (2 * n - m < 0) or ((2 * n - m) % 3) or (2 * m - n < 0) or ((2 * m - n) % 3) :
    print(0);
    exit();
    
y = (2 * n - m) // 3;
x = (2 * m - n) // 3;

ans = 1;
for i in range(max(x, y) + 1, x + y + 1) :
    ans *= i;
for i in range(1, min(x, y) + 1) :
    ans = ans // i;
print(ans % (1000000007));

Submission status: Time Limit Exceeded

Solution code:
import math

a,b=map(int, input().split())
if (a+b)%3 != 0:
  print(0)
  exit()
tempA, tempB =a,b
right=0
left=0
while tempA+tempB != 0:
  if tempA < 0 or tempB <0:
    print(0)
    exit()
  elif tempA >= tempB:
    tempA -= 2
    tempB -= 1
    right+=1
    #print("R")
  else:
    tempB -= 2
    tempA -= 1
    left+=1
    #print("L")

#print(right, left)
ans = math.factorial(right+left)/(math.factorial(right)*math.factorial(left))

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

Submission status: Time Limit Exceeded

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

x, y = sorted(pos)

num_twos = x // 2
rem = x % 2

solution = 0

m = 10**9 + 7 - 2


def ncr(n, r):
    return factorial(n) * factorial(r)**(m) * factorial(n-r)**(m)


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

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

solution = ncr(num_twos + rem, rem)

print(int(solution))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000)

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

def f(x, y):
    if x==1 and y==2:
        return 1
    elif x==2 and y==1:
        return 1
    elif x > 2*y or y > 2*x:
        return 0
    elif x > 0 and y > 0:
        return (f(x-1, y-2) + f(x-2, y-1)) % (10 ** 9 + 7)
    else:
        return 0

print(f(X, Y))

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:
from scipy.misc import comb

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
    npath = comb(n1+n2, n1, exact=True)
    print(npath % (10**9+7))

Submission status: Time Limit Exceeded

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

if (2*x-y)%3 != 0 or (-x+2*y)%3 != 0:
  print(0)
  exit()
  
a = ((2*x-y)//3)%mod
b = ((-x+2*y)//3)%mod


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)%mod)

Submission status: Time Limit Exceeded

Solution code:
import math

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

movableFlag = False

for x in range(X):
	y = X-x*2
	if x*2+y*1==X and x*1+y*2==Y:
		movableFlag = True
		break
	
if movableFlag:
	if x==0 or y==0:
		print(1)
	else:
		print(math.factorial(X-1) // (math.factorial(x) // math.factorial((X-1)-x)))
else:
	print(0)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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

def modinv(a, mod):
    return modpow(a, mod-2, mod)

mod = int(1e+9 + 7)

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

X2 = 2*X - Y
Y2 = -X + 2*Y

if X2 < 0:
    print "0"
    exit()
elif Y2 < 0:
    print "0"
    exit()

if X2%3 != 0:
    print "0"
    exit()
elif Y2%3 != 0:
    print "0"
    exit()

X2 = X2/3
Y2 = Y2/3

ans = 1

n = X2+Y2
m = Y2

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

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


print ans

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb
x,y = (int(z) for z in input().split())
s = 0
d = 1e+9 + 7
br = False
alim = min(x,int(y/2))
blim = min(int(x/2),y)

for a in range(alim+1):
  blim = int(min((x-a)/2,y-2*a ))
  if x<(a) or y<(2*a):break
  for b in range(blim+1):
#    print(a,b)
    if x<(a+2*b) or y<(2*a+b):
      br = True
      break
    elif x==(a+2*b) and y==(2*a+b):
      s+=comb(a+b,a)
      br = False
      break
  if br:
    br = False
    break
print(int(s%d))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from decimal import Decimal
input = sys.stdin.readline


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

    if x < y:
        temp = x
        x = y
        y = temp
    t = int(x / 2)

    in2_count = 0
    step = 0
    for i in range(t + 1):
        x_step = i + (x - i * 2)
        if (y - i) % 2 != 0:
            continue

        y_step = i + int((y - i) / 2)
        if x_step == y_step:
            in2_count = i
            step = x_step
            break

    if in2_count == 0 and step == 0:
        print('0')
        return

    result = Decimal(combinations_count(step, in2_count))
    print(result % Decimal(1000000007))
    # print(result)


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import exit
import math
x,y = map(int, input().split())
seppen = x + y
def combinations_count(n, r):

    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
if seppen%3 != 0:
    print(0)
    exit()
else:
    dan = seppen/3
    gen_y = seppen/3
    kyori = y - gen_y
    if kyori < 0 or kyori > dan:
        print(0)
    else:
        print(combinations_count(dan, kyori)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
if __name__=='__main__':
    x,y = map(int,input().split())
    x0 = (2.0*x-y)/3.0
    y0 = (2.0*y-x)/3.0
    if x0<0 or y0<0 or not x0.is_integer() or not y0.is_integer():
        ans = 0
    elif x0==0 and y0==0:
        ans = 1
    else:
        x0,y0=map(int,[x0,y0])
        ans = 1
        for i in range(max(x0,y0)+1,x0+y0+1):
            ans = ans*i//(i-max(x0,y0))
    print(int(ans%(10e9+7)))

Submission status: Time Limit Exceeded

Solution code:
import math
X,Y = map(int,input().split())
a,b = (2*Y-X)/3,(2*X-Y)/3
n = 10**9+7
nCr={}
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

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

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

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
def count():
  if not (a//1 == a and b//1==b):
    return 0
  else:
    ahat = int(a%n)
    bhat = int(b%n)
    return cmb(ahat+bhat,ahat)


print(int(count())%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
X,Y = map(int,input().split())
P = 10**9 + 7
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

if (X+Y)%3 != 0:
    ans = 0
elif min(X,Y)*2 < max(X,Y):
    ans = 0
else:
    A = (min(X,Y)-abs(X-Y))//3+abs(X-Y)
    B = (min(X,Y)-abs(X-Y))//3
    ans = 1
    for i in range(A):
        ans = ans*(A+B-i)%P
    for i in range(1,A+1):
        ans = ans*mod_inv(i,P)%P
print(ans)

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

Z=((X+Y)//3)

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

Submission status: Time Limit Exceeded

Solution code:
import sys

def find(dp,x,y):
    mod = 10**9+7
    if x < 0 or y < 0:
        return 0
    if (x,y) in dp.keys():
        return dp[(x,y)]

    dp[(x,y)] = find(dp,x-1,y-2)+find(dp,x-2,y-1)
    dp[(x,y)] %= mod

    return dp[(x,y)]

def main():
    sys.setrecursionlimit(10**8)
    x,y = map(int,raw_input().split())
    dp = {}
    dp[(0,0)] = 1
    print find(dp,x,y)


main()

Submission status: Time Limit Exceeded

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

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

def keiro(x,y,way):
    if x > X or y > Y:
        return 0
    if x == X and y == Y:
        return way + 1

    way1 = keiro(x+1, y+2, way)
    way2 = keiro(x+2, y+1, way)

    return way1+way2

ans = keiro(0, 0, 0)

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

Submission status: Time Limit Exceeded

Solution code:
# ABC145d
 
 
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
 
    x, y = map(int, input().split())
    #dp = [[-1] * (x + 1) for _ in range(y + 1)]
    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][j] != -1:
        #    return dp[i][j]
        #dp[i][j] = (dfs(i - 1, j - 2) + dfs(i - 2, j - 1)) % MOD
        # return dp[i][j]
 
    print(dfs(y, x) % MOD)
 
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
X,Y = map(int,input().split())
P = 10**9 + 7
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

if (X+Y)%3 != 0:
    ans = 0
elif min(X,Y)*2 < max(X,Y):
    ans = 0
else:
    A = (min(X,Y)-abs(X-Y))//3+abs(X-Y)
    B = (min(X,Y)-abs(X-Y))//3
    ans = 1
    for i in range(1,A+B+1):
        ans = ans*i%P
    for i in range(1,A+1):
        ans = ans*mod_inv(i,P)%P
    for i in range(1,B+1):
        ans = ans*mod_inv(i,P)%P
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import itertools
x, y = map(int, input().split())
# (2n+m) + (n+2m) = (x,y) が入るパターンを配列化
ptn = []
count = 0

# 配列総当たり
for n in range((x // 2) + 1):
    for m in range((y // 2) + 1):
        if(y == n + 2 * m and x == 2 * n + m):
            ptn.append([m, n])

for cl in ptn:
    if(cl[0] >= cl[1]):
        count += len(list(itertools.combinations(range(cl[0] + 1), cl[1])))
    else:
        count += len(list(itertools.combinations(range(cl[1] + 1), cl[0])))

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

Submission status: Time Limit Exceeded

Solution code:
def combinations_count(n, r):
    r = min(r, n - r)
    denom=1
    numer=1
    for i in range(1,r+1):
        denom*=i
    for i in range(n-r+1,n+1):
        numer*=i
    return numer // denom

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

if m/3==m//3 and m//3<=x<=2*m//3:
    n=m//3
    k=m*2//3-y
    r=combinations_count(n,k)
    print(r%(10**9+7))

else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
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 c(n, r)


print(solve(x, y) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

import itertools

X, Y = two_int()

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

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

dan = (X+Y)/3
if dan.is_integer():
    n = int(dan+1)
    k = X-(n-1)+1
    print(int(comb(n-1,k-1,(10**9+7))))
else:
    print(0)

Submission status: Time Limit Exceeded

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

n=t+1
k=x-t+1
#print(n)
#print(k)
print( (math.factorial(n-1) // (math.factorial(k-1) * math.factorial(n-k))) % MOD)

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
    for i in range(min(r, n - r)):
        u = u * (n - i) / (i + 1)
    return u


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:
# 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()
    abs_v = abs(y-x)
    print(int(factorial(int(move)) / (factorial(int((move - abs_v) / 2))
                                      * factorial(int((move - abs_v) / 2 + abs_v)))) % 1000000007)

else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
x,y=map(int,input().split())
if ((2*x)-y)%3!=0 or ((2*y)-x)%3!=0:
  print(0)
  sys.exit()
n=((2*x)-y)//3
m=((2*y)-x)//3
a=1
b=1
c=1
for i in range(1,m+n+1):
  a*=i
for j in range(1,m+1):
  b*=j
for k in range(1,n+1):
  c*=k
print((a//(b*c))%((10**9)+7))