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())
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)*pow(ka(n),mod-2,mod))%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
mx,my = readInts()
jump = [(1,2),(2,1)]
dq = deque()
dq.append((0,0))
cnt = 0
while dq:
    x,y = dq.popleft()
    for i in range(2):
        dx,dy = jump[i]
        nx = x + dx
        ny = y + dy
        if ny > my or nx > mx:
            continue
        if ny == my and nx == mx:
            cnt = (cnt + 1)%mod
        dq.append((nx,ny))
print(cnt%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
x,y = map(int,input().split())
mod = 10**9+7
def count_route(x,y):
  if x<=0 or y<=0:
    return 0
  elif x/y>2 or y/x>2:
    return 0
  elif x%y==0 and x//y==2:
    return 1
  elif y%x==0 and y//x==2:
    return 1
  else:
    return sum([count_route(x-1,y-2)%mod,count_route(x-2,y-1)%mod])
print(count_route(x,y))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
p = list(map(int,input().split()))
Q = deque()
Q.append(p)
cnt = 0
while Q:
  temp = Q.popleft()
  x,y = temp
  s = [x-1,y-2]
  t = [x-2,y-1]
  if x-1>=2 or y-2>=2:
    Q.append(s)
  if x-2>=2 or y-1>=2:
    Q.append(t)
  if s==[0,0] or t==[0,0]:
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    x, y = map(int, readline().split())
    ans = 0
    ilist = [1]
    tmp = 1
    for i in range(1, max(x,y)+1):
        tmp *= i
        ilist.append(tmp)
    for b in range(x//2+1):
        a = x - 2 * b
        if 2*a + b == y:
            ans += ilist[a+b] // ilist[b] //ilist[a]
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

def factorial(n):
    if n == 0:
        return 1
    else:
        a = 1
        for i in range(n):
            a *= n - i
        return a

def comb(a, b):
    return factorial(a) // (factorial(b) * factorial(a - b))

if y < x:
    temp = y
    y = x
    x = temp

dif = x - y
if ((y - dif) % 3 != 0) | (dif > y):
    print('0')
else:
    k = (y - dif) // 3
    n = comb(2 * k + dif, k) % (10**9 + 7)
    print(n)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

MAX = 2 * 10 ** 6 + 2
MOD = 10 ** 9 + 7

fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]

def comInit(mod):
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 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, r, mod):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod
    
comInit(MOD)

if X < Y:
    X, Y = Y, X
b = (2 * X - Y) // 3
a = X - 2 * b
print(com(a + b, b, MOD))

Submission status: Time Limit Exceeded

Solution code:
x,y = map(int,input().split())
def combinations_count(n, r): #組み合わせ(nCr)
    import math
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
if 1/2 <= y/x <= 2 and (x+y)/3 % 1 == 0:
    yy = (x+y)/3
    u = y - yy
    r = yy - u
    print(combinations_count(yy, min(r,yy-r))%(10**9+7))
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
# 21:50まで

# (X, Y)に移動させる移動方法は何通り？
# 移動方法は2パターン
#   (i + 1, j + 2) か (i + 2, j + 1)
#  移動させる組み合わせは、上記2種のパターン組み合わせ個数による

# 全パターン探索する場合
# 深さ優先探索 計算量ヤバめ

# (0, 0) -> (X, Y)
# (X, Y) に行くためには、
# (X-1, Y-2)
# (X-2, Y-1)
# 両方からいける
# の3通り

from collections import deque


def main():
    X, Y = map(int, input().rstrip().rsplit())

    if Y > 2*X or Y < X / 2:
        print(0)
        return

    if Y == 2*X or Y == X / 2:
        print(1)
        return

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

    cnt = 0
    while len(stack) > 0:
        x, y = stack.pop()

        if x == X and y == Y:
            cnt += 1
            continue

        if x > X or y > Y:
            continue

        stack.append((x+1, y+2))
        stack.append((x+2, y+1))
    print(cnt % (10 ** 9 + 7))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

from collections import deque

def power(base, exp):
    """ Fast power calculation using repeated squaring """
    if exp < 0:
        return 1 / power(base, -exp)
    ans = 1
    while exp:
        if exp & 1:
            ans *= base
        exp >>= 1
        base *= base
    return ans

def parse():
  return map(int, input().split(" "))

def print_grid(grid, X, Y):
  Y = len(grid)
  X = len(grid[0])
  for y in range(Y):
    for x in range(X):
      if grid[y][x]:
        print(1, end="")
      else:
        print(0, end="")
    print("")
  print("")

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

  start_X = 2
  start_Y = 2
  end_X = X + start_X
  end_Y = Y + start_Y

  visited = {}
  # visited = [[False for x in range(X + 1 + 4)] for y in range(Y + 1 + 4)]

  # 到達不可能かどうかの判定
  if X == 0 or Y == 0:
    print(0)
    exit(0)
  elif Y > X * 2:
    print(0)
    exit(0)
  elif X > Y * 2:
    print(0)
    exit(0)
  
  # 1通りの場合（片方の操作のみを連続で行う場合）
  if Y == X * 2:
    print(1)
    exit(0)
  elif X == Y * 2:
    print(1)
    exit(0)

  # 枠外は移動済みとする
  for y in range(Y + 1 + 4):  # ↓
    visited["{0},{1}".format(0, y)] = None
    visited["{0},{1}".format(1, y)] = None
    visited["{0},{1}".format(end_X + 1, y)] = None
    visited["{0},{1}".format(end_X + 2, y)] = None
  for x in range(X + 1 + 4):  # →
    visited["{0},{1}".format(x, 0)] = None
    visited["{0},{1}".format(x, 1)] = None
    visited["{0},{1}".format(x, end_Y + 1)] = None
    visited["{0},{1}".format(x, end_Y + 2)] = None

  # print("visited")

  # for y in range(Y + 1 + 4):
  #   for x in range(X + 1 + 4):
  #     if y < start_Y or x < start_X or x > end_X or y > end_Y:
  #       visited["{0},{1}".format(x, y)] = None
        # visited[y][x] = True
  # print_grid(visited)
  # exit(0)

  # 深さ優先探索
  ans = 0
  stack = deque([(start_X, start_Y)])
  while len(stack) > 0:
    x, y = stack.pop()
    if visited.get("{0},{1}".format(x, y), 0) == 0:
    # if not visited[y][x]:
      visited["{0},{1}".format(x, y)] = None
      # visited[y][x] = True
      stack.append((x + 1, y + 2))
      stack.append((x + 2, y + 1))
    
    if y == end_Y and x == end_X:
      ans += 1

    # print_grid(visited)
  print(ans % (power(10, 9) + 7))

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:

from collections import deque

def power(base, exp):
    """ Fast power calculation using repeated squaring """
    if exp < 0:
        return 1 / power(base, -exp)
    ans = 1
    while exp:
        if exp & 1:
            ans *= base
        exp >>= 1
        base *= base
    return ans

def parse():
  return map(int, input().split(" "))

def print_grid(grid, X, Y):
  Y = len(grid)
  X = len(grid[0])
  for y in range(Y):
    for x in range(X):
      if grid[y][x]:
        print(1, end="")
      else:
        print(0, end="")
    print("")
  print("")

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

  start_X = 2
  start_Y = 2
  end_X = X + start_X
  end_Y = Y + start_Y

  visited = {}
  # visited = [[False for x in range(X + 1 + 4)] for y in range(Y + 1 + 4)]

  # 到達不可能かどうかの判定
  if X == 0 or Y == 0:
    print(0)
    exit(0)
  elif Y > X * 2:
    print(0)
    exit(0)
  elif X > Y * 2:
    print(0)
    exit(0)

  # 枠外は移動済みとする
  for y in range(Y + 1 + 4):  # ↓
    visited["{0},{1}".format(0, y)] = None
    visited["{0},{1}".format(1, y)] = None
    visited["{0},{1}".format(end_X + 1, y)] = None
    visited["{0},{1}".format(end_X + 2, y)] = None
  for x in range(X + 1 + 4):  # →
    visited["{0},{1}".format(x, 0)] = None
    visited["{0},{1}".format(x, 1)] = None
    visited["{0},{1}".format(x, end_Y + 1)] = None
    visited["{0},{1}".format(x, end_Y + 2)] = None

  # print("visited")

  # for y in range(Y + 1 + 4):
  #   for x in range(X + 1 + 4):
  #     if y < start_Y or x < start_X or x > end_X or y > end_Y:
  #       visited["{0},{1}".format(x, y)] = None
        # visited[y][x] = True
  # print_grid(visited)
  # exit(0)

  # 深さ優先探索
  ans = 0
  stack = deque([(start_X, start_Y)])
  while len(stack) > 0:
    x, y = stack.pop()
    if visited.get("{0},{1}".format(x, y), 0) == 0:
    # if not visited[y][x]:
      visited["{0},{1}".format(x, y)] = None
      # visited[y][x] = True
      stack.append((x + 1, y + 2))
      stack.append((x + 2, y + 1))
    
    if y == end_Y and x == end_X:
      ans += 1

    # print_grid(visited)
  print(ans % (power(10, 9) + 7))

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:

from collections import deque

def parse():
  return map(int, input().split(" "))

def print_grid(grid, X, Y):
  Y = len(grid)
  X = len(grid[0])
  for y in range(Y):
    for x in range(X):
      if grid[y][x]:
        print(1, end="")
      else:
        print(0, end="")
    print("")
  print("")

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

  start_X = 2
  start_Y = 2
  end_X = X + start_X
  end_Y = Y + start_Y

  visited = {}
  # visited = [[False for x in range(X + 1 + 4)] for y in range(Y + 1 + 4)]

  # 枠外は移動済みとする
  for y in range(Y + 1 + 4):  # ↓
    visited["{0},{1}".format(0, y)] = None
    visited["{0},{1}".format(1, y)] = None
    visited["{0},{1}".format(end_X + 1, y)] = None
    visited["{0},{1}".format(end_X + 2, y)] = None
  for x in range(X + 1 + 4):  # →
    visited["{0},{1}".format(x, 0)] = None
    visited["{0},{1}".format(x, 1)] = None
    visited["{0},{1}".format(x, end_Y + 1)] = None
    visited["{0},{1}".format(x, end_Y + 2)] = None

  # for y in range(Y + 1 + 4):
  #   for x in range(X + 1 + 4):
  #     if y < start_Y or x < start_X or x > end_X or y > end_Y:
  #       visited["{0},{1}".format(x, y)] = None
        # visited[y][x] = True
  # print_grid(visited)
  # exit(0)

  # 深さ優先探索
  ans = 0
  stack = deque([(start_X, start_Y)])
  while len(stack) > 0:
    x, y = stack.pop()
    if visited.get("{0},{1}".format(x, y), 0) == 0:
    # if not visited[y][x]:
      visited["{0},{1}".format(x, y)] = None
      # visited[y][x] = True
      stack.append((x + 1, y + 2))
      stack.append((x + 2, y + 1))
    
    if y == end_Y and x == end_X:
      ans += 1

    # print_grid(visited)
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    X, Y = map(int, input().rstrip().rsplit())

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

    cnt = 0
    while len(stack) > 0:
        x, y = stack.pop()

        if x == X and y == Y:
            cnt += 1
            continue

        if x > X or y > Y:
            continue

        stack.append((x+1, y+2))
        stack.append((x+2, y+1))

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7

def comb(n, r):
    if n < r or n < 0 or r < 0:
        return 0

    n += 1
    over = 1
    under = 1
    for i in range(1,r + 1):
      over *= (n - i) % MOD
      under *= i % MOD
    return over * pow(under, MOD - 2, MOD) % MOD

if (X + Y) % 3 != 0:
    print(0)
else:
    a = (2 * X - Y) // 3
    b = (2 * Y - X) // 3
    print(comb(a+b, a))

Submission status: Time Limit Exceeded

Solution code:
import math
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) % (10 ** 9 + 7)

>TLE
> 竸プロの、nCk mod. p 　パターン
>逆元を利用する。
'''


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

diff = abs(x - y)
large = max(x, y)
small = min(x, y)

if (small * 2 < large):
    print(0)
    exit()


#ans = diff
large -= diff * 2
small -= diff

if (small % 3 != 0):
    print(0)
    exit()

else:
    num = small / 3
    nn = num * 2 + diff
    #rr = num
    ans = comb(int(nn), int(num), 10 ** 9 + 7)

    print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
MOD=10**9+7
x , y = map(int, input().split())
a=(2*x-y)//3
b=(2*y-x)//3
if 2*a+b!=x:
    print(0)
    exit()

factorial = [1]
inverse = [1]

n=a+b
r=a

for i in range(1, n+2):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))

def combi(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD

ans = combi(n,r)
print(ans)

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


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

mod = 10**9+7

division = (x+y)//3

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


mod = 10**9+7

#combを求める前処理 O(log division)
g1 = [1, 1] #元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

r = min(x,y)-division
ans = cmb(division,r,mod)

print(ans)

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


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

mod = 10**9+7

division = (x+y)//3

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


mod = 10**9+7

#combを求める前処理 O(log division)
g1 = [1, 1] #元テーブル
g2 = [1, 1] #逆元テーブル

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

r = min(x,y)-division
ans = cmb(division,r,mod)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
p = 10 ** 9 + 7
N = 10 ** 7
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
X,Y = list(map(int,input().split()))
if (X+Y)%3 != 0:
    print(0)
    exit()
N = (X+Y)//3
K = 2*N-X
print(cmb(N,K,p))

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10**9 + 7
N = 10**7  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N+1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

x,y=map(int,input().split())
ans=0
x_3=x//3
y_3=y//3
kyo2=min(x_3,y_3)
xx=x-kyo2*3
yy=y-kyo2*3

#print(xx,yy,kyo2)
    
if (xx==0 and yy==0):
  ans=cmb(2*kyo2,kyo2,p)
  print(ans)
elif (xx/yy==2):
  ans=cmb(2*kyo2+yy,kyo2,p)
  print(ans)
elif (yy/xx==2):
  ans=cmb(2*kyo2+xx,kyo2,p)
  print(ans)
else:
  print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
# N = int(input())
X, Y = [int(i) for i in input().split()]

sys.setrecursionlimit(100000)


@lru_cache(maxsize=None)
def solve(x, y):
    if x <= 0 or y <= 0:
        return 0
    if (x, y) == (1, 2) or (x, y) == (2, 1):
        return 1
    return (solve(x-1, y-2) + solve(x-2, y-1)) % (10**9+7)


print(solve(X, Y))

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
# N = int(input())
X, Y = [int(i) for i in input().split()]

sys.setrecursionlimit(100000)


# @lru_cache(maxsize=None)
def solve(x, y):
    if x <= 0 or y <= 0:
        return 0
    if (x, y) == (1, 2) or (x, y) == (2, 1):
        return 1
    return (solve(x-1, y-2) + solve(x-2, y-1)) % (10**9+7)


print(solve(X, Y))

Submission status: Time Limit Exceeded

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

from collections import deque
h=X;w=Y
sx,sy=0,0
stack=deque([[sx,sy]])
dxdy=[[1,2],[2,1]]
visited=[[0 for i in range(w)] for j in range(h)]
ans=0
while stack:
    x,y=stack.popleft()
    for i in dxdy:
        nx,ny=x+i[0],y+i[1]
        if (0<=nx<=h) and (0<=ny<=w):
            stack.append([nx,ny])
            if nx==h and ny==w:
                ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np

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

A = np.array([[1, 2],
           [2, 1]])

b = np.array([x, y])

N = np.linalg.solve(A, b)


if N[0].is_integer() == True and N[1].is_integer() == True and N[0] >=0 and N[1] >=0:
  
  k = math.factorial(N[0]+N[1])/(math.factorial(N[0])*math.factorial(N[1]))

  print(int(k%1000000007))

else:
  print(0)

Submission status: Time Limit Exceeded

Solution code:
x,y=map(int, input().split())
q = [[0,0]]
ans = 0
while len(q) > 0:
    point = q.pop(0)
    next1 = [point[0]+1, point[1]+2]
    next2 = [point[0]+2, point[1]+1]

    if next1 == [x,y]:
        ans += 1
    elif next1[0] < x and next1[1] < y:
        q.append(next1)
    if next2 == [x,y]:
        ans += 1
    elif next2[0] < x and next2[1] < y:
        q.append(next2)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
MAX = 5100000

MOD = 1000000007


def read_input():
    x, y = map(int, input().split(" "))
    return x, y


class BinomialCoefficients(object):
    def __init__(self, MAX=MAX, MOD=MOD):
        self.MOD = MOD
        self.fac = [1 for _ in range(MAX)]
        self.finv = [1 for _ in range(MAX)]
        self.inv = [1 for _ in range(MAX)]
        for i in range(2, MAX):
            self.fac[i] = self.fac[i - 1] * i % MOD
            self.inv[i] = MOD - self.inv[MOD % i] * (MOD // i) % MOD
            self.finv[i] = self.finv[i - 1] * self.inv[i] % MOD

    def calc(self, n, k):
        if n < k:
            return 0
        if n == 0 or k < 0:
            return 0
        return self.fac[n] * (self.finv[k] * self.finv[n - k] % self.MOD) % self.MOD


def ans(X, Y):
    a_3 = 2 * X - Y
    b_3 = 2 * Y - X
    if a_3 % 3 != 0 and b_3 % 3 != 0:
        return 0
    if a_3 < 0 or b_3 < 0:
        return 0
    a = a_3 // 3
    b = b_3 // 3

    c = BinomialCoefficients()
    return c.calc(a + b, a)


if __name__ == "__main__":
    X, Y = read_input()
    print(ans(X, Y))

Submission status: Time Limit Exceeded

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

if (2*x-y)%3!=0 or (2*y-x)%3!=0 or a<0 or b<0:
	print(0)

else:
	L=[1]*(a+b+1)
	for i in range(1,a+b+1):
		L[i]=L[i-1]*i
		L[i]=L[i]%mod
	ab=L[a]*L[b]
	ab=ab%mod
	for j in range(1, mod):
		abj=(ab*j)%mod
		if abj==L[a+b]:
			print(j)
			break

Submission status: Time Limit Exceeded

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

if (2*x-y)%3!=0 or (2*y-x)%3!=0 or a<0 or b<0:
	print(0)

else:
	L=[1]*(a+b+1)
	for i in range(1,a+b+1):
		L[i]=L[i-1]*i
		L[i]=L[i]%mod
	ab=L[a]*L[b]
	ab=ab%mod
	for j in range(1, mod):
		abj=(ab*j)%mod
		if abj==L[a+b]:
			print(j)
			break

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from math import factorial 
from math import floor
P = int(1e9)+7
def c(n, m, P):
       ch = 1
       for i in range(m):
           ch *= (n-i)
           ch %= P
       b = factorial(m) 
       b = pow(b, P-2, P)
       return ch*b%P
def main():
    x, y = map(int, readline().split())
    a = (2*y-x)/3
    b = (2*x-y)/3
    if (a < 0) or (b < 0):
        print(0)
        return
    if floor(a)-a != 0: 
        print(0)
        return
    if floor(b)-b != 0:
        print(0)
        return

    a = int(a)
    b = int(b)
    print(c(a+b, a, P)) 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from math import factorial 
P = int(1e9)+7
def c(n, m, P):
       ch = 1
       for i in range(m):
           ch *= (n-i)
           ch %= P
       b = factorial(m) 
       b = pow(b, P-2, P)
       return ch*b%P
def main():
    x, y = map(int, readline().split())
    a = 2*y-x
    b = 2*x-y
    if (a%3) or (b%3):
        print(0)
        return
    a = a//3
    b = b//3
    if a < 0:
        print(0)
        return
    if b < 0:
        print(0)
        return
    print(c(a+b, a, P)) 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from math import factorial 
P = int(1e9)+7
def c(n, m, P):
       ch = 1
       for i in range(m):
           ch *= (n-i)
           ch %= P
       b = factorial(m) 
       b = pow(b, P-2, P)
       return ch*b%P
def main():
    x, y = map(int, readline().split())
    if ((2*y-x)%3) or ((2*x-y)%3):
        print(0)
        return
    a = (2*y-x)//3
    b = (2*x-y)//3
    if a < 0:
        print(0)
        return
    if b < 0:
        print(0)
        return
    print(c(a+b, a, P)) 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from math import factorial 
P = int(1e9)+7
def c(n, m):
       ch = 1
       for i in range(m):
           ch *= (n-i)
           ch %= P
       b = factorial(m) 
       b = pow(b, P-2, P)
       return ch*b%P
def main():
    x, y = map(int, readline().split())
    if ((2*y-x)%3) or ((2*x-y)%3):
        print(0)
        return
    a = (2*y-x)//3
    b = (2*x-y)//3
    if a < 0:
        print(0)
        return
    if b < 0:
        print(0)
        return
    print(c(a+b, a)) 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from math import factorial 
def main():
    x, y = map(int, readline().split())
    if ((2*y-x)%3) or ((2*x-y)%3):
        print(0)
        return
    a = (2*y-x)//3
    b = (2*x-y)//3
    if a < 0:
        print(0)
        return
    if b < 0:
        print(0)
        return
    P = int(1e9)+7
    def c(n, m):
        ch = 1
        for i in range(m):
            ch *= (n-i)
            ch %= P
        b_ = factorial(m) 
        b = pow(b_, P-2, P)
        return ch*b%P
    print(c(a+b, a)) 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from math import factorial 
def main():
    x, y = map(int, readline().split())
    if ((2*y-x)%3) or ((2*x-y)%3):
        print(0)
        return
    a = (2*y-x)//3
    b = (2*x-y)//3
    if a < 0:
        print(0)
        return
    if b < 0:
        print(0)
        return
    P = int(1e9)+7
    def c(n, m):
        ch = 1
        for i in range(m):
            ch *= (n-i)
            ch %= P
        b = factorial(m) 
        b = pow(b, P-2, P)
        return ch*b%P
    print(c(a+b, a)) 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

if (X + Y) % 3 != 0 or X > 2*Y or Y > 2*X:
    print(0)
else:
    n2x = (2*X - Y) // 3
    n1x = (2*Y - X) // 3
    n = n2x + n1x

    # nCn2xを求める
    def combs(n,n2x):
        invs = [1] * (n+1)
        nfac = 1
        for i in range(1, n+1):
            nfac = nfac * i % mod
            invs[i] = pow(nfac, mod-2, mod)
        return nfac * invs[n2x] * invs[n-n2x] % mod

    print(combs(n, n2x))

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

X,Y = map(int,input().split())
x,y = (2*X-Y)//3,(2*Y-X)//3#行動１、行動２を起こす回数
if (2*X-Y)%3 != 0 or (2*Y-X)%3 != 0 or x < 0 or y < 0 or(x==0 and y==0):
    print(0)
    exit()
ans =1
for i in range(x+y,0,-1):
    ans = ((ans%MOD)*i)%MOD
for i in range(x,0,-1):
    ans = ((ans%MOD)*pow(i,MOD-2,MOD))%MOD
for i in range(y,0,-1):
    ans = ((ans%MOD)*pow(i,MOD-2,MOD))%MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7) 
x,y=map(int,input().split())
sum=0
def chess(i,j):
  a=0
  if i == x and j == y:
    a+=1
    return a
  elif i>x or j>y:
    return 0
  elif i<x and j<y:
    return chess(i+1,j+2)+chess(i+2,j+1)
  return a
  
print(chess(0,0)%(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 = 2*10**6 + 1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

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

A = (2*Y - X) // 3
B = (2*X - Y) // 3

print(cmb(A+B, A, mod))

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

X1, Y1 = map(int, input().split())

if X1 >= Y1:
  X = X1
  Y = Y1
  pass
else:
  X = Y1
  Y = X1
if X > 2 * Y:
  print(0)
  exit()
else:
  pass

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

if (2 * X - Y) % 3 != 0 or (2 * Y - X) % 3 != 0:
  print(0)
  exit()
else:
  ans = combinations_count((m + n), n) % (10 ** 9 + 7)
print(ans)

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

X1, Y1 = map(int, input().split())

if X1 >= Y1:
  X = X1
  Y = Y1
  pass
else:
  X = Y1
  Y = X1
if X > 2 * Y:
  print(0)
  exit()
else:
  pass

cnt1 = 0

while X < 2 * Y:
  X = X - 1
  Y = Y - 2
  cnt1 += 1

if X != 2 *Y:
  print(0)
  exit()
else:
  pass

cnt2 = Y
ans = combinations_count((cnt1 + cnt2), cnt2) % (10 ** 9 + 7)
print(ans)

Submission status: Time Limit Exceeded

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

X, Y = min(X,Y), max(X,Y)

dist = X+Y
if dist%3 != 0 or 2*X < Y:
  ans = 0
else:
  N = dist//3
  Y -= N
  Y = min(N,Y)
  
  ans = 1
  ue = 1
  shita = 1
  for n in range(Y):
    ue *= N-n
    shita *= n+1
    
  ans = (ue//shita) % (10**9+7)
  
print(ans)

Submission status: Time Limit Exceeded

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

X, Y = min(X,Y), max(X,Y)

dist = X+Y
if dist%3 != 0 or 2*X < Y:
  ans = 0
else:
  N = dist//3
  Y -= N
  Y = min(N,Y)
  
  ans = 1
  ue = 1
  shita = 1
  for n in range(Y):
    ue *= N-n
    shita *= n+1
    
  ans = (ue//shita) % (1**9+7)
  
print(ans)

Submission status: Time Limit Exceeded

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

X, Y = min(X,Y), max(X,Y)

dist = X+Y
if dist%3 != 0 or 2*X < Y:
  ans = 0
else:
  N = dist//3
  Y -= N
  Y = min(N,Y)
  
  ans = 1
  ue = 1
  shita = 1
  for n in range(Y):
    ue *= N-n
    shita *= n+1
    
  ans = int(ue/shita) % (1**9+7)
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def combination(m, n):
    a = 1
    b = 1

    for i in range(m-n+1, m+1):
        a *= i

    for j in range(1, n+1):
        b *= j

    return a/b


mod = 10**9 + 7

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

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

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

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

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

print(combination(n+m, n) % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): return k.join(list(map(str, lst)))
INF = float('inf')
from collections import deque
def solve():
    x, y = MI()

    q = deque([(0, 0)])
    mod = 1000000007

    cnt = {(0, 0): 1}
    while len(q) > 0:
        cx, cy = q.popleft()
        d = cnt[(cx, cy)]
        for i in [1, 2]:
            nx = cx + i
            ny = cy + 3 - i
            if nx > x or ny > y:
                continue
            elif (nx, ny) in q:
                cnt[(nx, ny)] += d
            else:
                q.append((nx, ny))
                cnt[(nx, ny)] = d
    print(cnt.get((x, y), 0) % mod)

if __name__ == '__main__':
    solve()