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):
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
from functools import reduce
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm_base(a, b):
    return (a * b) // gcd(a, b)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def nCr(n,r):
  bunshi = 1
  bunbo = 1
  for i in range(r):
    bunshi = (bunshi * (n-i)) % MOD
    bunbo = (bunbo * (i+1)) % MOD
  return bunshi * pow(bunbo, MOD - 2, MOD) % MOD


def main():
  X, Y = map(int, readline().split())
  if (x + y) % 3 != 0 or (2 * x - y) % 3 != 0 or (2 * y - x) % 3 != 0:
    print(0)
    sys.exit()
  else:
    n = (2*Y - X)//3
    m = (2*X - Y)//3
    ans = nCr(n+m, n)
  print(ans%MOD)
  
  
  
if __name__ == '__main__':
  main()

from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
from functools import reduce
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm_base(a, b):
    return (a * b) // gcd(a, b)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def nCr(n,r):
  bunshi = 1
  bunbo = 1
  for i in range(r):
    bunshi = (bunshi * (n-i)) % MOD
    bunbo = (bunbo * (i+1)) % MOD
  return bunshi * pow(bunbo, MOD - 2, MOD) % MOD


def main():
  X, Y = map(int, readline().split())
  if (X+Y)%3 != 0:
    ans = 0
  else:
    n = (2*Y - X)//3
    m = (2*X - Y)//3
    ans = nCr(n+m, n)
  print(ans)
  
  
  
if __name__ == '__main__':
  main()

from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
from functools import reduce
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm_base(a, b):
    return (a * b) // gcd(a, b)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def nCr(n,r):
  bunshi = 1
  bunbo = 1
  for i in range(r):
    bunshi = (bunshi * (n-i)) % MOD
    bunbo = (bunbo * (i+1)) % MOD
  return bunshi * pow(bunbo, MOD - 2, MOD) % MOD


def main():
  X, Y = map(int, readline().split())
  if (X+Y)%3 != 0:
    ans = 0
  else:
    n = (2*Y - X)//3
    m = (2*X - Y)//3
    ans = nCr(n+m, n)
  print(ans%MOD)
  
  
  
if __name__ == '__main__':
  main()

from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
from functools import reduce
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm_base(a, b):
    return (a * b) // gcd(a, b)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def nCr(n,r):
  bunshi = 1
  bunbo = 1
  for i in range(r):
    bunshi = (bunshi * (n-i)) % MOD
    bunbo = (bunbo * (i+1)) % MOD
  return bunshi * pow(bunbo, MOD - 2, MOD) % MOD


def main():
  X, Y = map(int, readline().split())
  if (X + Y) % 3 != 0 or (2 * X - Y) % 3 != 0 or (2 * Y - X) % 3 != 0:
    print(0)
    sys.exit()
  else:
    n = (2*Y - X)//3
    m = (2*X - Y)//3
    ans = nCr(n+m, n)
  print(ans%MOD)
  
  
  
if __name__ == '__main__':
  main()

import sys
import numpy as np

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    X, Y = map(int, readline().split())
    if X%3==Y%3==1 or X%3==Y%3==2:
        print(0)
        sys.exit()
    a = (2*Y-X)//3
    b = (2*X-Y)//3


    N = a+b
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]

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

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

    print(cmb(N, a, MOD))


if __name__ == '__main__':
    main()


Verdicts: Runtime Error

Wrong Answer

Wrong Answer

Wrong Answer

Accepted