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: Accepted

Solution code:
from functools import reduce

MOD = 1000000007

def comb(n, r):
    if n < 0 or r < 0 or r > n:
        return 0
    r = min(r, n - r)
    if r == 0: return 1

    numer = [n - r + i + 1 for i in range(r)]
    denom = [i + 1 for i in range(r)]

    for i in range(1, r):
        divisor = denom[i]
        if divisor > 1:
            offset = (n - r) % (i + 1)
            for j in range(i, r, i+1):
                numer[j - offset] //= divisor
                denom[j] //= divisor

    res = 1
    for i in range(r):
        if numer[i] > 1:
            res *= numer[i]
    return res

    # return reduce(lambda x, y: x*y if y > 1 else x, numer)

def main():
    x, y = map(int, input().split())
    ans = 0
    if (x+y)%3==0 and x <= 2*y <= 4*x:
        n = (x + y) // 3
        r = y - n
        ans = comb(n, r) % MOD
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from functools import reduce

MOD = 1000000007

def comb(n, r):
    if n < 0 or r < 0 or r > n:
        return 0
    r = min(r, n - r)
    if r == 0: return 1

    numer = [n - r + i + 1 for i in range(r)]
    denom = [i + 1 for i in range(r)]

    for i in range(1, r):
        divisor = denom[i]
        if divisor > 1:
            offset = (n - r) % (i + 1)
            for j in range(i, r, i+1):
                numer[j - offset] //= divisor
                denom[j] //= divisor

    # res = 1
    # for i in range(r):
    #     if numer[i] > 1:
    #         res *= numer[i]
    # return res

    return reduce(lambda x, y: x*y if y > 1 else x, numer)
    # return reduce(mul, numer)

def main():
    x, y = map(int, input().split())
    ans = 0
    if (x+y)%3==0 and x <= 2*y <= 4*x:
        n = (x + y) // 3
        r = y - n
        ans = comb(n, r) % MOD
    print(ans)

if __name__ == "__main__":
    import sys
    if sys.platform =='ios':
        sys.stdin=open('in.txt')
    sys.setrecursionlimit(10**6)
    main()

Submission status: Accepted

Solution code:
from sys import exit


def mpow(x, n):
    result = 1
    while n != 0:
        if n & 1 == 1:
            result *= x
            result %= 1000000007
        x *= x
        x %= 1000000007
        n >>= 1
    return result


def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0

    fac = [0] * (n + 1)
    fac[0] = 1
    for i in range(n):
        fac[i + 1] = fac[i] * (i + 1) % p
    return fac[n] * mpow(fac[n - k], p - 2) * mpow(fac[k], p - 2) % p


p = 1000000007

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

if (X+Y) % 3 != 0:
    print(0)
    exit()

a = (2 * Y - X) // 3
b = (2 * X - Y) // 3

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

print(mcomb(a + b, min(a, b)))

Submission status: Accepted

Solution code:
from sys import exit


def mpow(x, n):
    result = 1
    while n != 0:
        if n & 1 == 1:
            result *= x
            result %= 1000000007
        x *= x
        x %= 1000000007
        n >>= 1
    return result


p = 1000000007

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

if (X+Y) % 3 != 0:
    print(0)
    exit()

a = (2 * Y - X) // 3
b = (2 * X - Y) // 3

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

n = a + b
k = min(a, b)

if n == 0 and k == 0:
    print(1)
    exit()

if n < k or k < 0:
    print(0)
    exit()

fac = [0] * (n + 1)
fac[0] = 1
for i in range(n):
    fac[i + 1] = fac[i] * (i + 1) % p
print(fac[n] * mpow(fac[n - k], p - 2) * mpow(fac[k], p - 2) % p)

Submission status: Accepted

Solution code:
#coding:utf-8
x, y = map(int, input().split())

mod = 10**9 + 7
f = [1]
for i in range(10**6):
    f.append(f[-1] * (i+1) % mod)
    
def nCr(n, r):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

def main():
    if (x + y) % 3 != 0 or (x + y) // 3 < abs(x - y):
        print(0)
        return
    
    n = (x + y) // 3
    r = n // 2 - abs(x-y) // 2
    print(nCr(n, r))
    return
    
main()

Submission status: Accepted

Solution code:
import math
import os
import sys
# from fractions import gcd
input = sys.stdin.readline

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル


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


def main():
    X, Y = list(map(int, input().split()))
    N = (2 * Y - X) / 3
    M = (2 * X - Y) / 3

    if not (N.is_integer() and M.is_integer()):
        print(0)
        return

    N = int(N)
    M = int(M)

    for i in range(2, M + N + 1):
        g1.append((g1[-1] * i) % MOD)
        inverse.append((-inverse[MOD % i] * (MOD//i)) % MOD)
        g2.append((g2[-1] * inverse[-1]) % MOD)

    print(cmb(N+M, M, MOD))


if __name__ == '__main__':
    main()

Submission status: Accepted

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 and y>=0:
    ans = 1
    for i in range(x):
      ans = ans*(n-i)*pow(i+1,mod-2,mod)%mod
print(ans)

Submission status: Accepted

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 not 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: Accepted

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
	b=(2*x-y)//3
	if a>=0 and b>=0:
		print(cmb((x+y)//3,a,MOD,fac,ifac))
	else:
		print(0)
else:
	print(0)

Submission status: Accepted

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

# なぜかいつものこれだと99999で違った出力になりWAなる
# 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を使うか -> 片方が決まれたば一意に定まる
# 適当な連立方程式
n = (x + y) // 3
p = (n - abs(x - y)) // 2
# print(n, p)
# print(nCr(n, p))


# なんでWAになるんだろうね ググった


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)

print(cmb(n, p, mod))

Submission status: Accepted

Solution code:
from operator import mul
from math import factorial
from functools import reduce

def modpow(a, n, mod): # a^n mod
    result = 1
    while n > 0:
        if n & 1: result = result * a % mod
        a = a * a % mod
        n >>= 1
    return result

X, Y = map(int, input().split())
MOD = (10 ** 9) + 7
if ((2 * X) - Y) % 3 != 0:
    print(0)
    exit()
q = ((2 * X) - Y) // 3
p = X - (2 * q)
if q < 0 or p < 0:
    print(0)
    exit()
r = max(p, q)
s = min(p, q)

over = 1
for i in range(2,r+s+1):
    over = (over * i) % MOD
under = 0
e = 1
f = 1
for i in range(2,s+1):
    e = (e * i) % MOD
for i in range(2,r+1):
    f = (f * i) % MOD
under = e * f

result = (over * modpow(under, MOD-2, MOD) % MOD)
print(result)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def C(n,r):
    return fact[n]*pow(fact[n-r],mod-2,mod)*pow(fact[r],mod-2,mod) % mod

x,y = LI()

fact = [1]*(x+y)
for i in range(1,x+y):
    fact[i] = i*fact[i-1]
    fact[i] %= mod

if (x+y) % 3 != 0:
    print(0)
else:
    if 2*y-x < 0 or (2*y-x) % 3 != 0:
        print(0)
    elif 2*x-y < 0 or (2*x-y) % 3 != 0:
        print(0)
    else:
        print(C((x+y)//3,(2*x-y)//3))

Submission status: Accepted

Solution code:
X,Y = map(int,input().split())
M = X+Y
mod = 10**9 + 7
kaijou = [1]
for i in range(1,10**6+1):
    kaijou.append((kaijou[-1]*i)%mod)


def C(n,k):
    return (kaijou[n]*pow(kaijou[k],mod-2,mod)*pow(kaijou[n-k],mod-2,mod))%mod

    

if M%3!=0:
    print(0)
elif X<M//3 or Y<M//3:
    print(0)
else:
    print(C(M//3, X-M//3))

Submission status: Accepted

Solution code:
import math
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 
k = 10 ** 6
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1]

for i in range(2, k+1):
    g1.append( (g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)


a, b = map(int,input().split())
x = a + b

if x % 3 != 0:
    print(0)
    exit()

p = 0
q = 0
for i in range(x):
    if a <= 0 or b <= 0:
        if a == b == 0:
            break
        else:
            print(0)
            exit()
    else:
        if a >= b:
            a -= 2
            b -= 1
            p += 1
        else:
            a -= 1
            b -= 2
            q += 1

print(cmb(p+q, p, mod))

Submission status: Accepted

Solution code:
x, y = map(int, input().split())
mod = 1000000007
m = (x+y)//3
a = (m + x-y)//2
if (x+y)%3 != 0 or a<0 or a>m:
  print(0)
else:
  ans = 1
  for i in range(1, a+1):
    ans *= (m-a+i)*pow(i, mod-2, mod)
    ans %= mod
  print(ans)

Submission status: Accepted

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: Accepted

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: Accepted

Solution code:
MOD = 10**9 + 7

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

a3 = 2 * y - x
b3 = 2 * x - y
if not (a3 % 3 == 0 and b3 % 3 == 0):
  print(0)
  exit()

a = a3 // 3
b = b3 // 3

n = a + b

# https://qiita.com/derodero24/items/91b6468e66923a87f39f


def cmb(n, r):
  if (r < 0 or r > n):
    return 0
  r = min(r, n - r)
  return g1[n] * g2[r] * g2[n - r] % MOD


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)

print(cmb(a + b, a))

Submission status: Accepted

Solution code:
MOD = 10**9+7
fact = [1, 1]
for i in range(2, 10**6+1):
    fact.append((fact[i-1] * i) % MOD)


def comb(n, k):
    return (fact[n] * pow(fact[k], MOD-2, MOD) * pow(fact[n-k], MOD-2, MOD)) % MOD


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

n = (2 * X - Y) / 3
m = (2 * Y - X) / 3

if n < 0 or n != int(n):
    print(0)
elif m < 0 or m != int(m):
    print(0)
else:
    n = int(n)
    m = int(m)
    ans = comb(n+m, n)
    print(ans)

Submission status: Accepted

Solution code:
#145d
import scipy.misc

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

MOD_BY = 7 + 10**9

#たどり着くマスは
#(i+1,j+2)の移動回数をA
#(i+2,j+1)の移動回数をB
#とすると
#X = A + 2B
#Y = 2A + B
#となる
# A = X - 2B
# Y = 2(X - 2B) + B
# Y = 2X - 4B + B = 2X - 3B
# Y - 2X = - 3B
# 2X - Y = 3B
# ∴ B = (2X - Y)/3
# A = X - 2B = X -2{(2X - Y)/3}
# 3A = 3X -2(2X - Y) = 3X -4X +2Y = -X + 2Y
# ∴ A = (2Y - X)/3

A = (2*X - Y) / 3
B = (2*Y - X) / 3

#移動回数なのでA,Bともに整数かつマイナスはNG
#OKならば、白赤のボールの並べ方は何通り? という設問と同じ。
# (A+B)C(A)
# https://qiita.com/derodero24/items/91b6468e66923a87f39f#%E6%97%A2%E5%AD%98%E3%83%84%E3%83%BC%E3%83%AB%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E6%89%8B%E6%B3%95%EF%BC%93%E8%A9%95%E4%BE%A1-

def prepare(n, MOD):
 
    # n! の計算
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f
     
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    
    return fn, inv


if A >= 0 and B >= 0 and A.is_integer() is True and  B.is_integer() is True: 
    A = int(A)
    B = int(B)
    
    #print(scipy.misc.comb(A+B, A, 1)%MOD_BY) #これだと間に合わない
    
    #https://ikatakos.com/pot/programming_algorithm/number_theory/mod_combination
    #nCr ≡ n! * r!^(-1) * (n-r)!^(-1)   (mod m)
    #n = A+B
    #r = A　より
    fn_A_plus_B = prepare(A+B,MOD_BY)[0]
    inv_A = prepare(A,MOD_BY)[1]
    inv_B = prepare(B,MOD_BY)[1]
    
    print(fn_A_plus_B * inv_A * inv_B % MOD_BY)
    
else:
    print(0)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
MAX = 10 ** 6 + 1
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

def CoMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[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, k):
   if n < k:
       return 0
   if n < 0 or k < 0:
       return 0

   return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

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

if (X + Y) % 3:
    print(0)
    exit()
n = (X + Y) // 3
X -= n
Y -= n
if X < 0 or Y < 0:
    print(0)
    exit()
CoMinit()
ans = COM(X + Y, X)
print(ans)

Submission status: Accepted

Solution code:
import numpy
MOD = 10 ** 9 + 7
 
 
# a ^ b % MOD
def pow_mod(value, exp):
    r = 1
    while exp:
        if exp % 2:
            r *= value
            r %= MOD
        value *= value
        value %= MOD
        exp //= 2
    return r
 
 
fact = [1] * 1000001
for i in range(1, 1000000 + 1):
    fact[i] = fact[i - 1] * i % MOD

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

if (x + y) % 3 or x > y * 2 or y > x * 2:
    print("0")
    exit()

a, b = map(int, numpy.linalg.solve([[2, 1], [1, 2]], [x, y]))

ans = fact[a + b] % MOD
# ans /= fact[a] (mod 10^9 + 7)
ans *= pow_mod(fact[a], MOD - 2)
ans %= MOD
# ans /= fact[b] (mod 10^9 + 7)
ans *= pow_mod(fact[b], MOD - 2)
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
xy=list(map(int,input().split()))
if sum(xy)%3!=0 or 2*xy[0]<xy[1] or 2*xy[1]<xy[0]:
    print(0)
else:
    n=sum(xy)//3
    r=2*n-xy[0]
    #p=int(input("enter p as mod"))
    p=10**9+7
    g=[1,1] #元(各整数の階乗)のリスト/g[i]=i!
    inv=[1,1] #n^-1を保存するリスト
    ig=[1,1] #逆元(各整数の階乗のmod pにおける逆数)のリスト/ig[i]=(i!)^-1 mod p
    for i in range(2,n+1):
        gi=g[-1]*i%p
        g.append(gi)
        invi=-inv[p%i]*(p//i)%p
        inv.append(invi)
        igi=ig[-1]*inv[-1]%p
        ig.append(igi)
    ans=g[n]*ig[r]*ig[n-r]%p
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv
comb = Combination(10**6)
x,y = inpl()
if (x+y)%3 or max(x,y) > min(x,y)*2:
    print(0)
    quit()
n = (x+y)//3
c = comb(n,x-n)
print(c)

Submission status: Accepted

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

if (2*X-Y)%3 != 0 or (2*Y-X)%3 != 0 or 2*X-Y<0 or 2*Y-X<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: Accepted

Solution code:
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] # 階乗テーブル
    ifac = [1, 1] # 逆元の階乗テーブル
    inverse = [0, 1] # 逆元テーブル 0の階乗は1

    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())
if X > Y:
    X, Y = Y, X
dist = X + Y
if dist % 3 != 0:
    print(0)
    exit()

total = int((X+Y) / 3)
n = X - total
if Y > 2*X:
    print(0)
else:
    MOD = 10**9 + 7
    fac, ifac = make_tables(MOD, total)
    answer = cmb(total, n, MOD, fac, ifac)
    print(answer)

"""
p = (p/a)×a + (p %a)
この両辺の mod p をとると、
(p/a)×a + (p%a) ≡ 0
⇔(p/a) + (p%a)×a−1 ≡ 0　(両辺に a−1 をかける)

⇔(p%a) × a−1 ≡ −(p/a)
⇔a−1 ≡ −(((p%a)^−1) × (p/a))
"""

Submission status: Accepted

Solution code:
X, Y = map(int,input().split())
n = int((2*Y-X)/3)
m = int((2*X-Y)/3)
if (X+Y)%3!=0:
  print(0)
  exit()
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
p = 10 ** 9 + 7
N = 10 ** 6  
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
print(cmb(n+m, n, p))

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

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

    return modFacts, invs


X, Y = map(int, input().split())
if (X + Y) % 3 == 0 and 2 * Y - X >= 0 and 2 * X - Y >= 0:
    p = (2 * Y - X) // 3
    q = (2 * X - Y) // 3
    n = p + q
    r = min(p, q)
    modFacts, invs = prepare(n)
    ans = (modFacts[n] * invs[n - r] * invs[r]) % MOD
else:
    ans = 0

print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

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

    return modFacts, invs


dest = list(map(int, input().split()))

p = (2, 1)
q = (1, 2)
num_p = 0
num_q = 0

while dest[0] and dest[1]:
    if dest[0] >= dest[1]:
        dest[0] -= p[0]
        dest[1] -= p[1]
        num_p += 1
    else:
        dest[0] -= q[0]
        dest[1] -= q[1]
        num_q += 1

modFacts, invs = prepare(num_p + num_q)

if dest == [0, 0]:
    n = num_p + num_q
    r = min(num_p, num_q)
    ans = (modFacts[n] * invs[n - r] * invs[r]) % MOD
else:
    ans = 0

print(ans)

Submission status: Accepted

Solution code:
#----------------------------------------------------------
P = 10**9 + 7
N = 700000 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
finv = [1] + [1] # 1/x!
fac = [1] + [1] # x!
for i in range(2,N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
  fac += [(fac[i-1] * i) % P]
  finv += [(finv[i-1] * inv[i]) % P]

def comb(a, b):
    if a<b:
        return -1 # error
    return (fac[a] * ((finv[b] * finv[a-b]) % P)) %P
#----------------------------------------------------------
x, y = map(int, input().split())
if (2*y-x)%3!=0 or (2*x - y)%3!=0:
    print(0)
    exit(0)
A = (2*y-x)//3
B = (2*x-y)//3
if A<0 or B<0:
    print(0)
    exit(0)
print(comb(A+B, A))

Submission status: Accepted

Solution code:
import sys

x,y=map(int,input().split())
T=x+y
MOD=10**9+7

def nCmMOD(A,B,Mod):
    num,den=1,1
    for i in range(B):
        num*=(A-i)
        den*=(i+1)
        num%=Mod
        den%=Mod
    return (num*pow(den,Mod-2,Mod))%Mod

if T%3!=0 or y/x<1/2 or y/x>2:
    print(0)
    sys.exit()
else:
    n=(2*y-x)//3
    m=(2*x-y)//3
    l=min(n,m)
    print(nCmMOD(n+m,l,MOD))

Submission status: Accepted

Solution code:
from math import factorial
pos = map(int, input().split())
p = 10**9 + 7
x, y = sorted(pos)

if (x+y) % 3 != 0:
    print(0)
    exit()

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

# Python3 function to
# calculate nCr % p


def ncr(n, r, p):
    # initialize numerator
    # and denominator
    num = den = 1
    for i in range(r):
        num = (num * (n - i)) % p
        den = (den * (i + 1)) % p
    return (num * pow(den,
                      p - 2, p)) % p


ans = ncr(n+m, n, p)
print(ans)

Submission status: Accepted

Solution code:
MAX = 1000000 #階乗のmodを求めたい中で最大のもの
MOD = 10**9+7

fac = [0]*MAX   #階乗のmod
inv = [0]*MAX    #その数の逆元
finv = [0]*MAX   #階乗の逆元

def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[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,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return (fac[n] * (finv[k]*finv[n-k]))%MOD

#pが素数でないと使えない

COMinit()

x,y = map(int,input().split())
ans = 0
if 2*y-x < 0 or 2*x-y < 0:
  pass
elif (2*y-x)%3 != 0 or (2*x-y)%3 != 0: 
  pass
else:
  s = (2*y-x)//3
  t = (2*x-y)//3
  ans = COM(s+t,s)
  
print(ans)

Submission status: Accepted

Solution code:
X,Y = map(int,input().split())
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 = 1
  b = 1
  c = 1
  for i in range(1,n+1):
    a = (a*i)%p
  for i in range(1,k+1):
    b = (b*i)%p
  for i in range(1,n-k+1):
    c = (c*i)%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**2) %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
if (X+Y)%3 != 0 or X > 2*Y or Y > 2*X:
    print(0)
else:
    ab = (X+Y)//3
    a = X - ab
    b = ab - a
    mod = 10**9+7
    ans = comb(ab,min(a,b),mod)
    print(ans)

Submission status: Accepted

Solution code:
X,Y = map(int,input().split())
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 = 1
  b = 1
  c = 1
  for i in range(1,n+1):
    a = (a*i)%p
  for i in range(1,k+1):
    b = (b*i)%p
  for i in range(1,n-k+1):
    c = (c*i)%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
if (X+Y)%3 != 0 or X > 2*Y or Y > 2*X:
    print(0)
else:
    ab = (X+Y)//3
    a = X - ab
    b = ab - a
    mod = 10**9+7
    ans = comb(ab,min(a,b),mod)
    print(ans)

Submission status: Accepted

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

if (X+Y)%3 != 0 or X > 2*Y or Y > 2*X:
    print(0)
else:
    ab = (X+Y)//3
    a = X - ab
    b = ab - a
    mod = 10**9+7
    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+1
    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 )

    ans = cmb(ab,b,mod)
    print(ans)

Submission status: Accepted

Solution code:

def comb(n, r, mod=10 ** 9 + 7):
    n1 = n + 1
    r = min(n, 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

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

if (x+y) % 3 != 0:
    print(0)
    exit()

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

if n*m < 0:
    print(0)
    exit()

print(comb(n+m, m))

Submission status: Accepted

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

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 (2*Y - X) < 0:
    print(0)
elif (2*X - Y) < 0:
    print(0)
else:
    if (X - 2*Y) % 3 != 0 or (2*X - Y) % 3 != 0:
        print(0)
    else:
        a = (2 * Y - X) // 3
        b = (2 * X - Y) // 3
        ans = cmb(a+b, a)
        ans = ans % M
        print(ans)

Submission status: Accepted

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
        
        a = cmb(n,r)
        print(a%(int(1e9+7)))
        return 0


main()

Submission status: Accepted

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

if (X+Y)%3>0:
  print(0)
  exit()
  
a=(2*X-Y)//3
b=(2*Y-X)//3

if a*b<0:
  print(0)
  exit()

ab=a+b
ue=[1]*(ab+1)
for i in range(1, ab+1):
  ue[i]=ue[i-1]*i%p
  
out=ue[-1]*pow(ue[a], p-2, p)%p
out=out*pow(ue[b], p-2, p)%p

print(out)

Submission status: Accepted

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 0
  if (2*X-Y)%3:
    return 0
  m = (2*X-Y)//3
  n = X - 2*m
  if m < 0 or n < 0:
    return 0
  return (combination(m+n,m))

print(solve())