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):
inf = 10**9+7
import sys
a = 0
def nCr(n, r):
    r = min(r, n - r)
    if r == 0: return 1;
    if r == 1: return n;
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i 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 = (result * numerator[k])%inf
    return result

x, y = map(int, input().split())
key = 0
if x == 2*y:
    print(1)
    sys.exit()
if y == 2*x:
    print(1)
    sys.exit()
while x>0 and y>0:
    x, y = x-3, y-3
    key += 1
    print(x/y)
    if x == 2*y:
        a = 1
        break
    if y == 2*x:
        a = -1
        break

if x < 0 or y < 0:
    print(0)
    sys.exit()
if a == 0:
    print(0)
    sys.exit()
if a == 1:
    print(int(nCr(key*2+y ,key)))
else:
    print(int(nCr(key*2+x ,key)))

inf = 10**9+7
import sys

def nCr(n, r):
    r = min(r, n - r)
    if r == 0: return 1;
    if r == 1: return n;
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i 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 = (result * numerator[k])%inf
    return result

x, y = map(int, input().split())
key = 0
if x == 2*y:
    print(1)
    sys.exit()
if y == 2*x:
    print(1)
    sys.exit()
while x>0 and y>0:
    x, y = x-3, y-3
    key += 1
    print(x/y)
    if x == 2*y:
        a = 1
        break
    if y == 2*x:
        a = -1
        break

if x < 0 or y < 0:
    print(0)
    sys.exit()
if not a:
    print(0)
if a == 1:
    print(int(nCr(key*2+y ,key)))
else:
    print(int(nCr(key*2+x ,key)))

import sys

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

inf = 10**9+7

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

if a<0 or b<0:
    print(0)
    sys.exit()

def nCr(n, r):
    r = min(r, n - r)
    if r == 0: return 1;
    if r == 1: return int(n%inf);
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i 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 = (result*numerator[k])%inf
    return int(result)

print(nCr(a+b, a))

Verdicts: Runtime Error

Runtime Error

Accepted