Problem:


Score : 400 points

Problem Statement

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

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

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

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

Constraints

1 \leq X \leq 10^6

1 \leq Y \leq 10^6

All values in input are integers.

Input

Input is given from Standard Input in the following format:

X Y

Output

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

Sample Input 1

3 3

Sample Output 1

2

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

Sample Input 2

2 2

Sample Output 2

0

The knight cannot reach (2,2).

Sample Input 3

999999 999999

Sample Output 3

151840682

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



Sample input:
3 3


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
mod = 10**9+7
x,y = map(int,input().split())
if (x+y) % 3 != 0:
    res = 0
else:
    m = (2 * x - y) // 3
    n = (2 * y - x) // 3
    if m < 0 or n < 0:
        res = 0
    else:
        res = comb(n+m, n, mod)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
x,y = map(int,input().split())
def count(x,y):
    if (y+x) % 3 != 0 or y > 2 * x or y < x / 2:
        return 0
    elif x == 0 and y == 0:
        return 1
    else:
        return count(x-1, y-2) + count(x-2, y-1)
print(count(x,y))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
X,Y = (int(x) for x in input().split())
def route(x,y):
    d = min(x,y) - ((x+y)//3)
    if d == 0:
        return 1
    else:
        return (route(x-2,y-1) + route(x-1,y-2))%1000000007
if (X+Y) % 3 != 0 or min(X,Y) < (X+Y) // 3:
    print('0')
else:
    print(route(X,Y))

Submission status: Time Limit Exceeded

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

def knight(i, j):
    if i - 1 == 0 and j - 2 == 0: return 1
    if i - 2 == 0 and j - 1 == 0: return 1
    if i - 1 < 0 or j - 2 < 0: return 0
    if i - 2 < 0 or j - 1 < 0: return 0
    return knight(i - 1, j - 2) + knight(i - 2, j - 1) % (10 ** 9 + 7)

print(knight(x, y))

Submission status: Time Limit Exceeded

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

if (2*x-y)%3!=0 or (2*x-y)<0:
  print(0)
  exit()
if (2*y-x)%3!=0 or (2*y-x)<0:
  print(0)
  exit()
p=int((2*x-y)/3)
q=int((2*y-x)/3)
M=2*(10**6)
Mod=10**9+7

fac=[0]*M
finv=[0]*M
inv=[0]*M

def COMinit():
  fac[0]=fac[1]=1
  finv[0]=finv[1]=1
  inv[1]=1
  for i in range(2,M):
    fac[i]=(fac[i-1]*i%Mod)%Mod
    inv[i]=Mod-inv[Mod%i]*(Mod//i) %Mod
    finv[i]=(finv[i-1]*inv[i]%Mod)%Mod
def COM(n,k):
  if n<k:
    return 0
  if n<0 or k<0:
    return 0
  return (fac[n]*(finv[k]*finv[n-k]%Mod)%Mod)%Mod

COMinit()
print(COM(p+q,p))

Submission status: Time Limit Exceeded

Solution code:
def comb(n, r, p):
    x = 1
    for i in range(1, r + 1):
        x *= (n - i + 1) * pow(i, p - 2, p) % p
    return x % p

X, Y = map(int, input().split())
a = (2*X - Y)/3
b = (2*Y - X)/3
 
if (X+Y)%3 != 0:
    ans = 0
 
elif a<0 or b<0:
    ans = 0
 
else:
    ans = comb(int(a + b), int(a), 10**9 + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb


def main():
  x, y = map(int, input().split())
  
  if (x + y) % 3 != 0:
    print(0)
    return
  
  s = (2 * y - x) //3
  t = (2 * x - y) //3
  
  print(comb(s + t, s, exact=True) % (10 ** 9 + 7))


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:
    print(0)
    exit(0)

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

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**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 )
    g2.append( pow(g1[-1],mod-2,mod) )


print(cmb(a+b,a,mod))

Submission status: Time Limit Exceeded

Solution code:
import math
X, Y = map(int,input().split())
max = X // 2

# bはxが２を増えるパターンの回数
for b in range(0, max+1):
    a = X - 2 * b
    if a * 2 + b == Y:
        break
    if b == max:
        print(0)
        exit()

ans = math.factorial(a + b) // math.factorial(a) // math.factorial(b)
ans = ans % (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
X, Y = map(int, input().split())
n = (2 * X - Y) / 3
m = (2 * Y - X) / 3

if n < 0 or m < 0 or not n.is_integer() or not m.is_integer():
    print(0)
    exit()

n, m = map(int, [n, m])
mod = 10**9 + 7
fact = [1]
inv = [1]
for i in range(1, X + Y + 1):
    fact.append((fact[i-1] * i) % mod)
    inv.append(pow(fact[-1], mod-2, mod))

def cmb(n, r):
    return fact[n] * inv[n-r] * inv[r]

print(cmb(n+m, min(n, m)) % mod)

Submission status: Time Limit Exceeded

Solution code:
X, Y = map(int, input().split())
n = (2 * X - Y) / 3
m = (2 * Y - X) / 3

if n < 0 or m < 0 or not n.is_integer() or not m.is_integer():
    print(0)
    exit()

MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

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

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

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

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

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

    __radd__ = __add__

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

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

n, m = map(int, [n, m])
fact = [ModInt(1)]
for i in range(1, X + Y + 1):
    fact.append(fact[i-1] * i)

def cmb(n, r):
    return fact[n] / fact[n-r] / fact[r]

print(cmb(n+m, min(n, m)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
input = sys.stdin.readline
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+2
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 )


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

x,y=MI()
if y>2*x or x>2*y:
    print(0)
    sys.exit()
elif x%3==0 and y%3==0:
    m=x//3
    l=y//3
    print(cmb(m+l,2*l-m,mod))
    
elif x%3==1 and y%3==2:
    m=(x-1)//3
    l=(y-2)//3
    print(cmb(m+l+1,2*l-m+1,mod))
elif x%3==2 and y%3==1:
    m=(x-2)//3
    l=(y-1)//3
    print(cmb(m+l+1,2*l-m,mod))
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7


def power_expo(x, y):
    """Returns x^y.

    <https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6>
    """
    if y == 0:
        return 1
    elif y == 1:
        return x % MOD
    elif y % 2 == 0:
        return power_expo(x, y // 2) ** 2 % MOD
    else:
        return power_expo(x, y // 2) ** 2 * x % MOD


def main():
    x, y = [int(x) for x in input().split()]
    if (x + y) % 3 != 0:
        return 0
    summ = (x + y) // 3     # d + r
    diff = x - y  # d - r
    if summ % 2 != diff % 2:
        return 0
    d = (summ + diff) // 2  # Down
    r = (summ - diff) // 2  # Right
    if d < 0 or r < 0:
        return 0
    chosen = min(d, r)

    patterns = 1

    for i, j in zip(range(summ - chosen + 1, summ + 1), range(1, summ + 1)):
        patterns = patterns * i % MOD * power_expo(j, MOD - 2) % MOD

    return patterns


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

# やはり難しい，再び解説。割り算のときは mod 10^9+7 が厄介。
# とりあえず，割る方は 10^9+5 乗して掛ければいいらしい。

Submission status: Time Limit Exceeded

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

def cmb(n,k):
    x,y=1,1
    for i in range(k):
        x*=(n-i)%mod
        y*=(k-i)%mod
    return x*pow(y,mod-2,mod)%mod

if (X+Y)%3!=0:
    print(0)
else:
    m=(2*X-Y)//3
    n=(2*Y-X)//3
    if n<0 or m<0:
        print(0)
    else:
        mod=10**9+7
        ans=cmb(n+m,min(n,m))
        print(ans)

Submission status: Time Limit Exceeded

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

for i in range(2,X+1):
    for j in range(max(2,i//2),min(Y+1,i*2+1)):
        if (i+j) % 3 == 0:
            dp[i][j] = (dp[i-2][j-1] + dp[i-1][j-2]) % (10**9+7)

print(dp[X][Y])

Submission status: Time Limit Exceeded

Solution code:
x,y=map(int,input().split())
MAX_NUM = 2*10**6 + 1
pr = 10**9+7
fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]
fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % pr
    inv[i] = pr - inv[pr%i] * (pr // i) % pr
    finv[i] = finv[i-1] * inv[i] % pr
def c(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % pr) % pr
if (x+y)%3:
    print(0)
else:
    n=(x+y)//3
    x-=n
    y-=n
    print(c(x+y,x))

Submission status: Time Limit Exceeded

Solution code:
def gho(x):
  g=1
  for i in range(1,x+1):
    g*=i
  return g

q,w=map(int,input().split())
e,d=divmod((2*w-q),3)
r,f=divmod((2*q-w),3)

if d!=0 or f!=0:print(0)
else:
  print((gho(e+r)//(gho(e)*gho(r)))%(10*9+7))

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7

def Pow(a, n):
    if n == 0: return 1
    if n%2 == 0:
        return (Pow(a, n//2))**2%mod
    else:
        return Pow(a, n-1)*a%mod

X, Y = map(int, input().split())
if (X+Y)%3 != 0:
    print(0)
else:
    n = (X+Y)//3
    if X < n or Y < n or X > 2*n or Y > 2*n:
        print(0)
    else:
        k = min(X-n, Y-n)
        R = [0] * (k+1)
        for i in range(1,k+1):
            R[i] = Pow(i, mod-2)
        cmb = [0]*(k+1)
        cmb[0] = 1
        for i in range(k):
            cmb[i+1] = ((cmb[i]*(n-i))%mod)*R[i+1]%mod
        print(cmb[k])

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
X,Y = (int(x) for x in input().split())

if (X+Y) % 3 != 0:
  print(0)
  sys.exit()
  
n = (2*Y-X) / 3
m = (2*X-Y) / 3
if n < 0 or m < 0:
  print(0)
  sys.exit()
  
print(math.factorial(n+m) // (math.factorial(m) * math.factorial(n)))

Submission status: Time Limit Exceeded

Solution code:
X, Y = map(int,input().split())
MOD = 10 ** 9 + 7
if (X + Y) % 3 != 0 or 2 * X < Y or 2 * Y < X:
    print(0)
else:
    turn = (X + Y) // 3
    turn2 = X - turn
    turn1 = turn - turn2
    ans = 1
    for i in range(turn1):
        ans *= turn - i
        ans //= i + 1
    print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
def solve(x, y):
    if (x + y) % 3 != 0:
        return 0
    n = (x + y) // 3
    r = min((2 * y - x) // 3, (2 * x - y) // 3)
    return cmb(n, r, mod)

_x, _y = map(int, input().split())

mod = 10 ** 9 + 7
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inverse = [0, 1] # 逆元テーブル計算用テーブル

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

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

print(solve(_x, _y))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
X,Y = map(int,input().split())

mod = 10**9+7

dx = [1,2]
dy = [2,1]

sx = sy = 0

q = deque()
q.appendleft((sx,sy))
count = 0
while q:
  c = q.pop()
  for i in range(2):
    
    nx = c[0] + dx[i]
    ny = c[1] + dy[i]
    if nx == X and ny ==Y:
      count += 1 
    elif nx < X and ny < Y:
      q.appendleft((nx,ny))  
      
if count == 0:
  print(0)
else:
  print(count%mod)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
from collections import defaultdict
import sys
sys.setrecursionlimit(int(1e6))

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

dp = defaultdict(lambda: defaultdict(lambda: -1))
def dfs(num_max, num_min):
    if dp[num_max][num_min] != -1:
        return dp[num_max][num_min]
    if num_max == 0 and num_min == 0:
        return 1
        
    count = 0
    if num_max >= 0:
        count += dfs(num_max - 1, num_min)
        count %= int(1e9+7)
    if num_min >= 0:
        count += dfs(num_max, num_min - 1)
        count %= int(1e9+7)
        
    dp[num_max][num_min] = count
        
    return count

max_xy = max(X, Y)
min_xy = min(X, Y)
if (X + Y) % 3 == 0 and (max_xy - min_xy) / min_xy <= 2:
    a = 2 * (min_xy - (max_xy - min_xy)) // 6
    num_max = a + max_xy - min_xy
    num_min = a
    print(dfs(num_max, num_min))
else:
    print(0)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def comb(n, r, p):
    x, y = 1, 1
    for i in range(n, n - r, -1):
        x *= i
        y *= i + r - n
        x %= p
        y %= p
    return pow(y, p - 2, p) * x % p

x, y = map(int, input().split())
n = (x + y) // 3
p = 10 ** 9 + 7
if (x + y) % 3 == 0:
    r = 0
    if x > y:
        x, y = y, x
    while True:
        if 2 * x == y:
            break
        r += 1
        x -= 2
        y -= 1
    print(comb(n, r, p))
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

""" 
参考:http://drken1215.hatenablog.com/entry/2018/06/08/210000
maximとmodを適宜設定。
あ入力忘れを考慮してあえて入力例通らないようにしておいたで。

combを使う前にcominit()を使う

"""
maxim = 10**7
mod = 10**9+7
fac = [None] * maxim
finv = [None] * maxim
inv = [None] * maxim

def cominit():
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1

    for i in range(2, maxim):
        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):
    if (n < k):
        return 0
    if (n < 0 or k < 0):
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


def main():
    x,y = map(int, input().split())
    if (x+y) % 3 != 0 or x/2 > y or y > 2*x:
        print(0)
        return

    # (x+y) // 3で何段目かわかる
    # パスカルの三角形で言うところのハジから何番目かがわかればいい

    # k段目の点は -x + 3*k上にある
    # 2*xが一番端にある

    if y < x:
        y,x = x,y
        # パスカルの三角形は左右対称
    
    k = (x+y) // 3
    # k段目の上端は (k, 2k)に存在する
    # 左から何番目かは2*k -yで求まる
    # 解は kC2*k-y

    cominit()
    print(comb(k, 2*k-y))


    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:


a, b = map(int, input().split())
MOD = (1e9 + 7)

def calc(x, y):
    right = above = 0
    while x>0 and y>0:
        if x>y:
            x -= 2
            y -= 1
            right += 1
        else:
            x -= 1
            y -= 2
            above += 1

    return (True, right, above) if x==0 and y==0 else (False, None, None)


def res(n, k):
    # print(n, k)
    total = 1
    if k < n-k:
        k = n-k
    for i in range(k+1, n+1):
        total = (total * i)# % MOD
    d = 1
    for i in range(1, n-k+1):
        d = (d*i) #% MOD
    return total // d

r, right, above = calc(a, b)
if not r:
    print(0)
else:
    print(int(res(above+right, right) % MOD))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
m = 10**9+7
def bfs():
    X, Y = map(int, input().split())
    que = deque([[0, 0]])
    ans = 0
    while que:
        x, y = que.popleft()
        for i, j in ([1,2], [2,1]):
            nx, ny = x+i, y+j
            if nx < X and ny < Y:
                que.append([nx, ny])
            elif nx == X and ny == Y:
                ans += 1
    return ans
print(bfs()%m)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs():
    X, Y = map(int, input().split())
    que = deque([[0, 0]])
    ans = 0
    while que:
        x, y = que.popleft()
        for i, j in ([1,2], [2,1]):
            nx, ny = x+i, y+j
            if nx < X and ny < Y:
                que.append([nx, ny])
            elif nx == X and ny == Y:
                ans += 1
    return ans
print(bfs())

Submission status: Time Limit Exceeded

Solution code:
import math
from scipy.misc import comb

#def permod(n, r):
  #return (math.factorial(n) // math.factorial(n - r)) % (10 ** 9 + 7)

def main():
  X,Y = map(int,input().split())
  
  if (X + Y) % 3 != 0:
    print(0)
    
  else:
    a = Y - (X + Y) // 3
    b = X - (X + Y) // 3
    
    total = a + b
    m = min(a,b)
    
    ans = comb(total,m,exact = True)
    print(ans)
    
main()

Submission status: Time Limit Exceeded

Solution code:
import math

def permod(n, r):
  return (math.factorial(n) // math.factorial(n - r)) % (10 ** 9 + 7)

def main():
  X,Y = map(int,input().split())
  
  if (X + Y) % 3 != 0:
    print(0)
    
  else:
    a = Y - (X + Y) // 3
    b = X - (X + Y) // 3
    
    total = a + b
    m = min(a,b)
    
    ans = permod(total,m)
    print(ans)
    
main()

Submission status: Time Limit Exceeded

Solution code:
import math

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

if (X + Y) % 3 != 0:
  print(0)
  
else:
  a = Y - (X + Y) // 3
  b = X - (X + Y) // 3
  total = a + b
  m = min(a,b)
  def permod(n, r):
    return (math.factorial(n) // math.factorial(n - r)) % (10 ** 9 + 7)
  
  ans = permod(total,m)
  print(ans)

Submission status: Time Limit Exceeded

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

def stair(n):
    m=1
    for i in range (2,n+1):
        m=m*i
    return m

def comb(n,r):
    return stair(n)//(stair(r)*stair(n-r))

if (X+Y)%3==0 and (X+Y)//3>=abs(X-Y):
    ans=comb((X+Y)//3,( (X+Y)//3 - abs(X-Y) )//2)
    print(ans%1000000009)
else:
    print(0)

Submission status: Time Limit Exceeded

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

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

cnt_d1 = 0
cnt_d2 = 0

diff = Y - X
if diff == 0:
    if X % 3 != 0:
        print(0)
        exit()
    cnt_d1 = X // 3
    cnt_d2 = cnt_d1
elif diff > 0:
    Y -= 2 * diff
    X -= 1 * diff
    if X < 0 or X % 3 != 0:
        print(0)
        exit()

    cnt_d1 = X // 3
    cnt_d2 = diff + X // 3
else:
    diff = - diff
    X -= 2 * diff
    Y -= 1 * diff
    if X < 0 or X % 3 != 0:
        print(0)
        exit()

    cnt_d1 = diff + X // 3
    cnt_d2 = X // 3

MOD = 10**9 + 7
fact = [1]
fact_inv = [1]
for i in range(cnt_d1+cnt_d2 + 10):
    new_fact = fact[-1]*(i+1) % MOD
    fact.append(new_fact)
    fact_inv.append(pow(new_fact, MOD-2, MOD))


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


print(mod_comb_k(cnt_d1+cnt_d2, cnt_d1, MOD))

'''
dp = np.array([[0] * (Y + 1) for _ in range(X + 1)], dtype=np.int64)
#dp = [np.zeros(Y+1, np.int64) for _ in range(X+1)]
print(dp)

for i in range(X):
    if i > 0:
        dp[i] = dp[i]
'''

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
def pow_with_mod(a, b, p):
    if b==0: return 1
    if b%2==0:
        d=pow_with_mod(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*pow_with_mod(a,b-1,p ))%p

def comb_with_mod(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*pow_with_mod(b,p-2,p)*pow_with_mod(c,p-2,p))%p

div = 10 ** 9 + 7
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()

ans = comb_with_mod(X+Y, X, div)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

def factorial(n):
    result = 1
    for i in range(1, n+1):
        result *= i % mod
    return result

def combinations_count(n, r):
    return factorial(n) % mod // (factorial(n - r) % mod * factorial(r) % mod)

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

if (x + y) % 3 != 0:
    print(0)
else:
    n = (2 * y - x) // 3
    m = (2 * x - y) // 3
    comb_num = combinations_count(n+m, n)
    print(comb_num)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

x, y = map(int, input().split())
if y > x:
  x, y = y, x

a = (x+y)/3
b = (2*y-x)/3
if (x+y)%3 == 0 and (2*y-x)%3 == 0 and a*b >= 0:
  answer = factorial(a) // factorial(b) // factorial(a - b)
  print(answer % (10**9+7))
else:
  print(0)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
x, y = map(int, input().split())

mod = 10**9 + 7
f = [1]
for i in range(10**6):
    f.append(f[-1] * (i+1) % mod)
    
def nCr(n, r):
    return f[n] * pow(f[r], f[r] ** (mod-2), mod) * pow(f[n-r] ** (mod-2), mod) % mod

def main():
    if (x + y) % 3 != 0 or (x + y) // 3 < abs(x - y):
        print(0)
        return

    n = (x + y) // 3
    r = n - abs(x - y)
    print(nCr(n, r))
    return
    
main()

Submission status: Time Limit Exceeded

Solution code:
#from operator import mul
from math import factorial
#from functools import reduce
X, Y = map(int, input().split())
MOD = (10 ** 9) + 7
if ((2 * X) - Y) % 3 != 0:
    print(0)
    exit()
q = ((2 * X) - Y) // 3
p = X - (2 * q)
if q < 0 or p < 0:
    print(0)
    exit()
r = max(p, q)
s = min(p, q)

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

print(comb(r+s, r, MOD) % MOD)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

if (2*Y - X) < 0:
    print(0)
elif (2*X - Y) < 0:
    print(0)
else:
    if (X - 2*Y) % 3 != 0 or (2*X - Y) % 3 != 0:
        print(0)
    else:
        a = (2 * Y - X) // 3
        b = (2 * X - Y) // 3
        m = 10**9+7
        res = 1
        for i in range(1,a+b+1):
            res = res*i%m
        for i in range(1,a+1):
            res = res*mod_inv(i,m)%m
        for i in range(1,b+1):
            res = res*mod_inv(i,m)%m
        print(res)

Submission status: Time Limit Exceeded

Solution code:
def mod_inv(a, m):
    return pow(a,m-2,m)


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

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

n = (X + Y) // 3
nx, ny = X - n, Y - n

if nx < 0 or ny < 0:
    print(0)
    exit()

ans = 1
for i in range(1, nx + ny + 1):
    ans = ans * i % MOD
for i in range(1, nx + 1):
    ans = ans * mod_inv(i, MOD) % MOD
for i in range(1, ny + 1):
    ans = ans * mod_inv(i, MOD) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb

x, y = map(int, input().split())
s, l = min(x,y), max(x,y)
if 2*s-l<0 or (2*s-l)%3!=0:
  print(0)
else:
  r = (2*s-l)//3
  n = 2*r+l-s
  print(comb(n,r,exact=True)%1000000007)

Submission status: Time Limit Exceeded

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

x, y = map(int, input().split())
s, l = min(x,y), max(x,y)
if 2*s-l<0 or (2*s-l)%3!=0:
  print(0)
else:
  r = (2*s-l)//3
  n = 2*r+l-s
  print(comb(n,r)%1000000007)

Submission status: Time Limit Exceeded

Solution code:
#拡張ユークリッド互除法
#ax+by=1の1つの解(gcd(a,b)=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 modinv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m #負の値を返さないように

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

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

if (X+Y)%3 != 0 or X*2-Y < 0:
    ans = 0
else:
    a = (2*X-Y)//3
    b = (2*Y-X)//3
    m = 10**9+7
    ans = 1
    for i in range(b+1,a+b+1):
        ans = ans*i%m
    for i in range(1,a+1):
        ans = ans*modinv(i,m)%m
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#べき乗関数powを使った逆元の計算
def modinv2(a,m):
    return pow(a,m-2,m)

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

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

if (X+Y)%3 != 0 or X*2-Y < 0:
    ans = 0
else:
    a = (2*X-Y)//3
    b = (2*Y-X)//3
    m = 10**9+7
    ans = 1
    for i in range(1,a+b+1):
        ans = ans*i%m
    for i in range(1,a+1):
        ans = ans*modinv2(i,m)%m
    for i in range(1,b+1):
        ans = ans*modinv2(i,m)%m
print(ans)

Submission status: Time Limit Exceeded

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

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


def step(x, y):
    if x == y == 0:
        return 1
    elif x < 0 or y < 0:
        return 0
    else:
        if (x, y) in d:
            return d[(x, y)]
        else:
            d[(x, y)] = step(x-1, y-2) + step(x-2, y-1)
            return d[(x, y)]


print(step(x, y))

Submission status: Time Limit Exceeded

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

m = int(1e9)+7

def fp(a, p):
	if p==0:
		return 1
	h = fp(a, p//2)
	h *= h
	h %= m
	if p % 2:
		h = h * a % m
	return h

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

	if a > b:
		tmp = a
		a = b
		b = tmp

	ans = 1
	for i in range(b+1, a+b+1):
		ans *= i
		ans %= m

	for i in range(2, a+1):
		ans *= fp(i, m-2)
		ans %= m
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial as fact

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

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

if a+2*b==x and b+2*a==y and a>=0 and b>=0:
    ans=fact(n)%mod * pow(fact(n-a),mod-2,mod)*pow(fact(a),mod-2,mod)
    print(ans%mod)
else:
    print("0")

Submission status: Time Limit Exceeded

Solution code:
M = 10 ** 9 + 7
F = [0] * 999999
I = [0] * 999999

def powM(n, k):
    global M
    result = 1
    while k > 0:
        if (k & 1) == 1:
            result = (result * n) % M
        n = (n * n) % M
        k >>= 1
    return result

def factorialM(n):
    global M, F, I
    F[0] = 1
    I[0] = 1
    for i in range(1, n+1):
        F[i] = (F[i - 1] * i) % M
        I[i] = powM(F[i], M - 2) % M

def solve(x, y):
    global M
    if (x + y) % 3 > 0:
        return 0
    n = (2 * y - x) // 3
    m = (2 * x - y) // 3
    if n < 0 or m < 0:
        return 0
    factorialM(n + m)
    return F[n + m] * (I[n] * I[m] % M) % M

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

Submission status: Time Limit Exceeded

Solution code:
M = 10 ** 9 + 7
F = []
I = []

def powM(n, k):
    global M
    result = 1
    while k > 0:
        if (k & 1) == 1:
            result = (result * n) % M
        n = (n * n) % M
        k >>= 1
    return result

def factorialM(n):
    global M, F, I
    F.append(1)
    I.append(1)
    for i in range(1, n+1):
        F.append((F[i - 1] * i) % M)
        I.append(powM(F[i], M - 2) % M)

def solve(x, y):
    global M
    if (x + y) % 3 > 0:
        return 0
    n = (2 * y - x) // 3
    m = (2 * x - y) // 3
    if n < 0 or m < 0:
        return 0
    factorialM(n + m)
    return F[n + m] * (I[n] * I[m] % M) % M

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

Submission status: Time Limit Exceeded

Solution code:
x,y=[int(i) for i in input().split()]

m=1000000007

def conbmod(a,b,m):
    ans=1
    bikkuri=1
    for i in range(b):
        ans*=(a-i)
        bikkuri*=i+1
        ans=ans%m
        bikkuri=bikkuri%m
    
    while ans%bikkuri!=0:
        ans+=m
    return int(ans/bikkuri)
    
    

if y<=2*x  and x<=2*y and (2*x-y)%3==0 and (2*y-x)%3==0:
    a=(2*y-x)//3
    b=(2*x-y)//3
    
    print(conbmod(a+b,b,m))
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
X, Y = map(int,input().split())
DIV = 10**9 + 7
#y=2x以下かつy=(1/2)x以上の位置にいなくてはいけない
N = (X+Y)//3
#NCAを求める
nkai = 1
for l in range(1,N+1):
    nkai *= l
ans = 0
if (X+Y) % 3 != 0:
    ans = 0
else:
    #操作の回数 A+B = N
    N = (X+Y) // 3
    for i in range(N+1):
        count = 0
        A = i
        B = N - i
        if (A+2*B) == X and (2*A + B) == Y:
            akai = 1
            nakai = 1
            for m in range(1,A+1):
                akai *= m
            for n in range(1,N-A+1):
                nakai *= n
            count = (nkai)//(akai*nakai)
            ans += 1*count
ans = ans % DIV
print(ans)