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:
MOD = 1000000007

def pow(a, b):
	if not b:
		return 1
	c = pow(a, b // 2)
	if b % 2:
		c = a * c % MOD * c % MOD
	else:
		c = c * c % MOD
	return c

X, Y = map(int, input().split())
if (X * 2 - Y) % 3 or (Y * 2 - X) % 3:
	print(0)
else:
	a, b = (X * 2 - Y) // 3, (Y * 2 - X) // 3
	if a < 0 or b < 0:
		print(0)
	else:
		c = [1] * (a + b + 1)
		i = 1
		while i <= a + b:
			c[i] = c[i - 1] * i % MOD
			i += 1
		print(c[a + b] * pow(c[a], MOD - 2) % MOD * pow(c[b], MOD - 2) % MOD)

Submission status: Accepted

Solution code:
'''
https://atcoder.jp/contests/abc145/tasks/abc145_d
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 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<0 or b<0:
        print(0)
        exit()

    def extgcd(a, b):
        if b == 0:
            return a, 1, 0
        else:
            d, x, y = extgcd(b, a % b)
            x -= (a // b) * y
            return d, y, x
        
    def modinv(a, mod): 
        return extgcd(a, mod)[1] % mod

    def modcomb(n, k, mod):
        q, a = 1, 1
        for i in range(n-k+1, n+1):
            q = (q * i) % mod
        for i in range(2, k+1):
            a = (a * i) % mod
        return int(q * modinv(a, mod) % mod)

    print(modcomb(a+b, a, mod))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
import math

def main():
    def pre(n,MOD):
        a=1
        for i in range(1,n+1):
            a=(a*i)%MOD
        an=a
        b=pow(a,MOD-2,MOD)
        bs=[1]*(n+1)
        bs[n]=b
        for i in range(n,1,-1):
            b=b*i%MOD
            bs[i-1]=b
        return an,bs
    
    x,y=map(int,input().split())
    d=(x+y)//3
    MOD=10**9+7
    if (x+y)%3!=0 or x<d or y<d:
        print(0)
    else:
        a,b=pre(d,MOD)
        a=a*b[y-d]*b[2*d-y]%MOD
        print(a)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def comb(n,r,mod):
  ans = 1
  for i in range(r):
    ans *= n-i
    ans %= mod
  for i in range(1,r+1):
    ans *= pow(i,mod-2,mod)
    ans %= mod
  return ans
  
if (2*X-Y)%3!=0 or 2*X-Y<0 or (-1)*X+2*Y<0:
  print(0)
else:
  p = (2*X-Y)//3
  q = ((-1)*X+2*Y)//3
  print(comb(p+q,p,mod))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc145/tasks/abc145_d
from math import factorial
x, y = map(int, input().split())
mod = 10 ** 9 + 7

# two_steps = x // 2
# one_steps = x % 2
# ans = 0
# while two_steps:
#     if one_steps * 2 + two_steps * 1 == y:
#         ans += (factorial(one_steps + two_steps) * (pow(factorial(one_steps), mod - 2, mod) * pow(factorial(two_steps), mod - 2, mod))) % mod
#     two_steps -= 1
#     one_steps += 2
# print(ans)

MAX = 10 ** 6 + 1

def com_init(MAX, mod):
    fac = [0] * MAX
    finv = [0] * MAX
    inv = [0] * MAX
    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
    return fac, finv

fac, finv = com_init(MAX, mod)

def nCr(n, r):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod 

if (x + y) % 3 == 0:
    a = (-x + 2 * y) // 3
    b = (2 * x - y) // 3
    ans = nCr(a + b, a)
    # ans = (factorial(a + b) * (pow(factorial(a), mod - 2, mod) * pow(factorial(b), mod - 2, mod))) % mod
else:
    ans = 0

print(ans)

Submission status: Accepted

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


def comb(n, r, mod):
    numerator = denominator = 1
    for i in range(r):
        numerator = numerator * (n - i) % mod
        denominator = denominator * (i + 1) % mod
    return numerator * inv(denominator, mod) % mod


# 逆元を返す関数(非再帰拡張Euclidの互除法))
# pow(a, mod-2, mod)と等価
def inv(a, mod):
    b = mod
    p, q = 1, 0
    while b > 0:
        c = a // b
        a, b = b, a-c*b
        p, q = q, p-c*q
    return p + mod if p < 0 else p


i = (2*y - x) // 3
j = (2*x - y) // 3
if (x + y) % 3 == 0 and i >= 0 and j >= 0:
    ans = comb(i+j, i, mod)
else:
    ans = 0
print(ans)

Submission status: Accepted

Solution code:
import sys
mod = 10**9+7
def bpow(x,n,m) :
  if n == 0 :
    return 1
  ans = 1
  while n > 1 :
    if n%2 != 0 :
      ans = ans*x%mod
    x = x*x%mod
    n //= 2
  return ans*x%mod
      
x,y = map(int,input().split())

for i in range(0,10**6+1) :
  xa = x - 1*i
  ya = y - 2*i
  if xa%2 == 0 and ya == 1*(xa//2) and xa >= 0 :
    n = i+xa//2
    # n!のあまりを求める
    np = 1
    for j in range(1,n+1) :
      np = (np*j)%mod
    #1/p!のあまりを求める
    pp = 1
    for j in range(1,i+1) :
      pp = pp*bpow(j,mod-2,mod)%mod
    #1/q!のあまりを求める
    qp = 1
    for j in range(1,(n-i)+1) :
      qp = qp*bpow(j,mod-2,mod)%mod
    print(np*pp*qp%mod)
    sys.exit()
print(0)

Submission status: Accepted

Solution code:
X,Y = map(int,input().split())
if((-X+2*Y)%3 != 0 or (-Y+2*X)%3 != 0 or -X+2*Y<0 or -Y+2*X<0):
    print(0)
    exit()
A = (-X+2*Y)//3
B = (-Y+2*X)//3
mod = 10**9+7
def combinations_count(A,B):
    bunsi,bunbo = 1,1
    for i in range(1,A+1):
        bunsi = (bunsi*(B+i))%mod
        bunbo = (bunbo*i) % mod
    return (bunsi*pow(bunbo,mod-2,mod))%mod
ans = combinations_count(A,B)
print(ans)

Submission status: Accepted

Solution code:
def com(n,r,mod):
    k=min(r,n-r)
    C=1
    for i in range(1,k+1):
        C=(C*(n+1-i)*pow(i,mod-2,mod))%mod
    return C
x,y=map(int,input().split())
mod = 10 ** 9 + 7
n = (2 * y - x) // 3
m = (2 * x - y) // 3
if (x + y) % 3 != 0 or n<0 or m<0:
    print(0)
    exit()

print(com(n+m,n,mod))

Submission status: Accepted

Solution code:
def comb(n, r, p):
    x, y = 1, 1
    for i in range(n, n - r, -1):
        x *= i
        y *= i + r - n
        x %= p
        y %= p
    return pow(y, p - 2, p) * x % p

x, y = map(int, input().split())
n = (x + y) // 3
p = 10 ** 9 + 7
if (x + y) % 3 == 0 and max(x, y) <= 2 * min(x, y):
    r = 0
    if x > y:
        x, y = y, x
    a = (2 * x - y) // 3
    r = min(a, n - a)
    print(comb(n, r, p))
else:
    print(0)

Submission status: Accepted

Solution code:
def factorial(N,MOD,r=True):
    fact = [1]*(N+1)
    rfact = [1]*(N+1)
    r = 1
    for i in range(1,N+1):
        fact[i] = r = r * i % MOD
    rfact[N] = r = pow(fact[N],MOD-2,MOD)
    for i in range(N, 0, -1):
        rfact[i-1] = r = r * i % MOD
    if r:
        return fact,rfact
    else:
        return fact
mod = 10**9 + 7
fact,rfact = factorial(10**6,mod)

def perm(n,k): #上のfactorialと併用
    return fact[n]*rfact[n-k]%mod
def comb(n,k): #上のfactorialと併用
    return fact[n]*rfact[k]*rfact[n-k]%mod

x,y = map(int,input().split())
if (x+y)%3:
    print(0)
    exit()
a = (-x+2*y)//3
b = (2*x-y)//3

print(comb(a+b,a) if a >= 0 and b >= 0 else 0)

Submission status: Accepted

Solution code:
X,Y=map(int,input().split())
mod=pow(10,9)+7
m=(2*X-Y)//3
n=(2*Y-X)//3
if  m!=(2*X-Y)/3 or n!=(2*Y-X)/3 or m<0 or n<0:
    print(0)

else:
    bunsi = 1
    bunbo = 1
    for i in range(0, n):
        bunsi = (bunsi * (m + 1 + i)) % mod
        bunbo = (bunbo * (1 + i)) % mod
    print((bunsi * pow(bunbo, mod - 2, mod)) % mod)

Submission status: Accepted

Solution code:
X,Y=map(int,input().split())
mod=pow(10,9)+7
m=(2*X-Y)//3
n=(2*Y-X)//3
if  m==(2*X-Y)/3 and n==(2*Y-X)/3 and m>=0 and n>=0:
    bunsi = 1
    bunbo = 1
    for i in range(0, n):
        bunsi = (bunsi * (m + 1 + i)) % mod
        bunbo = (bunbo * (1 + i)) % mod
    print((bunsi * pow(bunbo, mod - 2, mod)) % mod)

else:
    print(0)

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
mod=10**9+7
n_max=2*(10**6+1)
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
FI[n_max-1]=pow(F[n_max-1],mod-2,mod)
for i in reversed(range(n_max-1)):
  FI[i]=(FI[i+1]*(i+1))%mod
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod
x,y=map(int,input().split())
if (x+y)%3!=0:
  print(0)
else:
  n=(x+y)//3
  if x<n or y<n:
    print(0)
  else:
    print(comb(n,x-n))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
import copy
#import numpy as np
 
# 入力
#A, B, C, D = map(int, input().split())
#L = list(map(int, input().split()))
#S = list(str(input()))
#N = int(input())
#S = str(input())

X, Y = map(int, input().split())
MOD = pow(10, 9) + 7

def comb_mod(n, r, mod):
  num = 1
  den = 1
  for i in range(r):
    num = (num * (n - i)) % mod
    den = (den * (i + 1)) % mod
  den_r = pow(den, mod - 2, mod)
  return (num * den_r) % mod


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

if (n == (2*Y - X) / 3 and m == (2*X - Y) / 3 
    and n >= 0 and m >= 0):  
  a = n + m
  b = min(n, m)
  print(comb_mod(a, b, MOD))
else :
  print (0)

Submission status: Accepted

Solution code:
import sys

def comb_mod(n, r, mod):
  x = 1
  y = 1
  for i in range(r):
    x = (x * (n - i)) % mod
    y = (y * (i + 1)) % mod
    
  ans = x * pow_k(y, mod-2, mod)
  
  return ans % mod
  
# x^n % mod
def pow_k(x, n, mod):
  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 (x * K) % mod
  
MOD = 10 ** 9 + 7
x, y = map(int, input().split())

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

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

ans = comb_mod(a+b, min(a,b), MOD)
print(ans)

Submission status: Accepted

Solution code:
#145_D
x,y=map(int,input().split())
mod=10**9+7
if (x+y)%3!=0:
    print(0)
else:
    n=(2*x-y)//3
    m=(2*y-x)//3
    if n<0 or m<0:
        print(0)
    else:
        f=[1 for i in range(m+n+1)]
        for i in range(2,m+n+1):
            f[i]=f[i-1]*i%mod
        print(f[m+n]*pow(f[n],mod-2,mod)*pow(f[m],mod-2,mod)%mod)

Submission status: Accepted

Solution code:
import sys

X, Y = map(int, input().split())
A, mod = divmod(2*Y-X, 3)
if mod != 0 or A < 0:
	print(0)
	sys.exit()
B, mod = divmod(2*X-Y, 3)
if mod != 0 or B < 0:
	print(0)
	sys.exit()

mod = 10**9 + 7

a = A+B
b = min(A,B)

ans = 1

for i in range(b):
	ans *= a-i
	ans %= mod

	ans *= pow(i+1, mod-2, mod)

ans %= mod

print(ans)

Submission status: Accepted

Solution code:
mod = int(1e9) + 7
x, y = map(int, input().split())

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

n = (x+y)//3
a = x - n
b = y - n
r = min(a, b)
if r < 0:
    print(0)
    exit()
val1 = 1
for i in range(a+b):
    val1 = (val1 * ((a+b) - i)) % mod
val2 = 1
for i in range(r):
    val2 = (val2 * (r-i)) % mod
for i in range(a+b-r):
    val2 = ((val2% mod) * ((a+b-r)-i)) % mod
# val1 = factorial(a+b) % mod
# val2 = (factorial(r) % mod * factorial((a+b)-r) % mod) % mod
print((val1 * pow(val2,mod-2,mod)) % mod)

Submission status: Accepted

Solution code:
MOD = 1000000007

def pow(a, b):
	if not b:
		return 1
	c = pow(a, b // 2)
	if b % 2:
		c = a * c % MOD * c % MOD
	else:
		c = c * c % MOD
	return c

X, Y = map(int, input().split())
if (X * 2 - Y) % 3 or (Y * 2 - X) % 3:
	print(0)
else:
	a, b = (X * 2 - Y) // 3, (Y * 2 - X) // 3
	if a < 0 or b < 0:
		print(0)
	else:
		c = [1] * (max(a + b, a) + 1)
		i = 1
		while i <= max(a + b, a):
			c[i] = c[i - 1] * i % MOD
			i += 1
		print(c[a + b] * pow(c[a], MOD - 2) % MOD * pow(c[b], MOD - 2) % MOD)

Submission status: Accepted

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  mod=pow(10,9)+7
  x,y=map(int,input().split())
  ans=0
  if (2*y-x)%3!=0 or  (2*x-y)%3!=0:
    print(0)
    exit()
  a,b=(2*y-x)//3,(2*x-y)//3
  n,r=(a+b),a
  fact=[0]*(n+1)
  inv=[0]*(n+1)
  factinv=[0]*(n+1)
  fact[0],fact[1]=1,1
  inv[1]=1
  factinv[0],factinv[1]=1,1
  for i in range(2,n+1):
    fact[i]=(fact[i-1]*i)%mod
    inv[i]=mod-(inv[mod%i]*(mod//i))%mod               
    factinv[i]=(factinv[i-1]*inv[i])%mod      
  def cmb(n,r,mod):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod
  print(cmb(n, r, mod)) 
      
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def ncr(n,r,mod):
    cnt=1
    for i in range(n-r+1,n+1):
        cnt*=i
        cnt%=mod
    for i in range(1,r+1):
        cnt*=pow(i,mod-2,mod)
        cnt%=mod
    return cnt
mod=10**9+7
x,y=map(int,input().split())
if (x+y)%3!=0:
    print(0)
    exit()
mini=min(x,y)
if (x+y)//3>mini:
    print(0)
    exit()
n=(x+y)//3
dif=abs(x-y)
if dif%2==0:
    r=dif//2
    center=n//2
    print(ncr(n,center+r,mod))
else:
    r=(dif-1)//2
    center=n//2
    print(ncr(n,center-r,mod))

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    X,Y = map(int, input().split())

    t = X//2
    a = b = 0
    while t <= X:
        b = X - t
        a = t - b
        if 2*a + b == Y: break
        t += 1
    else:
        print(0)
        exit()

    fu = FactorialUtils(t)
    print(Mint(1) * fu.fac[t] * fu.ifac[a] * fu.ifac[b])

class FactorialUtils:
    def __init__(self, n, mod=10**9+7):
        self.__mod = mod
        self.fac = [1] * (n+1)
        self.ifac = [1] * (n+1)
        for i in range(2, n+1): self.fac[i] = self.fac[i-1] * i % mod
        self.ifac[n] = pow(self.fac[n], mod-2, mod)
        for i in range(n, 1, -1): self.ifac[i-1] = self.ifac[i] * i % mod

    def choose(self, n, r):
        if r < 0 or r > n: return 0
        return (self.fac[n] * self.ifac[n-r] % self.__mod) * self.ifac[r] % self.__mod

    def multichoose(self, u, k):
        return (self.fac[u+k-1] * self.ifac[u-1] % self.__mod) * self.ifac[k] %self.__mod

class Mint:
    def __init__(self, value=0, mod=10**9+7):
        self.value = ((value % mod) + mod) % mod
        self.mod = mod

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, self.mod
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        return (u + self.mod) % self.mod

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.val
    def __neg__(self): return Mint(-self.value, self.mod)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % self.mod
        return self
    def __add__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other) + self.mod) % self.mod
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other), self.mod)
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % self.mod
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other, self.mod)
        self *= other.inverse
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other), self.mod)
        new_obj //= self
        return new_obj


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#コンビネーション
def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod

N = pow(10, 6) + 10  # N は必要分だけ用意する
mod = pow(10, 9) + 7
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

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


x,y = map(int,input().split())
ans = 0
if (x + y) % 3 == 0:
    a = (2 * y - x) // 3
    b = (2 * x - y) // 3
    ans = cmb(a + b, min(a, b))
print(ans)

Submission status: Accepted

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

if (X+Y)%3 != 0 or abs(X-Y) > (X+Y)//3:
    print(0)
    exit(0)
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
MOD = 10**9 + 7

print(cmb((X+Y)//3,min(X,Y)-(X+Y)//3)%MOD)

Submission status: Accepted

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

if (X+Y)%3:
    print(0)
    exit()
n = (X+Y)//3
r = X-n
if not 0 <= r <= n:
    print(0)
    exit()

MAXN = r
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
def comb(n,r):
    ret = 1
    for i in range(r):
        ret *= n-i
        ret *= inv[i+1]
        ret %= MOD
    return ret

print(comb(n,r))

Submission status: Accepted

Solution code:
def main():
    X, Y = (int(i) for i in input().split())
    if (X+Y) % 3 != 0:
        return print(0)
    m = (X + Y)//3 + 3
    fac = [0] * m
    finv = [0] * m
    inv = [0] * m
    MOD = 10**9 + 7

    def COMBinitialize(m):
        fac[0] = 1
        finv[0] = 1
        if m > 1:
            fac[1] = 1
            finv[1] = 1
            inv[1] = 1
            for i in range(2, m):
                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 COMB(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

    COMBinitialize(m)
    n = (X+Y)//3
    k = X - n
    print(COMB(n, k))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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


class Combination:
    """
    SIZEが10^6程度以下の二項係数を何回も呼び出したいときに使う
    使い方:
    comb = Combination(SIZE, MOD)
    comb(10, 3) => 120
    """

    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


move = (X + Y) // 3
yoko = (move - (Y - X)) // 2
tate = move - yoko

comb = Combination(10**6+10, 10**9+7)
ans = comb(tate+yoko, yoko)
print(ans)

Submission status: Accepted

Solution code:
def cmb1(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+10
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 )


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

if (-x+2*y)>= 0 and (-x+2*y)%3 == 0 and  (2*x-y)>= 0 and (2*x-y)%3 == 0:
    a = (-x+2*y)//3
    b = (2*x-y)//3
    print(cmb1(a+b, a, mod))
else:
    print(0)

Submission status: Accepted

Solution code:
p = 10**9+7
def pow(x,m):
    if m==0:return 1
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2))%p
X,Y = map(int,input().split())
K = X+Y
A = [1 for _ in range(K)]
for i in range(2,K):
    A[i] = (A[i-1]*i)%p
B = [1 for _ in range(K)]
B[K-1] = pow(A[K-1],p-2)
for i in range(K-2,1,-1):
    B[i] = ((i+1)*B[i+1])%p
if 2*Y-X>=0 and Y<=2*X and (X+Y)%3==0 and (2*Y-X)%3==0:
    k = (X+Y)//3
    i = (2*Y-X)//3
    cnt = (A[k]*B[i]*B[k-i])%p
    print(cnt)
else:
    print(0)

Submission status: Accepted

Solution code:
p,q=map(int,input().split())
mod=10**9+7
x=(2*q-p)//3
y=q-2*x
def ie(n,r,mod):
  if r==1:
    return n%mod
  elif r%2==0:
    return (ie(n,r//2,mod)**2)%mod
  else:
    return ((ie(n,r//2,mod)**2)*n)%mod
if x+2*y!=p or 2*x+y!=q or x<0 or y<0:
  print(0)
elif x==0 or y==0:
  print(1)
else:
  a=[(x+y)%mod]
  b=[1]
  for i in range(1,min(x,y)):
    a.append(a[-1]*(x+y-i)%mod)
    b.append(b[-1]*(i+1)%mod)
  print((a[-1]*ie(b[-1],mod-2,mod))%mod)

Submission status: Accepted

Solution code:
x,y = map(int, input().split())

p = 7+pow(10,9)
def cmb(n,r,p):
    numerator = 1
    for i in range(n-r+1, n+1):
        numerator = numerator * i % p
    denominator = 1
    for i in range(1, r+1):
        denominator = denominator * i % p
    return numerator * pow(denominator, p-2, p) % p


if (x+y)% 3 == 1 or (x+y)%3 == 2:
    print(0)
else:
    n = (-x + 2*y)/3 # (+1,+2)の座標の変化の回数
    m = (2*x - y )/3 # (+2, +1)の座標の変化の回数
    if n<0 or m<0:
        print(0)
    else:
        print(cmb(int(n+m), int(n), p))

Submission status: Accepted

Solution code:
X,Y=map(int,input().split())
N=(X+Y)//3
import sys
sys.setrecursionlimit(10**8)
A=X-N
B=Y-N
No=False
if (X+Y)%3!=0 or X<N or Y<N:
    No=True
ans=1
C=min(A,B)
for i in range(0, C):
    ans*=N-i
    ans%=(10**9+7)
def inv(i, p, q):
    if q==1:
        return i%p
    if q%2==0:
        x=inv(i, p,q//2)
        return (x**2)%p
    else:
        x=inv(i, p,q//2)
        return (x**2*i)%p
tmp=1
for i in range(C):
    tmp*=(i+1)
    tmp%=(10**9+7)
iv=inv(tmp, 10**9+7,10**9+5)
ans=ans*iv%(10**9+7)
if No:
    print(0)
else:
    print(ans)

Submission status: Accepted

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

# a+2b=X
# 2a+b=Y
# b = (2X-Y)/3
# a = (2Y-X)/3

p = 10 ** 9 + 7
N = 10 ** 6 +10  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

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)

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


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

if a < 0 or b < 0 or a%3!=0 or b%3!=0:
    print(0)
else:
    a = a//3
    b = b//3

    print(cmb(a+b,a,p))

Submission status: Accepted

Solution code:
X, Y = (int(i) for i in input().split())

def power(a, b):
	if b == 0:
		return 1
	elif b == 1:
		return a % 1000000007
	elif b % 2 == 0:
		return (power(a, b//2) ** 2) % 1000000007
	else:
		return (power(a, b//2) ** 2 * a) % 1000000007

def divide(a, b):
	return (a * power(b, 1000000005)) % 1000000007


#階乗の逆元を求める
fac_lim = 1000000
fac = [None]*(fac_lim+1)
fac[0] = 1
for i in range(fac_lim):
    fac[i+1] = fac[i] * (i+1)
    fac[i+1] = fac[i + 1] % 1000000007

fac_inv = [None]*(fac_lim+1)
fac_inv[fac_lim] = power(fac[fac_lim], 1000000005)
for i in range(fac_lim, 0, -1):
    fac_inv[i-1] = (fac_inv[i] * i)  % 1000000007

def conv(a, b):
    return (fac[a] * fac_inv[a-b] * fac_inv[b]) % 1000000007


MOD = 10**9 + 7
if (X+Y)%3 != 0:
    ans = 0
else:
    N = (X+Y)//3
    M = X - Y
    if (N+M)%2 !=0:
        ans = 0
    else:
        a = (N+M)//2
        if 0 <= a <= N:
            ans = conv(N, a)
        else:
            ans = 0
print(ans%MOD)

Submission status: Accepted

Solution code:
X,Y = list(map(int,input().split()))
mod = 10**9+7
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]

Xd = (2*X-Y)/3
Yd = (-X+2*Y)/3

def init(n):
    for i in range(2, n + 1):
        fac.append(fac[-1] * i % mod)
        inv.append(-inv[mod % i] * (mod // i) % mod)
        finv.append(finv[-1] * inv[-1] % mod)

def com(n, k, mod):
    if n < 0 or k < 0 or n < k:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod

if Xd % 1 == 0 and Yd % 1 == 0:
    init(int(Xd+Yd))
    print(com(int(Xd+Yd), int(Yd), mod)) # 161700
else:
    print('0')

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    x,y = map(int,input().split())
    a_old = 2 * y - x
    b_old = 2 * x - y

    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 (a_old % 3 == 0) and (b_old % 3 == 0) and (a_old >= 0) and (b_old >= 0):
        a_new = int(a_old // 3)
        b_new = int(b_old // 3)
        n = a_new + b_new
        r = cmb(n,a_new)
        print(int(r % (10**9 + 7)))
    else:
        print(0)

if __name__ == "__main__":
    main()

Submission status: Accepted

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


# nCr フェルマーの小定理より（ABC156D参照）
def comb_mod(n, r, mod):
    num = 1
    den = 1
    for i in range(r):
        num = (num * (n - i)) % mod
        den = (den * (i + 1)) % mod
    den_r = pow(den, mod - 2, mod)
    return (num * den_r) % mod


# n+2m=X,2n+m=Yより
n = (2 * Y - X) // 3
m = (2 * X - Y) // 3

# 3の倍数以外は0
# (0,6)など、n<0 or m<0のときも0
if (X + Y) % 3 != 0 or n < 0 or m < 0:
    print(0)
else:
    print(comb_mod(n + m, n, mod))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
MOD = 1000000007  # type: int

# 逆元comb
def comb(n, k):
    k = min(n-k,k)
    ans = 1
    for i in range(1, k + 1):
        ans *= (n + 1 - i) * pow(i,MOD-2,MOD)
        ans %= MOD
    return ans

def solve(X: int, Y: int):
    if (X+Y)%3 != 0 or Y*2-X < 0 or X*2-Y < 0:
        print(0)
        return

    # (1,2)の移動をa回, (2,1)の移動をb回するとするをそれぞれ何回か決まる
    a = (Y*2-X)//3
    b = (X*2-Y)//3
    print(comb(a+b,a))
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(X, Y)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import reduce
mod = 10**9+7
def mul(a,b):
    return a*b % mod
def cmb(n,r,mod):
    if r == 0:
        return 1
    if r == 1:
        return n % mod 
    above = reduce(mul,range(n-r+1,n+1)) 
    below = reduce(mul,range(1,r+1)) 
    ans = above*pow(below,mod-2,mod) % mod
    if ans < 0:
        ans += mod
    return ans
x,y = map(int,input().split())
if 2*x-y < 0 or 2*y-x<0 or (2*x-y) % 3 != 0:
    print(0)
    exit()
a = (2*x-y)//3
b = (2*y-x)//3
print(cmb(a+b,min(a,b),mod))

Submission status: Accepted

Solution code:
X,Y=map(int,input().split())
mod=10**9+7
"""2a+b=X 2b+a=Yを満たすabの並び替え"""
###a+b=(X+Y)/3,a-b=X-Y
###a,b>=0 かつ X+Y(mod3)==0
if (X+Y)%3!=0:
    print("0")##immposible
else:
    a=min(((X+Y)//3+(X-Y))//2,((X+Y)//3-(X-Y))//2)
    b=max(((X+Y)//3+(X-Y))//2,((X+Y)//3-(X-Y))//2)
    ###(a+b)combination a
    c=1
    d=1
    if a>0 and b>=0:
        for i in range(a):
            c*=(a+b-i)
            c=c%mod
            d*=(i+1)
            d=d%mod
        print((c*pow(d,mod-2,mod))%mod)
    elif a==0 and b>0:
        print("1")
    else:
        print("0")

Submission status: Accepted

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

mod=10 ** 9 + 7
def binomial(n,k):
    x=1
    y=1
    for i in range(k):
        x=x*(n-i)%mod
        y=y*(i+1)%mod
    return x*pow(y,mod-2,mod)%mod

if (2*X-Y)%3==0 and  (2*Y-X)%3==0:
    a=(2*X-Y)//3
    b=(2*Y-X)//3
    if a<0 or b<0:
        print(0)        
    else:
        print(binomial(a+b,a)%mod)
else:
    print(0)

Submission status: Accepted

Solution code:
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

""" 
参考:http://drken1215.hatenablog.com/entry/2018/06/08/210000
maximとmodを適宜設定。
あ入力忘れを考慮してあえて入力例通らないようにしておいたで。

combを使う前にcominit()を使う

"""
maxim = 10**6 + 10
mod = 10**9+7
fac = [None] * maxim
finv = [None] * maxim
inv = [None] * maxim

def cominit():
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1

    for i in range(2, maxim):
        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


def main():
    x,y = map(int, input().split())
    if (x+y) % 3 != 0 or x/2 > y or y > 2*x:
        print(0)
        return

    # (x+y) // 3で何段目かわかる
    # パスカルの三角形で言うところのハジから何番目かがわかればいい

    # k段目の点は -x + 3*k上にある
    # 2*xが一番端にある
    
    k = (x+y) // 3
    # k段目の上端は (k, 2k)に存在する
    # 左から何番目かは2*k -yで求まる
    # 解は kC2*k-y

    cominit()
    m = (2*y-x)//3
    n = m+x-y
    
    print(com(m+n,n))

    return

if __name__ == '__main__':
    main()