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:
#https://qiita.com/derodero24/items/91b6468e66923a87f39f
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 )


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

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

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

print(cmb(a // 3, m, mod))

Submission status: Accepted

Solution code:
import sys
X,Y=map(int,input().split())
if (X+Y)%3!=0:
    print(0)
    sys.exit()
if X>2*Y or Y>2*X:
    print(0)
    sys.exit()
mod=10**9+7
A=(X+Y)//3
B=min(X,Y)-A


ans=1
for i in range(B):
    den=i+1
    num=A-i
    ans=ans*num*pow(den,mod-2,mod)%mod

print(ans)

Submission status: Accepted

Solution code:
import sys

x,y=map(int,input().split())
d=abs(x-y)
if x>=y:
    x-=2*d
    y-=d
else:
    x-=d
    y-=2*d
if x%3!=0 or x<0:
    print(0)
    sys.exit()

cnt=x//3

mod=10**9+7
N=7*10**5+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)

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

print(cmb(2*cnt+d,cnt))

Submission status: Accepted

Solution code:
X, Y = map(int, input().split())
x, y = (X*2-Y)//3, (Y*2-X)//3
mod = 10**9+7
n = min(x, y)

factorial = [1]
for i in range(1, n+1):
    factorial.append((factorial[i-1]*i)%mod)

p_list = [(x+y)%mod]
for i in range(1, n+1):
    p_list.append((p_list[i-1]*(x+y-i))%mod)
    
if (X+Y)%3 != 0:
    print (0)
elif x < 0 or y < 0:
    print (0)
elif n == 0:
    print (1)
else:
    print (p_list[n-1]*pow(factorial[n], 10**9+5, mod)%mod)

Submission status: Accepted

Solution code:
import sys

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

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

if (X + Y) % 3 != 0 or n < 0 or m < 0:
    print(0)
    sys.exit(0)

N = int(n + m)
r = int(min([n, m]))
p = 10**9 + 7
fact = [1, 1]
inv = [0, 1]
factinv = [1, 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(fact[N] * factinv[r] * factinv[N-r] % p)

Submission status: Accepted

Solution code:



def factorial(x, modp):
    curr = 1
    for i in range(1, x + 1):
        curr *= i
        curr %= modp
    return curr


def power(x, n, modp):
    if n == 0:
        return 1

    k = 1
    while n > 1:
        if n % 2:
            k *= x
            k %= modp
        x *= x
        x %= modp
        n //= 2
    
    return k * x % modp


def submit():
    x, y = map(int, input().split())
    
    # (i, j) -> (i + 1, j + 2)の移動方法をs回
    # (i, j) -> (i + 2, j + 1)の移動方法をt回行なったとする
    # t = Y - 2s, s = (2Y - X) / 3となる
    s = 2*y - x
    if s < 0 or s % 3 != 0: # 移動方法なし
        print(0)
        return
    s //= 3

    t = y - 2*s
    if t < 0: # 移動方法なし
        print(0)
        return

    # 全移動n = s + t中のs移動のパターンを数え上げれば良い
    # n_C_sを求めれば良い
    # n! / s! (n - s)! ≡ n! (s!)^modp-2 ((n - s)!)^modp-2
    n = s + t
    modp = 10**9 + 7
    ans = factorial(n, modp) * power((factorial(s, modp)), modp - 2, modp) * power(factorial(n - s, modp), modp - 2, modp)
    ans %= modp
    print(ans)
    
    
if __name__ == "__main__":
    submit()

Submission status: Accepted

Solution code:
import sys
x,y = [int(x) for x in input().split()]
mod = 10**9+7
if (x+y)%3!=0:
    print(0)
    sys.exit()
n = (2*y-x)//3
m = (2*x-y)//3
if n<0 or m<0:
    print(0)
    sys.exit()

a = 1
for i in range(m+1,n+m+1):
    a = a * i % mod
b = 1
for i in range(1,n+1):
    b = b * i % mod
b = pow(b,mod-2,mod)
print(a*b%mod)

Submission status: Accepted

Solution code:
import sys

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,Y = (int(x) for x in input().split())

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

if (2*Y-X) % 3 == 0:
  n = (2*Y-X) // 3  
else:
  n = -1

if (2*X-Y) % 3 == 0:
  m = (2*X-Y) // 3
else:
  m = -1

if n < 0 or m < 0:
  print(0)
  sys.exit()
print(int(cmb(n+m,n)) % (10**9 +7))

Submission status: Accepted

Solution code:
class Combination:
    def __init__(self, mod, max_num):
        self.mod = mod
        self.fac = [0] * max_num
        self.finv = [0] * max_num
        self.inv = [0] * max_num

        self.fac[0], self.fac[1] = 1, 1
        self.finv[0], self.finv[1] = 1, 1
        self.inv[1] = 1

        for i in range(2, max_num):
            self.fac[i] = self.fac[i-1] * i % mod
            self.inv[i] = mod - self.inv[mod % i] * (mod // i) % mod
            self.finv[i] = self.finv[i - 1] * self.inv[i] % mod

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


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

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

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

com = Combination(1000000007, 1000000)

print(com.calc(n+m, n))

Submission status: Accepted

Solution code:
X, Y = map(int,input().split())
MOD = 10 ** 9 + 7
if (X + Y) % 3 != 0 or 2 * X < Y or 2 * Y < X:
    print(0)
elif 2 * X == Y or 2 * Y == X:
    print(1)
else:
    turn = (X + Y) // 3
    turn2 = X - turn
    turn1 = turn - turn2
    ans = turn
    inv = [0, 1]
    for i in range(2, min(turn1, turn2) + 1):
        ans = ans * (turn - i + 1) % MOD
        ans = ans * (-inv[MOD % i] * (MOD // i)) % MOD
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    print(ans % MOD)

Submission status: Accepted

Solution code:
import math
import time
from collections import deque
from collections import defaultdict
from copy import deepcopy

mod = 10 ** 9 + 7
t = time.time()


def inv(n, mod):
    return power(n, mod-2)

def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret

def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return ((power(n, p//2) % mod) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p-1)) % mod

def main():
    X, Y = iip()
    aa = (int(-X) + int(2*Y)) // 3
    bb = (int(-Y) + int(2*X)) // 3
    if (int(-X) + int(2*Y)) % 3 != 0 or  (int(-Y) + int(2*X)) % 3 != 0:
        print(0)
        exit()

    if X > 2*Y or Y > 2*X:
        print(0)
        exit()

    a = min(aa, bb)
    b = max(aa, bb)

    npr = 1
    bunbo = 1
    for i in range(1, a+1):
        npr *= (i+b)
        npr = npr % mod

        bunbo *= i
        bunbo = bunbo % mod

    ans = npr * inv(bunbo, mod) % mod

    print(ans)



main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

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


def combination(n, r, mod):
    r = min(r, n-r)

    numer = 1
    denom = 1

    for i in range(r):
        numer = numer * (n-i) % mod
        denom = denom * (r-i) % mod

    return numer * pow(denom, mod-2, mod) % mod


m_n = (X+Y) // 3
m = X - m_n
n = Y - m_n

if (X+Y) % 3 != 0 or m < 0 or n < 0:
    print(0)
    exit()

    
print(combination(m_n, m, mod))

Submission status: Accepted

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

def pow(a,b,M):
    if b == 0:
        return 1
    else:
        if b % 2 == 0:
            return pow((a**2)%M,b//2,M) % M
        else:
            return (a * pow((a**2)%M,b//2,M)) % M

def inv(a,M):
    return pow(a,M-2,M)

def comb(n,k,M):
    nume,deno = 1,1
    for i in range(1,k+1):
        deno = (deno * (n-i+1)) % M
        nume = (nume * i) % M
    return (deno * inv(nume,M)) % M

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

Submission status: Accepted

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

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

if a.is_integer() and a >= 0 and  b.is_integer() and b >= 0:
    tmp = [i for i in range(int(a) + 1, int(a + b) + 1)]
    bunshi = 1
    for t in tmp:
        bunshi *= t % mod
        bunshi %= mod
    tmp = [i for i in range(1, int(b) + 1)]
    bunbo = 1
    for t in tmp:
        bunbo *= pow(t, mod -2, mod) % mod
        bunbo %= mod
    print(bunshi * bunbo % mod)
    
else:
    print(0)

Submission status: Accepted

Solution code:
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()
mod = 10 ** 9 + 7

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

def moddiv(a, b):
    _, inv, _ = extGCD(b, mod)
    return (a * inv) % mod

N = 2 * 10 ** 6 + 10
fact = [0] * (N)
fact[0] = 1
for i in range(1, N):
    fact[i] = (fact[i-1] * i) % mod

def comb(a, b):
    return moddiv(moddiv(fact[a+b], fact[a]), fact[b])

print(comb(x, y))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
#(a*x)をmで割った余りが1になるようなxを求める
#aで割ったときの余りはa^(-1)をかけた余りと同じ
#逆元a^(-1)を求める
#aとmが互いに素であることが条件

def gyakugen( a, m ):
  b = m
  x, y = 1, 0
  while b>0:
    q = a // b
    a, b = b, a-q*b
    x, y = y, x-q*y
  return x if x>0 else x+m


#(a/b)をmで割った余りを求める
#b^(-1)にaを掛けたものをmで割ればよい

def div_remainder(a,b,m):
    b_inv=gyakugen(b,m)
    a%=m
    return (a*b_inv)%m


#(a*b)をmで割った余りを求める

def multi_remainder(a,b,m):
    a%=m
    b%=m
    return (a*b)%m



#nPrをmで割った余りを求める(ただしn<m、mは素数)

def perm_remainder(n,r,m):
    if r>1:
      return (perm_remainder(n-1,r-1,m)*n)%m
    elif r==1:
      return n
    else:
      return 1

#nCrをmで割った余りを求める(ただしn<m,mは素数)

def comb_remainder(n,r,m):
    r=min(r,n-r)
    return (perm_remainder(n,r,m)*gyakugen(perm_remainder(r,r,m),m))%m


x,y=map(int,input().split())
m=10**9+7
if (2*x-y)%3!=0 or (-x+2*y)%3!=0 or 2*x-y<0 or -x+2*y<0:
  ans=0
else:
  nx=(2*x-y)//3
  n=(x+y)//3
  ans=comb_remainder(n,nx,m)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

MOD = 1000000007

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

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

def combination(n,r,mod):
    r = min(r, n-r)
    numer = denom = 1

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


tmp = (X+Y) // 3
m = X - tmp
n = Y - tmp
if m < 0 or n < 0:
    print(0)
    exit() 

ans = combination(m+n, m, MOD)
print(ans)

Submission status: Accepted

Solution code:
MOD=10**9+7
def modpow(a,n,mod):
    res=1
    a=a%mod
    while(n>0):
        if(n&1):
            res=res*a%mod
        a=a*a%mod
        n>>=1
    return res

def com(n,k,mod):
    res=1
    tmp=1
    for i in range(1,k+1):
        res=res*(n-i+1)%mod
        tmp=tmp*i%mod
    a=modpow(tmp,1000000005,mod)
    return res*a%mod

X,Y=map(int,input().split())
if((X+Y)%3!=0):
    print(0)
    exit()
m=(2*X-Y)//3
n=(2*Y-X)//3
if(m<0 or n<0):
    print(0)
    exit()
print(com(m+n,m,MOD))

Submission status: Accepted

Solution code:
def gcd1(a, b):
    def calc(a, b, first, second):
        if a < b:
            a, b = b, a
        r = a % b
        q = -(a - r)//b
        if r == 0:
            return b, second
        # first += q * second
        first = [x + q * y for (x, y) in zip(first, second)]
        return calc(r, b, second, first)
    first = [1, 0]
    second = [0, 1]
    return calc(a, b, first, second)

def mod_inv(n, mod):
    table = gcd1(n, mod)
    inv = table[1][1]
    if inv < 0:
        inv += mod
    return inv

def cmb(n, r, mod):
    ans = 1
    for i in range(r):
        ans = (ans * n) % mod
        n -= 1
    ans1 = 1
    for i in range(1, r + 1):
        ans1 = (ans1 * i) % mod
    return ans * mod_inv(ans1, mod)

def main():
    m = 10**9 + 7
    X, Y = map(int, input().split())
    XY = X + Y
    min_xy = XY // 3
    max_xy = XY - min_xy
    if XY % 3 != 0:
        print(0)
        return
    if X < min_xy or X > max_xy or Y < min_xy or Y > max_xy:
        print(0)
        return
    index_x = X - min_xy
    index_y = Y - min_xy
    # print(index_x, index_y)
    ans = cmb(min_xy, index_x, m)
    print(ans % m)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD=10**9+7

def powmod(a,p):
  if p==0:
    return 1
  elif p==1:
    return a
  elif p%2==0:
    powsq=powmod(a,p//2)
    return (powsq**2)%MOD
  elif p%2==1:
    powsq=powmod(a,p//2)
    return (a*powsq**2)%MOD

def invmod(a):
  return powmod(a,MOD-2)

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

if (X+Y)%3!=0:
  print(0)
else:
  u=(2*X-Y)//3
  v=(-X+2*Y)//3
  if u>=0 and v>=0:
    #print(int(u),int(v))
    ui=int(u)
    vi=int(v)

    bunshi=1
    for i in range(vi):
      bunshi*=ui+vi-i
      bunshi%=MOD
    bumbo=1
    for i in range(vi):
      bumbo*=vi-i
      bumbo%=MOD

    #calculate bunshi/bumbo%MOD as bunshi*bumbo^-1%MOD
    print(bunshi*invmod(bumbo)%MOD)
  else:
    print(0)

Submission status: Accepted

Solution code:
#組み合わせ総数
mod = 10 ** 9 + 7
def comb(n, k):
    res = 1
    for i in range(n - k + 1, n + 1):
        res = res * i % mod
    for i in range(1, k + 1):
        res = res * pow(i, mod - 2, mod) % mod
    return res

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

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

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

if n >= 0 and m >= 0:
    print(comb(m + n,min(m,n)))
else:
    print(0)

Submission status: Accepted

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

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

if (X+Y)%3 != 0 :
    print(0)
elif X < (X+Y)//3 or Y < (X+Y)//3 :
    print(0)
else :
    i = X - (X+Y)//3
    print(comb((X+Y)//3, i, mod))

Submission status: Accepted

Solution code:
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()

def C(n, r ,mod=10**9+7):
    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]) %mod

    return result % mod

print(C(a+b,b))

Submission status: Accepted

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

a = (2 * x - y) // 3
b = (2 * y - x) // 3
rent_a = (2 * x - y) % 3
rent_b = (2 * y - x) % 3

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

if a < 0 or b < 0:
    ans = 0
elif rent_a != 0 or rent_b != 0:
    ans = 0
else:
    n = a + b
    ans = combination(n, a)

print(ans)

Submission status: Accepted

Solution code:
def solve(x, y):
    if (x + y) % 3 != 0:
        return 0
    n = (x + y) // 3
    r = min((2 * y - x) // 3, (2 * x - y) // 3)
    return cmb(n, r, mod)

_x, _y = map(int, input().split())

mod = 10 ** 9 + 7
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inverse = [0, 1] # 逆元テーブル計算用テーブル

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

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

print(solve(_x, _y))

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

MOD = 10**9+7

def calc(x, y):
    return int((x + y) / 3), int((2*x - y) / 3)

def mod_cmb(n, r, mod):
    if r == 0:
        return 1
    x = 1
    y = n
    for i in range(2,r+1):
        x *= i
        x %= mod
        y *= n-i+1
        y %= mod
    return y * pow(x, mod-2, mod) % mod


def main():
    x, y = input_nums()
    if (x+y) % 3 != 0:
        print(0)
        exit(0)
    n, m = calc(x, y)
    if n < 0 or m < 0:
        print(0)
        exit(0)
    ans = mod_cmb(n, m, MOD)
    print(ans % MOD)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

#フェルマーの小定理を用いてcombの計算を行う
def comb(n, k, mod, frac):
    a=frac[n]
    b=frac[k]
    c=frac[n-k]
    return (a * pow(b, mod-2, mod) * pow(c, mod-2, mod)) % mod

if 2*y-x < 0 or 2*x-y < 0:
  print(0)
elif (2*y-x)%3 != 0 or (2*x -y) % 3 != 0:
  print(0)
else:
  a = int((2*y-x)//3)
  b = int((2*x-y)//3)
  mod = 10**9 + 7
  frac = [1]
  for i in range(a+b):
      frac.append(frac[i]*(i+1)%mod)
  print(comb(a + b, a, mod, frac))

Submission status: Accepted

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

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

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

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

"""Combination(mod付き)の高速計算"""
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)

ans = modcomb(n+m, m, 10**9+7)
print(ans)

Submission status: Accepted

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

#2n+n==X+Y
#x-n, y-n
#n=(X+Y)//3
#(x-n+y-n)C(x-n)
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  # 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)

#print(cm(n, r, p))

if (X+Y)%3!=0:
  print(0)
else:
  n=(X+Y)//3
  print(cmb(X+Y-2*n, X-n, p))

Submission status: Accepted

Solution code:
# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math
mod = 10**9 + 7

# n = int(input())
# a = list(map(int, input().split()))
def fac(n):
    a = n
    t = 1
    while a > 0:
        t *= a
        t %= mod
        a -= 1
    return t


def C(n,r):
    return (fac(n) * pow(fac(r),mod-2,mod) * pow(fac(n-r),mod-2,mod) )%mod

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

ans = 0

if (x+y)%3==0 and max(x,y)-min(x,y)<=min(x,y):
    diff = max(x,y)-min(x,y)
    total = (x+y)//3
    ans = C(total,(total-diff)//2)

print(ans)

Submission status: Accepted

Solution code:
X,Y = map(int,input().split())
mod = 10**9+7
if (2*X-Y) % 3 != 0 or (2*Y-X) % 3 != 0:
    print(0)
    exit(0)
x,y = (2*Y-X)//3,(2*X-Y)//3
if x < 0 or y < 0:
    print(0)
    exit(0)
N = x+y
K = min(x,y)
def pow(x, n, mod):
    ret = 1
    while n>0:
        if (n&1):
            ret = (ret*x) % mod
        x = (x*x) % mod
        n >>= 1
    return ret
fact = [0]*(N+1)
fact[0] = 1
for i in range(1, N+1):
    fact[i] = (fact[i-1]*i) % mod
finv = [0]*(N+1)
finv[N] = pow(fact[N], mod-2, mod)
for i in range(N, 0, -1):
    finv[i-1] = (finv[i]*i) %mod
print((fact[x+y]*finv[x]*finv[y]) % mod)

Submission status: Accepted

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

def kai(x, p):
    a = 1
    for i in range(1, x + 1):
        a *= i
        a %= p
    return a

def comb(a, b, p):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= kai(a, p)
    c *= pow(kai(b, p), p - 2, p)
    c *= pow(kai(a - b, p), p - 2, p)
    return c % p

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

z = (x + y) // 3
p = 10 ** 9 + 7
print(comb(x + y - 2 * z, x - z, p))

Submission status: Accepted

Solution code:
from itertools import combinations
# from math import factorial as f
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

MOD = 10**9 + 7
def main():
    X, Y = map(int, input().split())
    a = 2 * X - Y
    if a % 3 != 0 or a < 0:
        print(0)
        return
    a = a // 3

    b = 2 * Y - X
    if b % 3 != 0 or b < 0:
        print(0)
        return
    b = b // 3

    total = a + b
    fac, ifac = make_tables(MOD, total)
    ans = cmb(a+b, min(a, b), MOD, fac, ifac)
    print(ans)


main()

Submission status: Accepted

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

MOD = 10 ** 9 + 7
class modint:
    def __init__(self, x):
        self.x = x.x if isinstance(x, modint) else x % MOD
    def __str__(self): return str(self.x)
    __repr__ = __str__
    def __int__(self): return self.x
    __index__ = __int__
    def __add__(self, other): return modint(self.x + modint(other).x)
    def __sub__(self, other): return modint(self.x - modint(other).x)
    def __mul__(self, other): return modint(self.x * modint(other).x)
    def __pow__(self, other): return modint(pow(self.x, modint(other).x, MOD))
    def __floordiv__(self, other): return modint(self.x * pow(modint(other).x, MOD - 2, MOD))
    def __lt__(self, other): return self.x < modint(other).x
    def __gt__(self, other): return self.x > modint(other).x
    def __le__(self, other): return self.x <= modint(other).x
    def __ge__(self, other): return self.x >= modint(other).x
    def __eq__(self, other): return self.x == modint(other).x
    def __ne__(self, other): return self.x != modint(other).x
    def inv(self): return pow(self.x, MOD - 2, MOD)

def modC(n, r):  # nCr = n!/(n-r)!r!
    r = min(r, n - r)
    ans = modint(1)
    for i in range(n, n - r, -1):
        ans *= i
    for i in range(2, r + 1):
        ans //= i
    return ans

if (2 * Y - X) % 3 != 0 or (2 * X - Y) % 3 != 0:
    print(0)
else:
    a, b = (2 * Y - X) // 3, (2 * X - Y) // 3
    if a == 0 and b == 0:
        print(1)
    elif a < 0 or b < 0:
        print(0)
    else:
        print(modC(a + b, a))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#コンビネーション
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 = 10 ** 6  # 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)

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

if (2 * y - x) % 3 != 0 and (2 * x - y) % 3 != 0:
    print(0)
else:
    a = (2 * y - x) // 3
    b = (2 * x - y) // 3
    ans = cmb(a+b, a)
    print(ans % (pow(10, 9) + 7))

Submission status: Accepted

Solution code:
def cmb(n,r,mod):
    r=min(r,n-r)
    if r==0:
        return 1
    elif r<0:
        return 0
    else:
        X=1
        Y=1
        for i in range(r):
            X*=n-i
            X%=mod
            Y*=i+1
            Y%=mod
        Y=pow(Y,mod-2,mod)
        X*=Y
        return X%mod

if __name__ == "__main__":
    X,Y=map(int,input().split())
    if (2*Y-X)%3!=0 or (2*X-Y)%3!=0:
        print(0)
    else:
        xd=(2*X-Y)//3
        yd=(2*Y-X)//3
        print(cmb(xd+yd,yd,10**9+7))

Submission status: Accepted

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

    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
    r = X - n
    print(COMB(n, r))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from numpy.linalg import solve
import math
import sys
input = sys.stdin.readline

MOD = 10 ** 9 + 7



def main():
    X, Y = map(int, input().split())

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

    left = [[2, 1], [1, 2]]
    right = [X, Y]

    n, m = map(int, solve(left, right))

    if n < 0 or m < 0:
        print(0)
        quit()

    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]

    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

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

    print(cmb(n+m, n))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
x,y=map(int,input().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):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
if x/y>2 or x/y<0.5 or (x+y)%3!=0:
    print(0)
    exit()
a=(2*x-y)//3
print(cmb((x+y)//3,a)%(10**9+7))

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

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 は必要分だけ用意する
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()
ans = 0
if (x + y) % 3 == 0:
    a = (2 * y - x) // 3
    b = (2 * x - y) // 3
    ans = cmb(a + b, a)
print(ans)

Submission status: Accepted

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

mod = 10**9 + 7
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
N = 10**6
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

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)

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

k = (x + y) // 3
n = x - k
m = y - k
ans = cmb(n + m, n, mod)
print(ans)

Submission status: Accepted

Solution code:
def solve():
    mod = 10 ** 9 + 7
    fac, finv, inv = COMinit(10 ** 6, mod)

    X, Y = map(int, input().split())
    if (X + Y) % 3 != 0:
        print(0)
        return
    
    ans = 0
    for one_cnt in range(10 ** 6):
        x1 = one_cnt * 2
        y1 = one_cnt * 1
        remain_x = X - x1
        remain_y = Y - y1
        if remain_x * 2 != remain_y or remain_x < 0 or remain_y < 0:
            continue
        two_cnt = remain_x
        ans += COM(one_cnt+two_cnt, one_cnt,mod,fac,finv,inv)
    
    print(ans)

def n_combination(n, r, mod):
    numer_sum = 1
    denom_sum = 1
    for i in range(r):
        numer_sum *= n - i
        numer_sum % mod
        denom_sum *= r - i
        numer_sum % mod
    
    return numer_sum * modinv(denom_sum, mod) % mod

def modinv(a, mod):
    return pow(a, mod-2, mod)
    
def COMinit(N, mod):
    fac = [0] * N
    finv = [0] * N
    inv = [0] * N

    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1

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

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

if __name__ == '__main__':
    solve()