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: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc145/tasks/abc145_d

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

if (2*Y- X) % 3 or (2*X- Y) % 3:
    print(0)
    exit()

x = (2*Y - X) // 3
y = (2*X - Y) // 3

n = x + y
r = x


mod = 10**9 + 7
f = 1
for i in range(1, n + 1):
    f = f*i % mod
fac = f
f = pow(f, mod-2, mod)
facinv = [f]
for i in range(n, 0, -1):
    f = f*i % mod
    facinv.append(f)

print(fac * facinv[r] * facinv[n - r] % mod)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc145/tasks/abc145_d

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

if (2*Y- X) % 3 or (2*X- Y) % 3:
    print(0)
    exit()

x = (2*Y - X) // 3
y = (2*X - Y) // 3

n = x + y
r = x


mod = 10**9 + 7
f = 1
fac = [f]
for i in range(1, n + 1):
    f = f*i % mod
f = pow(f, mod-2, mod)
facinv = [f]
for i in range(n, 0, -1):
    f = f*i % mod
    facinv.append(f)

print(fac[n] * facinv[r] * facinv[n - r] % mod)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc145/tasks/abc145_d

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

if (2*Y- X) % 3 or (2*X- Y) % 3:
    print(0)
    exit()

x = (2*Y - X) // 3
y = (2*X - Y) // 3

n = x + y
r = x


mod = 10**9 + 7
f = 1
fac = [f]
for i in range(1, n + 1):
    f = f*i % mod
    fac.append(f)
f = pow(f, mod-2, mod)
facinv = [f]
for i in range(n, 0, -1):
    f = f*i % mod
    facinv.append(f)

print(fac[n] * facinv[r] * facinv[n - r] % mod)

Submission status: Runtime Error

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)
  
  # 0,0始点で，片方の操作のみを連続で行う場合
  if Y == X * 2:
    print(1)
    exit(0)
  elif X == Y * 2:
    print(1)
    exit(0)
  
  # 始点となりえる点を探索
  stack = deque((0, 0))
  while len(stack) > 0:
    start_x, start_y = stack.pop()
    if Y - start_y == (X - start_x) * 2:
      print(1)
      exit(0)
    elif X - start_x == (Y - start_y) * 2:
      print(1)
      exit(0)

    # 次の始点をスタック
    next_start_x = start_x + 3
    next_start_y = start_y + 3
    if next_start_x <= X and next_start_y <= Y:
      stack.append((next_start_x, next_start_y))
  
  # a,b始点で，片方の操作のみを連続で行う場合
  

  # 枠外は移動済みとする
  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: Runtime Error

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)
  
  # 0,0始点で，片方の操作のみを連続で行う場合
  if Y == X * 2:
    print(1)
    exit(0)
  elif X == Y * 2:
    print(1)
    exit(0)
  
  # 始点となりえる点を探索
  stack = deque([0, 0])
  while len(stack) > 0:
    start_x, start_y = stack.pop()
    if Y - start_y == (X - start_x) * 2:
      print(1)
      exit(0)
    elif X - start_x == (Y - start_y) * 2:
      print(1)
      exit(0)

    # 次の始点をスタック
    next_start_x = start_x + 3
    next_start_y = start_y + 3
    if next_start_x <= X and next_start_y <= Y:
      stack.append((next_start_x, next_start_y))
  
  # a,b始点で，片方の操作のみを連続で行う場合
  

  # 枠外は移動済みとする
  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: Runtime Error

Solution code:

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

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

if (2*X-Y)%3!=0 or (2*Y-X)%3!=0:
    print(0)
else:
    a = (2*X-Y)//3
    b = (2*Y-X)//3
    if (2*X-Y)%3!=0 or (2*Y-X)%3!=0:
        print(0)
    else:
        fact = [1]
        for n in range(1,a+b+1):
            fact.append(fact[-1]*n%MOD)
        print(ModInt(fact[a+b])/ModInt(fact[a])/ModInt(fact[b]))

Submission status: Runtime Error

Solution code:


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

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

if (2*X-Y)%3!=0 and (2*Y-X)%3!=0:
    print(0)
else:
    a = (2*X-Y)//3
    b = (2*Y-X)//3
    if a>=0 and b>=0:
        fact = [1]
        for n in range(1,a+b+1):
            fact.append(fact[-1]*n%MOD)
        print(ModInt(ModInt(fact[a+b])/ModInt(fact[a]))/ModInt(fact[a]))
    else:
        print(0)

Submission status: Runtime Error

Solution code:


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

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

if (2*X-Y)%3!=0 and (2*Y-X)%3!=0:
    print(0)
else:
    a = (2*X-Y)//3
    b = (2*Y-X)//3
    if(a>=0 and b=>0):
        fact = [1]
        for n in range(1,a+b+1):
            fact.append(fact[-1]*n%MOD)
        print(ModInt(ModInt(fact[a+b])/ModInt(fact[a]))/ModInt(fact[a]))
    else:
        print(0)

Submission status: Runtime Error

Solution code:

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

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

if (2*X-Y)%3!=0 or (2*Y-X)%3!=0:
    print(0)
else:
    a = (2*X-Y)//3
    b = (2*Y-X)//3
    fact = [1]
    for n in range(1,a+b+1):
        fact.append(fact[-1]*n%MOD)
    print(ModInt(fact[a+b])/ModInt(fact[a])/ModInt(fact[b]))

Submission status: Runtime Error

Solution code:


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

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

if (2*X-Y)%3!=0 and (2*Y-X)%3!=0:
    print(0)
else:
    a = (2*X-Y)//3
    b = (2*Y-X)//3
    fact = [1]
    for n in range(1,a+b+1):
        fact.append(fact[-1]*n%MOD)
    print((ModInt(fact[a+b])/ModInt(fact[a]))/ModInt(fact[a]))

Submission status: Runtime Error

Solution code:


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

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

if (2*X-Y)%3!=0 and (2*Y-X)%3!=0:
    print(0)
else:
    a = (2*X-Y)//3
    b = (2*Y-X)//3
    fact = [1]
    for n in range(1,a+b+1):
        fact.append(fact[-1]*n%MOD)
    print(ModInt(ModInt(fact[a+b])/ModInt(fact[a]))/ModInt(fact[a]))

Submission status: Runtime Error

Solution code:


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

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

if (2*X-Y)%3!=0 and (2*Y-X)%3!=0:
    print(0)
else:
    a = (2*X-Y)//3
    b = (2*Y-X)//3
    fact = [1]
    for n in range(1,a+b+1):
        fact.append(fact[-1]*n%MOD)
    print(ModInt(fact[a+b])/ModInt(fact[a])/ModInt(fact[b]))

Submission status: Runtime Error

Solution code:


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

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

if (2*X-Y)%3!=0 and (2*Y-X)%3!=0:
    print(0)
else:
    a = (2*X-Y)//3
    b = (2*Y-X)//3
    fact = [1]
    for n in range(1,a+b+1):
        fact.append(fact[-1]*n%MOD)
    print(ModInt(fact[a+b])/ModInt(fact[a])/ModInt(fact[a]))

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
x, y = map(int, input().split())

if (x + y) % 3 != 0 or x > 2 * y or y > 2 * x:
    print(0)
    sys.exit()

# 手数
n = (x + y) // 3
x -= n
y -= n


MOD = 10**9 + 7


def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f

    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv


fact, invs = prepare(n, MOD)

print(fact * invs[x] * invs[y] % MOD)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
x, y = map(int, input().split())

if (x + y) % 3 != 0 or x > 2 * y or y > 2 * x:
    print(0)
    sys.exit()

# 手数
n = (x + y) // 3
x -= n
y -= n


# モジュラ逆数戦法
def prepare(n, MOD):

    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f

    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return fn, invs


fact, invs = prepare(n, MOD)

print(fact * invs[x] * invs[y] % MOD)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
x, y = map(int, input().split())

if (x + y) % 3 != 0 or x > 2 * y or y > 2 * x:
    print(0)
    sys.exit()

# 手数
n = (x + y) // 3
x -= n
y -= n


# モジュラ逆数戦法
def prepare(n, MOD):
    nrt = int(n ** 0.5) + 1
    nsq = nrt * nrt
    facts = np.arange(nsq, dtype=np.int64).reshape(nrt, nrt)
    facts[0, 0] = 1
    for i in range(1, nrt):
        facts[:, i] = facts[:, i] * facts[:, i - 1] % MOD
    for i in range(1, nrt):
        facts[i] = facts[i] * facts[i - 1, -1] % MOD
    facts = facts.ravel().tolist()

    invs = np.arange(1, nsq + 1, dtype=np.int64).reshape(nrt, nrt)
    invs[-1, -1] = pow(facts[-1], MOD - 2, MOD)
    for i in range(nrt - 2, -1, -1):
        invs[:, i] = invs[:, i] * invs[:, i + 1] % MOD
    for i in range(nrt - 2, -1, -1):
        invs[i] = invs[i] * invs[i + 1, 0] % MOD
    invs = invs.ravel().tolist()

    return facts, invs


facts, invs = prepare(n, MOD)

print(facts[n] * invs[x] * invs[y] % MOD)

Submission status: Runtime Error

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

a = (4*Y-2*X)//6
b = (Y-2*X)//-3
if a == 0 and b == 0:
    print(0)
    import sys
    sys.exit()

from math import factorial
print(factorial(a+b)//factorial(a)*factorial(b)%(10e9+7))

Submission status: Runtime Error

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

# dp = [[0 for _ in range(X+1)] for __ in range(Y+1)]
# dp[1][2] = 1
# dp[2][1] = 1

# for xi in range(X + 1):
#     for yi in range(Y + 1):
#         dp[xi][yi] = dp[xi - 1][yi - 2] + dp[xi - 2][yi - 1]

# print(dp[X][Y])
import sys
sys.setrecursionlimit(100000)  # RecursionError対策

def help(x, y):
    if x < 0 or y < 0:
        return 0
    if (x == 1 and y == 2) or (x == 2 and y == 1):
        return 1
    else:
        return (help(x - 1, y - 2) + help(x - 2, y - 1))%(10e9+7)

print(help(X, Y))

Submission status: Runtime Error

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

sys.setrecursionlimit(10000)  # RecursionError対策

def help(x, y):
    if x < 0 or y < 0:
        return 0
    if (x == 1 and y == 2) or (x == 2 and y == 1):
        return 1
    else:
        return (help(x - 1, y - 2) + help(x - 2, y - 1))%(10e9+7)

print(help(X, Y))

Submission status: Runtime Error

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

# dp = [[0 for _ in range(X+1)] for __ in range(Y+1)]
# dp[1][2] = 1
# dp[2][1] = 1

# for xi in range(X + 1):
#     for yi in range(Y + 1):
#         dp[xi][yi] = dp[xi - 1][yi - 2] + dp[xi - 2][yi - 1]

# print(dp[X][Y])

def help(x, y):
    if x < 0 or y < 0:
        return 0
    if (x == 1 and y == 2) or (x == 2 and y == 1):
        return 1
    else:
        return (help(x - 1, y - 2) + help(x - 2, y - 1))%(10e9+7)

print(help(X, Y))

Submission status: Runtime Error

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

num_A, num_B = 0, 0

num_A_r = int(X/3)*2
num_A_d = int(Y/3)
num_B_r = int(X/3)
num_B_d = int(Y/3)*2

num_A = num_A_d
num_B = num_B_r
if num_A > 0 and num_B > 0:
  num_all = num_A + num_B
  num_min = min(num_A, num_B)
  total = 1
  for i in range(num_all, num_all-num_min, -1):
    total *= i
  for i in range(num_min, 0, -1):
    total /= i
  print(int(total))
else:
  print(0)

Submission status: Runtime Error

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, readline().split())

if x < y:
    x, y = y, x

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

a = x - 2 * b

MOD = 10 ** 9 + 7
a %= MOD
b %= MOD

MAX = 10 ** 6 * 2 + 2
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)

print(com(a + b, b, MOD))

Submission status: Runtime Error

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, readline().split())

if x < y:
    x, y = y, x

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

a = x - 2 * b

MOD = 10 ** 9 + 7
a %= MOD
b %= MOD

MAX = 10 ** 6 + 10
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)

print(com(a + b, b, MOD))

Submission status: Runtime Error

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, readline().split())

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

a = x - 2 * b

MOD = 10 ** 9 + 7
a %= MOD
b %= MOD

MAX = 10 ** 6 + 10
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)

print(com(a + b, b, MOD))