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: Wrong Answer

Solution code:
x,y = map(int,input().split())
n = 0
mod = 10**9+7
ans = 0
if not (x+y)%3:
  n = (x+y)//3
  x-=n
  y-=n
  if x>0 or y>0:
    ans = 1
    for i in range(x):
      ans = ans*(n-i)*pow(i+1,mod-2,mod)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
MOD=10**9+7

def cmb(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    """
    階乗テーブル、逆元の階乗テーブルを作成する
    """
    fac = [1, 1] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac
    
x,y=map(int,input().split())

fac,ifac=make_tables(MOD,10**6)

if (2*x-y)%3==0 and (2*y-x)%3==0:
	a=(2*y-x)//3
	print(cmb((x+y)//3,a,MOD,fac,ifac))
else:
	print(0)

Submission status: Wrong Answer

Solution code:
# nCr
# 駄目な場合を考える
# - x+yが3の倍数でない
# - min(x,y):max(x,y)が倍より大きい
x, y = map(int, input().split())
x, y = max(x, y), min(x, y)
if (x + y) % 3 != 0 or (min(x, y) / max(x, y)) > 2.0:
    print(0)
    exit()


def nCr(n, r):
    res = 1
    for i in range(1, r + 1):
        res = res * (n - i + 1) // i
        res %= 10 ** 9 + 7
    return res


# x, yがそれぞれ何回ずつ2と1を使うか -> 片方が決まれたば一意に定まる
# 適当な連立方程式
# 2n+m = X, n+2m = Y: m = (X-2n), n + 2X - 4n = 2X-3n = Y, n = (2X-Y)/3
# なぜか最後のテストケースが通らない ジャッジのバグでは？
p = (2 * x - y) // 3
q = x - 2 * p

print(nCr(p + q, p))

Submission status: Wrong Answer

Solution code:
M = 10 ** 9 + 7
X, Y = map(int, input().split())

def f(n):
  if n == 0: return 1
  res = 1
  for i in range(1,n+1):
    res = (res * i) % M
  return res % M

def pow(x, n):
  res = 1
  while n:
    if (n & 1) == 1:
      res = res * x % M
    x = x * x % M
    n = n >> 1
  return res

def c(n,r):
  if r == 0 or r == n:
    res = 1
  elif r == 1 :
    res = n
  else:
    res = f(n) * pow(f(r), M-2) * pow(f(n-r), M-2)
  return res % M

if (X+Y) % 3 != 0:
  ans = 0
else:
  a = 0
  b = (X+Y)//3
  if X < Y: X, Y = Y, X
  a = X - Y
  a += (2*Y-X)//3
  if 2*Y - X <= 0:
    ans = 0
  else:
    ans = c(b, a) % M
print (ans)

Submission status: Wrong Answer

Solution code:
M = 10 ** 9 + 7
X, Y = map(int, input().split())

def f(n):
  if n == 0: return 1
  res = 1
  for i in range(1,n+1):
    res = (res * i) % M
  return res % M

def pow(x, n):
  res = 1
  while n:
    if (n & 1) == 1:
      res = res * x % M
    x = x * x % M
    n = n >> 1
  return res

def c(n,r):
  if r == 0 or r == n:
    res = 1
  elif r == 1 :
    res = n
  else:
    res = f(n) * pow(f(r), M-2) * pow(f(n-r), M-2)
  return res % M

if (X+Y) % 3 != 0:
  ans = 0
else:
  a = 0
  b = (X+Y)//3
  if X < Y: X, Y = Y, X
  a = X - Y
  a += (2*Y-X)//3
  ans = c(b, a) % M
print (ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
X, Y = map(int, input().split())
mod = 10 ** 9 + 7
for t in range(X + Y + 1):
  if t == X + Y:
    print(0)
    exit(0)
  if X + Y - 2 * t == t:
    X -= t
    Y -= t
    break
if X <= 0 or (Y <= 0):
  print(0)
  exit(0)
class Factorial:
  def __init__(self, n, mod):
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod
f = Factorial(X + Y, mod)
#print(X, Y)
print(f.combi(X + Y, X))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
X, Y = map(int, input().split())
mod = 10 ** 9 + 7
class Factorial:
  def __init__(self, n, mod):
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod
f = Factorial(X + Y, mod)
if (X + Y) % 3: print(0)
else: print(f.combi((X + Y) // 3, X // 3))

Submission status: Wrong Answer

Solution code:
mod = 10**9+7
X,Y = map(int,input().split())

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

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

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

def pow_mod(x,n):
    if n==0:
        return 1
    
    K = 1
    while n>1:
        if n%2 != 0:
            K *= x
            K %= mod
        x *= x
        x %= mod
        n //= 2

    return K*x

def n_C_k(n,k,mod):
    factorial_n = factorial_mod(n,mod)
    factorial_k = factorial_mod(k,mod)
    factorial_nk = factorial_mod(n-k,mod)
    conbi=factorial_n*pow_mod(factorial_nk,mod-2)*pow_mod(factorial_k,mod-2)
    return conbi%mod

print(n_C_k(x+y,x,mod))

Submission status: Wrong Answer

Solution code:

def cmb(n, r):
    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

# x軸側にr回、y軸側にl回動くとすると、最終的な到達マスは
# (x,y) = (2r+l, r+2l)
# 2r + l == X
# r + 2l == Y
# ∴ r = (2X-Y)/3, l = (2Y-X)/3 
def main():

    X,Y = [int(i) for i in input().split(" ")]

    # そもそも到達不可能
    if (2*X-Y) < 0 or (2*Y-X) < 0 or (2*X-Y)%3 > 0 or (2*Y-X)%3 > 0:
        print(0)
        return 0

    # コンビネーション計算
    else:
        r = (2*X-Y)//3
        l = (2*Y-X)//3
        n = r+l
        print(r, l, n)

        a = cmb(n,r)
        print(a%(int(1e9+7)))
        return 0


main()

Submission status: Wrong Answer

Solution code:

def cmb(n, r):
    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

# x軸側にr回、y軸側にl回動くとすると、最終的な到達マスは
# (x,y) = (2r+l, r+2l)
# 2r + l == X
# r + 2l == Y
# ∴ r = (2X-Y)/3, l = (2Y-X)/3 
def main():

    X,Y = [int(i) for i in input().split(" ")]

    # そもそも到達不可能
    if (2*X-Y)%3 > 0 or (2*Y-X)%3 > 0:
        print(0)
        return 0

    # コンビネーション計算
    else:
        r = (2*X-Y)//3
        l = (2*Y-X)//3
        n = r+l

        a = cmb(n,r)
        print(a%(int(1e9+7)))
        return 0


main()

Submission status: Wrong Answer

Solution code:
MOD = 7+1000000000

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

def solve():
  X,Y = map(int,input().split())
  if (X+Y)%3:
    return -1
  if (2*X-Y)%3:
    return -1
  m = (2*X-Y)//3
  n = X - 2*m
  if m < 0 or n < 0:
    return -1
  from itertools import combinations
  return (combination(m+n,m))

print(solve())

Submission status: Wrong Answer

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

def cmb(n, r):
    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):
        result %= 10 ** 9 + 7
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

x, y = readmi()
if (x + y) % 3 != 0:
    print(0)
else:
    n = (x + y) // 3
    x -= n
    y -= n
    if x < 0 or y < 0:
        print(0)
    else:
        a = cmb(x + y, x)
        print(a)

Submission status: Wrong Answer

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(nx + 1, nx + ny + 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: Wrong Answer

Solution code:
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
    return [w[0], w[1]]


def mod_inv(a, m):
    x = extgcd(a, m)[0]
    return (m + x % m) % 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

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: Wrong Answer

Solution code:
def num_combinations_mod2(n, r, mod=10 ** 9 + 7):
    # mod must be a prime.
    # nCr = (n! / (n-r)!) * (r!)^-1
    # a = n! / (n-r)!
    # b = (r!)^-1
    if r > n:
        return 0
    if r < 0 and n < 0:
        return 0
    r = min(r, n - r)
    a = 1
    b = 1
    for i in range(1, r + 1):
        a = a * (n + 1 - i) % mod
        b = b * i % mod
    return a * pow(b, mod - 2, mod) % mod


def main(x, y):
    if (x + y) % 3 != 0:
        return 0

    total = (x + y) // 3
    n = (2 * x - y) // 3
    m = total - n
    answer = num_combinations_mod2(m+n, n, 10**9+7)
    return answer


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

Submission status: Wrong Answer

Solution code:
def num_combinations_mod2(n, r, mod=10 ** 9 + 7):
    # mod must be a prime.
    # nCr = (n! / (n-r)!) * (r!)^-1
    # a = n! / (n-r)!
    # b = (r!)^-1
    r = min(r, n - r)
    a = 1
    b = 1
    for i in range(1, r + 1):
        a = a * (n + 1 - i) % mod
        b = b * i % mod
    return a * pow(b, mod - 2, mod) % mod


def main(x, y):
    if (x + y) % 3 != 0:
        return 0

    total = (x + y) // 3
    n = (2 * x - y) // 3
    m = total - n
    answer = num_combinations_mod2(m+n, n, 10**9+7)
    return answer


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

Submission status: Wrong Answer

Solution code:
def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(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 factorials, invs

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

if (x+y) % 3 != 0:
    print(0)
else:
    mod = int(1e9 + 7)
    n = (2*y - x) // 3
    m = y - 2 * n
    print(n, m)
    if n < 0 or m < 0:
        print(0)
    else:
        factorials, invs = prepare(n+m, mod)
        ans = 1
        ans = ans * factorials[n+m] % mod
        ans = ans * invs[n] % mod
        ans = ans * invs[m] % mod
        print(ans)

Submission status: Wrong Answer

Solution code:
def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(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 factorials, invs

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

if ((x+y) % 3 != 0) or (2 * x < y):
    print(0)
else:
    mod = int(1e9 + 7)
    n = (2*y - x) // 3
    m = y - 2 * n
    print(n, m)
    if n < 0 or m < 0:
        print(0)
    else:
        factorials, invs = prepare(n+m, mod)
        ans = 1
        ans = ans * factorials[n+m] % mod
        ans = ans * invs[n] % mod
        ans = ans * invs[m] % mod
        print(ans)

Submission status: Wrong Answer

Solution code:
mod = 1000000007
x, y = map(int, input().split())
x, y = min(x, y), max(x, y)

if (2*x-y)%3 != 0:
  print(0)
else:
  b = (2*x-y)//3
  a = x - 2*b
  afact, bfact, abfact = 1, 1, 1
  for i in range(1, a+1):
    afact = (afact * i)%mod
  for i in range(1, b+1):
    bfact = (bfact * i)%mod
  for i in range(1, a+b+1):
    abfact = (abfact * i)%mod
    
  print((abfact * pow(afact, mod-2, mod) * pow(bfact, mod-2, mod))%mod)

Submission status: Wrong Answer

Solution code:
mod = 1000000007
x, y = map(int, input().split())
x, y = min(x, y), max(x, y)
d = y - x
a, b = d + (x-d)%3 + (x-d)//3, (x-d)//3
if a + 2*b != x or 2*a + b != y:
  print(0)
else:
  afact, bfact, abfact = 1, 1, 1
  for i in range(1, a+1):
    afact = (afact * i)%mod
  for i in range(1, b+1):
    bfact = (bfact * i)%mod
  for i in range(1, a+b+1):
    abfact = (abfact * i)%mod
    
  print((abfact * pow(afact, mod-2, mod) * pow(bfact, mod-2, mod))%mod)

Submission status: Wrong Answer

Solution code:
import numpy as np
from math import factorial
from operator import mul
from functools import reduce

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
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 for_factorial(n):
    val = 1
    for i in range(2, n + 1):
        val *= i
    return val % divisor 

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

points = np.array([[1, 2], [2, 1]])
values = np.array([x, y])
a, b = np.linalg.solve(points, values).tolist()

if a.is_integer() and b.is_integer():
  a = int(a)
  b = int(b)
  print(a, b)

  r = a if a < b else b

  print(cmb(a+b, r, 10 ** 9 + 7))

else:
    print(0)

Submission status: Wrong Answer

Solution code:
# ABC-145-D
X, Y = map(int, input().split())
ans = 0
mod = 10**9 + 7

# 組み合わせを出す関数
# https://qiita.com/derodero24/items/91b6468e66923a87f39f
def cmb(n, r):
    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

if (X + Y) % 3 != 0: 
    ans = 0
else:
    #(+1,+2)を行う回数nを求める。
    n = (2*Y - X)//3
    #(+2,+1)を行う回数mを求める。    
    m = Y - 2*n
    ans = cmb(n+m, n)
    
print(ans%mod)

Submission status: Wrong Answer

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

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

i=(2*Y-X)//3
j=(2*X-Y)//3

def m_pow(n,m):
    ret = 1
    while m:
        if m&1:
            ret=ret*n%MOD
        n=n*n%MOD
        m>>=1
    return ret

def m_fact(n):
    if n==0:
        return 1
    ret = 1
    for i in range(1,n+1):
        ret=ret*i%MOD
    return ret

def m_comb(n,k):
    return m_fact(n) * m_pow(m_fact(k), MOD-2) * m_pow(m_fact(n-k), MOD-2) %MOD

print(m_comb(i+j,min(i,j)))

Submission status: Wrong Answer

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

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

i=(2*Y-X)//3
j=(2*X-Y)//3

def m_pow(n,m):
    ret = 1
    while m:
        if m&1:
            ret*=ret*n%MOD
        n=n*n%MOD
        m>>=1
    return ret

def m_fact(n):
    if n==0:
        return 1
    ret = 1
    for i in range(1,n+1):
        ret=ret*i%MOD
    return ret

def m_comb(n,k):
    return m_fact(n) * m_pow(m_fact(k), MOD-2) * m_pow(m_fact(n-k), MOD-2) %MOD

print(m_comb(i+j,min(i,j)))

Submission status: Wrong Answer

Solution code:
# 二項係数を"やるだけ"にしてくれるライブラリ
from collections import Counter
MAX = 1000010
MOD = 10**9+7
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX


# テーブルを作る前処理
def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD


# 二項係数計算
def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD


# 前処理完了
COMinit()

X, Y = map(int, input().split())
ans = 0
if (X+Y) % 3 != 0:
    print(0)
else:
    ans = 0
    # Aの操作: (i, j) -> (i+1, j+2)
    # Bの操作: (i, j) -> (i+2, j+1)
    # Aの操作回数を決め打ちする
    for i in range(X):
        x, y = X, Y
        # iがAの操作回数
        x -= i
        y -= i*2
        if x < 0 or y < 0:
            continue
        if x == 0 and y == 0:
            continue
        # この状態で残りのxがyの2倍あるならBの操作だけで到達できる
        if x == y*2:
            # Bの操作の回数はy回数
            ans += (COM(i+y, i) + MOD) % MOD

    print((ans+MOD) % MOD)

Submission status: Wrong Answer

Solution code:
# 二項係数を"やるだけ"にしてくれるライブラリ
from collections import Counter
MAX = 1000010
MOD = 10**9+7
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX


# テーブルを作る前処理
def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD


# 二項係数計算
def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD


# 前処理完了
COMinit()

X, Y = map(int, input().split())
ans = 0
if (X+Y) % 3 != 0:
    print(0)
else:
    ans = 0
    # Aの操作: (i, j) -> (i+1, j+2)
    # Bの操作: (i, j) -> (i+2, j+1)
    # Aの操作回数を決め打ちする
    for i in range(X):
        x, y = X, Y
        # iがAの操作回数
        x -= i
        y -= i*2
        if x < 0 or y < 0:
            continue
        if x == 0 and y == 0:
            continue
        # この状態で残りのxがyの2倍あるならBの操作だけで到達できる
        if x == y*2:
            # Bの操作の回数はy回数
            ans += COM(i+y, i)

    print(ans % MOD)

Submission status: Wrong Answer

Solution code:
# 二項係数を"やるだけ"にしてくれるライブラリ
from collections import Counter
MAX = 1000010
MOD = 10**9+7
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX


# テーブルを作る前処理
def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD


# 二項係数計算
def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD


# 前処理完了
COMinit()

X, Y = map(int, input().split())
ans = 0
if (X+Y) % 3 != 0:
    print(0)
else:
    ans = 0
    # Aの操作: (i, j) -> (i+1, j+2)
    # Bの操作: (i, j) -> (i+2, j+1)
    # Aの操作回数を決め打ちする
    for i in range(X):
        x, y = X, Y
        # iがAの操作回数
        x -= i
        y -= i*2
        # この状態で残りのxがyの2倍あるならBの操作だけで到達できる
        if x == y*2:
            # Bの操作の回数はy回数
            ans += COM(i+y, i)

    print(ans % MOD)

Submission status: Wrong Answer

Solution code:
mod = 10**9+7

def pow(n, x):
  if x == 0:
    return 1
  elif x % 2 == 0:
    return pow(n * n % mod, x // 2)
  else:
    return n * pow(n * n % mod, x // 2) % mod

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

x, y = map(int, input().split())
m = abs(x - y)
n = (x + y) // 3
if (x + y) % 3 == 0 and n >= m:
  print(comb(n, n // 2 + m))
else:
  print(0)

Submission status: Wrong Answer

Solution code:
mod = 10**9+7

def pow(n, x):
  if x == 0:
    return 1
  elif x % 2 == 0:
    return pow(n * n % mod, x // 2)
  else:
    return n * pow(n * n % mod, x // 2) % mod

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

x, y = map(int, input().split())
n = (x + y) // 3 - abs(x - y)
if (x + y) % 3 == 0 and n >= 0:
  print(comb(n, n // 2))
else:
  print(0)

Submission status: Wrong Answer

Solution code:
X, Y = map(int,input().split())
def combination(n,r,mod=10**9+7):
    n1 = n+1
    r = min(r,n-r)
    numer = denom = 1
    for i in range(1,r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom,mod-2,mod) % mod

#y=2x以下かつy=(1/2)x以上の位置にいなくてはいけない
if (X+Y) % 3 != 0:
    ans = 0
else:
    N = (X+Y)//3
    r = Y - N
    ans = combination(N,r)
print(ans)

Submission status: Wrong Answer

Solution code:
X, Y = map(int,input().split())
DIV = 10**9 + 7
def combination(n,r,mod=DIV):
    n1 = n
    r = min(r,n-r)
    numer = denom = 1
    for i in range(1,r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom,mod-2,mod) % mod

#y=2x以下かつy=(1/2)x以上の位置にいなくてはいけない
N = (X+Y)//3
ans = 0
if (X+Y) % 3 != 0:
    ans = 0
else:
    r = Y - N
    ans = combination(N,r)
print(ans)

Submission status: Wrong Answer

Solution code:
def cmb(n, r):
    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

def run():
  X, Y = map(int, input().split())
  b = X+Y
  if b%3 != 0:
    print(0)
    exit()
  x = b//3
  i = X - x
  if i > x//2:
    i = x - i
  ans = cmb(x, i)
  mod=10**9+7
  print(ans%(mod))
  
if __name__ == '__main__':
  run()

Submission status: Wrong Answer

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

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

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

if (2*y-x)%3!=0 or (2*x-y)%3!=0:
    print(0)
else:
    k=(2*y-x)//3
    l=(2*x-y)//3
    a = combination(k+l,l,10**9+7)
    print(a)

Submission status: Wrong Answer

Solution code:
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

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

if (2*y-x)%3!=0 or (2*x-y)%3!=0:
    print(0)
else:
    k=(2*y-x)//3
    l=(2*x-y)//3
    a = combination(k+l,l,10**9+7)
    print(a)

Submission status: Wrong Answer

Solution code:
import collections
import math
import operator as op
from functools import reduce

import numpy as np

MOD = 10**9 + 7

# def nCr(n, r):
#     r = min(r, n-r)
#     numer = reduce(op.mul, range(n, n-r, -1), 1)
#     denom = reduce(op.mul, range(1, r+1), 1)
#     return numer // denom


def nCr(n, r, mod=MOD):
    r = min(r, n-r)
    numer, denom = 1, 1
    for i in range(1, r + 1):
        numer = (numer * (n + 1 - i)) % mod
        denom = (denom * i) % mod
    return numer * pow(denom, mod - 2, mod) % mod


# def nCr(n, r):
#     r = min(r, n-r)
#     numer = reduce(op.mul, range(n, n-r, -1), 1)
#     denom = reduce(op.mul, range(1, r+1), 1)
#     return numer // denom

# cache = {}
# def nCr(n, r):
#     r = min(r, n-r)
#     if (n, r) in cache:
#         return cache[(n, r)]

#     if r == 0:
#         ret = 1
#     if n == r:
#         ret = 1
#     else:
#         ret = (nCr(n-1, r-1) + nCr(n-1, r)) % MOD

#     cache[(n, r)] = ret
#     return ret


def main():
    X, Y = list(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
        print(nCr(a+b, a) % MOD)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections
import math
import operator as op
from functools import reduce

import numpy as np

MOD = 10**9 + 7

def nCr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer // denom



# def nCr(n, r):
#     r = min(r, n-r)
#     numer = reduce(op.mul, range(n, n-r, -1), 1)
#     denom = reduce(op.mul, range(1, r+1), 1)
#     return numer // denom

# cache = {}
# def nCr(n, r):
#     r = min(r, n-r)
#     if (n, r) in cache:
#         return cache[(n, r)]

#     if r == 0:
#         ret = 1
#     if n == r:
#         ret = 1
#     else:
#         ret = (nCr(n-1, r-1) + nCr(n-1, r)) % MOD

#     cache[(n, r)] = ret
#     return ret


def main():
    X, Y = list(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
        print(nCr(a+b, a)%MOD)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math

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

m = (2*x - y)//3
n = (x - (4*x - 2*y)//3)

if m < 0 or n < 0 or (x+y)%3 == 1:
	print(0)
else:
	print(math.factorial(m+n) // (math.factorial(m+n - n) * math.factorial(n)) % (10**9+7))

Submission status: Wrong Answer

Solution code:
X, Y = map(int,input().split())
n = (2*Y-X)/3
m = (2*X-Y)/3
if n < 0 or m < 0:
  print(0)
  exit()
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(int(r)):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res
print(combination(n+m, n))

Submission status: Wrong Answer

Solution code:
X, Y = map(int,input().split())
n = (2*Y-X)/3
m = (2*X-Y)/3
if isinstance(n, float) or isinstance(m, float):
  print(0)
  exit()
if n < 0 or m < 0:
  print(0)
  exit()
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res
print(combination(int(n)+int(m), int(n)))

Submission status: Wrong Answer

Solution code:
X, Y = map(int,input().split())
n = (2*Y-X)/3
m = (2*X-Y)/3
if n < 1 and m < 1 :
  print(0)
  exit()
if n < 0 or m < 0:
  print(0)
  exit()
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res
print(combination(int(n)+int(m), int(n)))

Submission status: Wrong Answer

Solution code:
X, Y = map(int,input().split())
n = (2*Y-X)/3
m = (2*X-Y)/3
if n < 1 and m < 1:
  print(0)
  exit()
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res
print(combination(int(n)+int(m), int(n)))

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce
X, Y = map(int,input().split())
n = (2*Y-X)//3
m = (2*X-Y)//3
def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom
print(0 if n< 0 or m < 0 else combinations_count(n+m, n)%(10**9+7))

Submission status: Wrong Answer

Solution code:
mod = 10**9+7

frac = [1] * 2000000

for i in range(2,2000000):
    frac[i] = frac[i-1] * i % mod

def combi(n,k):
    a = frac[n]
    b = modpow(frac[k],mod-2)
    c = modpow(frac[n-k],mod-2)
    return a*b*c%mod

def bi(x):
    o = []
    while x != 0:
        o.append(x%2)
        x //= 2
    return o

def modpow(m,n):
    o = bi(n)
    p = [m]
    leo = len(o)
    while leo > len(p):
        a = p[-1]
        p.append(a*a%mod)
    b = 1
    for i in range(leo):
        if o[i] == 1:
            b *= p[i]
            b %= mod
    return b

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

A = (-1) * X +   2  * Y
B =   2  * X + (-1) * Y

if A % 3 or B % 3:
    print(0)
    exit()

A //= 3
B //= 3

print(combi(A+B,min(A,B)))