Problem: 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.

Submission attempts (in order):
import math
tmp = input().split()
X = int(tmp[0])
Y = int(tmp[1])

mod = 10 ** 9 + 7

if (X + Y) % 3 != 0:
    print(0)
else:
    n = (2 * Y - X) / 3
    m = Y - 2 * n
    if n < 0 or m < 0:
        print(0)
        exit()
    n %= mod
    m %= mod
    total=1
    for i in range(int(n + m), int(n), -1):
        total *= i

    m = math.factorial(m)

    total //= m
    print(total%mod)

import math
tmp = input().split()
X = int(tmp[0])
Y = int(tmp[1])

mod = 10 ** 9 + 7

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

    total //= n*m
    print(total%mod)

import math
tmp = input().split()
X = int(tmp[0])
Y = int(tmp[1])

zl = 0
lz = 0

# print(zl)
# print(lz)
x, y = 0, 0
while True:
    x += 2
    y += 1
    zl += 1

    if x >= X or y >= Y:
        x -= 2
        y -= 1
        zl -= 1
        break
# print(x)
# print(y)
# print(zl)
# print()
while True:
    x += 1
    y += 2
    lz += 1

    if x >= X or y >= Y:
        break
# print(x)
# print(y)
# print(lz)

# print()
print(int(math.factorial(zl+lz)/(math.factorial(zl)+math.factorial(lz))))

import math
tmp = input().split()
X = int(tmp[0])
Y = int(tmp[1])

mod = 10 ** 9 + 7

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


import math
tmp = input().split()
X = int(tmp[0])
Y = int(tmp[1])

mod = 10 ** 9 + 7

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


import math
tmp = input().split()
X = int(tmp[0])
Y = int(tmp[1])

mod = 10 ** 9 + 7

if (X + Y) % 3 != 0:
    print(0)
else:
    n = int((2 * Y - X) / 3)
    m = int(Y - 2 * n)
    if n < 0 or m < 0:
        print(0)
        exit()
    n %= mod
    m %= mod

    r = n
    n = n+m
    # 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(result % mod)


Verdicts: Time Limit Exceeded

Time Limit Exceeded

Wrong Answer

Time Limit Exceeded

Time Limit Exceeded

Accepted