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:
def sq(a, b, mod):  # aのb乗を剰余
    if b == 0:
        return 1
    elif b % 2 == 0:
        return sq(a, b // 2, mod)**2 % mod
    else:
        return sq(a, b - 1, mod) * a % mod
  
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

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

def nCk(n,k,mod):
  prev=1
  for i in range(1,min(k,n-k)+1):
    v=(prev * (n+1-i) % mod * modinv(i, mod) % mod)
    prev=v
  return prev

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

if (x+y)%3!=0:
  print(0)
else:
  n=(x+y)//3
  k=(2*x-y)//3
  if k<0 or k>n:
    print(0)
  else:
    print(nCk(n,k,mod))

Submission status: Accepted

Solution code:
X, Y = map(int, input().split())
n = (2 * X - Y) / 3
m = (2 * Y - X) / 3

if n < 0 or m < 0 or not n.is_integer() or not m.is_integer():
    print(0)
    exit()

MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

n, m = map(int, [n, m])
fact = [ModInt(1)]
for i in range(1, X + Y + 1):
    fact.append(fact[i-1] * i)

def cmb(n, r):
    return fact[n] / fact[n-r] / fact[r]

print(cmb(n+m, min(n, m)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def power_expo(x, y):
    """Returns x^y.

    <https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6>

    結局, 組み込み関数の `pow()` のほうが速そう. 第3引数でmodもできる.
    """
    if y == 0:
        return 1
    elif y % 2 == 0:
        return power_expo(x, y // 2) ** 2 % MOD
    else:
        return power_expo(x, y // 2) ** 2 * x % MOD


def combinations_mod(n, r, mod=1000000007):
    """Returns nCr in mod."""
    combs = 1
    for i, j in zip(range(n - r + 1, n + 1), range(1, r + 1)):
        combs = combs % mod * i % mod * pow(j, mod - 2, mod) % mod
    return combs


def main():
    x, y = [int(x) for x in input().split()]
    if (x + y) % 3 != 0:
        return 0
    summ = (x + y) // 3     # d + r
    diff = x - y  # d - r
    if summ % 2 != diff % 2:
        return 0
    d = (summ + diff) // 2  # Down
    r = (summ - diff) // 2  # Right
    if d < 0 or r < 0:
        return 0
    chosen = min(d, r)

    patterns = combinations_mod(summ, chosen)

    return patterns


if __name__ == '__main__':
    print(main())

# やはり難しい，再び解説。割り算のときは mod 10^9+7 が厄介。
# とりあえず，割る方は 10^9+5 乗して掛ければいいらしい。
# でかい累乗, pow() なら間に合うな. Python3 1310 ms; Pypy3 457 ms.

Submission status: Accepted

Solution code:
import sys
import math
input = sys.stdin.readline
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

x,y=MI()
if y>2*x or x>2*y:
    print(0)
    sys.exit()
elif x%3==0 and y%3==0:
    m=x//3
    l=y//3
    print(cmb(m+l,2*l-m,mod))
    
elif x%3==1 and y%3==2:
    m=(x-1)//3
    l=(y-2)//3
    print(cmb(m+l+1,2*l-m+1,mod))
elif x%3==2 and y%3==1:
    m=(x-2)//3
    l=(y-1)//3
    print(cmb(m+l+1,2*l-m,mod))
else:
    print(0)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def power_expo(x, y):
    """Returns x^y.

    <https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6>

    結局, 組み込み関数の `pow()` のほうが速そう. 第3引数でmodもできる.
    """
    if y == 0:
        return 1
    elif y % 2 == 0:
        return power_expo(x, y // 2) ** 2 % MOD
    else:
        return power_expo(x, y // 2) ** 2 * x % MOD


def main():
    x, y = [int(x) for x in input().split()]
    if (x + y) % 3 != 0:
        return 0
    summ = (x + y) // 3     # d + r
    diff = x - y  # d - r
    if summ % 2 != diff % 2:
        return 0
    d = (summ + diff) // 2  # Down
    r = (summ - diff) // 2  # Right
    if d < 0 or r < 0:
        return 0
    chosen = min(d, r)

    patterns = 1

    for i, j in zip(range(summ - chosen + 1, summ + 1), range(1, summ + 1)):
        patterns = patterns % MOD * i % MOD * pow(j, MOD - 2, MOD) % MOD

    return patterns


if __name__ == '__main__':
    print(main())

# やはり難しい，再び解説。割り算のときは mod 10^9+7 が厄介。
# とりあえず，割る方は 10^9+5 乗して掛ければいいらしい。

Submission status: Accepted

Solution code:
p = 10**9+7
def nCr(n,r):
    if r*2>n:
        return nCr(n,n-r)
    else:
        a = b = 1
        for i in range(r):
            a = a * (n - i) % p
            b = b * (r - i) % p
        return (a * pow(b,p-2,p)) % p

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

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

print(int(nCr(a+b, a)))

Submission status: Accepted

Solution code:
X, Y = map(int, input().split())
n = (2 * X - Y) / 3
m = (2 * Y - X) / 3

if n < 0 or m < 0 or not n.is_integer() or not m.is_integer():
    print(0)
    exit()

n, m = map(int, [n, m])
mod = 10**9 + 7
fact = [1]
inv = [1]
for i in range(1, X + Y + 1):
    fact.append((fact[i-1] * i) % mod)
    inv.append(pow(fact[-1], mod-2, mod))

def cmb(n, r):
    return fact[n] * inv[n-r] * inv[r]

print(cmb(n+m, min(n, m)) % mod)

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
if (2*b-a)%3==0 and (2*a-b)%3==0 and (2*b-a)>=0 and (2*a-b)>=0:
  n=(2*b-a)//3
  m=(2*a-b)//3
  p = 10**9+7
  def nCr(n,r):
    if r*2>n:
        return nCr(n,n-r)
    else:
        a = b = 1
        for i in range(r):
            a = a * (n - i) % p
            b = b * (r - i) % p
        return (a * pow(b,p-2,p)) % p

  print(nCr((m+n),m))
else:
  print(0)

Submission status: Accepted

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

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

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

    if (X+Y)%3==0 and Y<=X*2 and X<=Y*2:
        n = (X+Y)//3
        r = X-(X+Y)//3
        print(combMod(n, r, p))
    else:
        print('0')

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
# 組み合わせ計算
# 約分してから計算するアルゴリズム
# 10^9 + 7 で割ったあまりを返すバージョン
MOD = 1000000007

def combination(n, r):
    # n >= 0, r >= 0, r <= n を仮定
    if n < 0 or r < 0 or n < r:
        return -1

    # r <= n - r を仮定
    if n - r < r:
        r = n - r

    # r < 2 の場合
    if r == 0:
        return 1
    if r == 1:
        return n

    # nCr の分子
    # [n - r + 1, n - r + 2, ... , n - 1, n]
    numerator = [n - r + 1 + i for i in range(r)]


    # nCr の分母
    # [1, 2, ... , r - 1, r]
    denominator = [i + 1 for i in range(r)]

    # nCr を約分する
    for i in range(r):
        # i番目の分母で約分する
        # 0番目は1なので省略

        # 元の（今までの約分を行う前の）i番目の分母の値
        original_denominator = i + 1

        # 今までの約分を行った後の、i番目の分母の値
        # 今回の約分で割る数
        divisor = denominator[i]

        # divisorが1（全て約分済み）の場合は無視する
        if divisor == 1:
            continue

        # 約分する相手の分子を決める
        # 0～i番目の分子（約分前）の中で、
        # original_denominatorで割り切れる数
        # （一つしかない）を選ぶ
        # remainder = i番目の分子 % original_denominator
        # とするとき、
        # (i - remainder)番目の分子 = i番目の分子 - remainder
        # (i - remainder)番目の分子 % original_denominator
        #  = (i番目の分子 - remainder) % original_denominator
        #  = 0
        # なので、(i - remainder)番目の分子を選べばよい。

        # remainder = i番目の分子 % original_denominator
        #           = (n - r + i + 1) % (i + 1)
        #           = (n - r) % (i + 1)
        remainder = (n - r) % original_denominator

        # divisor で約分できるペアをすべて約分する
        for j in range(i, r, original_denominator):
            numerator[j - remainder] = numerator[j - remainder] // divisor
            denominator[j] = denominator[j] // divisor

    ans = 1
    for i in numerator:
        ans = (ans * i) % MOD
    return ans

X, Y = map(int, input().split())
if X < Y:
    d = Y - X
    n = X
else:
    d = X - Y
    n = Y

# (n, n + d)
if (n - d) % 3 != 0 or n < d:
    print(0)
else:
    print(combination((2*n + d) // 3, (n - d) // 3))

Submission status: Accepted

Solution code:
#nCrをmodで割った余りO(r)
def comb(n, r, mod):
    r = min(r, n-r)
    mol = 1
    deno = 1
    for i in range(1, r+1):
        mol = mol * (n-r+i) % mod
        deno = deno * i % mod
    ret = mol * pow(deno, mod-2, mod) % mod
    return ret

x,y = map(int,input().split())
if (x+y)%3 != 0 or 2*y-x < 0 or 2*x-y < 0:
    print(0)
else:
    a = (2*y-x)//3
    b = (2*x-y)//3
    mod = 10**9+7
    print(comb(a+b,a,mod))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


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


x, y = map(int, readline().split())
if (x + y) % 3 != 0 or not (x <= 2 * y and y <= 2 * x):
    print(0)
else:
    n = (x + y) // 3
    print(combination(n, y - n))

Submission status: Accepted

Solution code:
import sys
#import bisect
#from collections import deque
import math

def input():
    return sys.stdin.readline().rstrip('\n')


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

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

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

M = max((2*X-Y)//3, (2*Y-X)//3)
N = min((2*X-Y)//3, (2*Y-X)//3)

if M<0 or N<0:
    print(0)
    sys.exit()
    
mod = pow(10,9) + 7

#from scipy.special import comb
#print(comb(M+N,N) % (pow(10,9) + 7))
#print(comb(M+N,N, exact=True)% (pow(10,9) + 7))  causes "RE" at atcoder
#from math import factorial
#print((factorial(M+N)//factorial(M)//factorial(N)))

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

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

def ohmycomb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

print(ohmycomb(M+N, N, mod))

Submission status: Accepted

Solution code:
def modinv(a,m):
    return pow(a,m-2,m)

x,y = map(int,input().split())
if (x+y)%3 != 0 or 2*y-x < 0 or 2*x-y < 0:
    print(0)
else:
    a = (2*y-x)//3
    b = (2*x-y)//3
    ans = 1
    mod = 10**9+7
    for i in range(1,a+1):
        ans = ans*(i+b)*modinv(i,mod)%mod
    print(ans)

Submission status: Accepted

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

def cmb(n,k):
    x,y=1,1
    for i in range(k):
        x = x * (n-i)%mod
        y = y * (k-i)%mod
    return x*pow(y,mod-2,mod)%mod

if (X+Y)%3!=0:
    print(0)
else:
    m=(2*X-Y)//3
    n=(2*Y-X)//3
    if n<0 or m<0:
        print(0)
    else:
        mod=10**9+7
        ans=cmb(n+m,min(n,m))
        print(ans)

Submission status: Accepted

Solution code:
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 =    2 * x -  y 
b =   - x + 2 * y 

ans = 0
if a % 3 == 0 and b % 3 == 0:
    a = a//3
    b = b//3
    ans = cmb(a+b, a, mod)
print(ans)

Submission status: Accepted

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

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

def combi(n,r,mod=10**9+7):
    fac = [0]*(n+1)
    fac[0] = 1
    fac[1] = 1
    for i in range(2,n+1):
        fac[i] = fac[i-1] * i % mod
    return( ( fac[n] * modinv(fac[r]) )%mod * modinv(fac[n-r]) % mod)

if (X+Y) % 3 != 0 or X > 2*Y or Y > 2*X:
    print(0)
else:
    n = X - (X + Y)//3
    m = (X + Y)//3 - n
    print(combi(n+m,m))

Submission status: Accepted

Solution code:
MOD = 1000000007
import sys
x, y = map(int, input().split())

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

#nCr n*(n-1)*...*(n-r+1)/(r*(r-1)*...*1)

def pow_k(x, n, MOD):
  if n==0:
    return 1
  res = 1
  while n:
    if n&1:
      res = res*x%MOD
    x = x*x%MOD
    n = n>>1
  return res

def comb(n, r, MOD):
  numerator = 1
  denominator = 1
  
  for i in range(r):
    numerator = numerator * (n-i) % MOD
    
  inv = [1]*r
  for i in range(r):
    inv[i] = pow_k(i+1, MOD-2, MOD)
  
  for i in range(r):
    denominator = denominator * inv[i]%MOD
  
  return numerator*denominator%MOD

if a<b:
  a, b = b, a
  
print(comb(a+b, b, MOD))

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
MAX_NUM = 2*10**6 + 1
MAX_NUM//=3
MAX_NUM+=1
pr = 10**9+7
fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]
fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % pr
    inv[i] = pr - inv[pr%i] * (pr // i) % pr
    finv[i] = finv[i-1] * inv[i] % pr
def c(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % pr) % pr
if (x+y)%3:
    print(0)
else:
    n=(x+y)//3
    x-=n
    y-=n
    print(c(x+y,x))

Submission status: Accepted

Solution code:
import numpy as np

def nCr(n,r):
    if r*2>n:
        return nCr(n,n-r)
    mod = 10 ** 9 + 7
    a = b = 1
    for i in range(r):
        a = (a * (n - i)) % mod
        b = (b * (r - i)) % mod
    return (a * pow(b,mod-2,mod))%mod

X,Y = map(int,input().split())
if (X+Y)%3 != 0:
    print(0)
else:
    left = np.array([[1,2],[2,1]])
    right = np.array([X,Y])
    n = int(np.linalg.solve(left,right)[0])
    m = int(np.linalg.solve(left,right)[1])
    if n < 0 or m < 0 :
        print(0)
    else:
        print(nCr(n+m,n))

Submission status: Accepted

Solution code:
from functools import reduce
mod = 10**9+7

def P(n, k):
  return reduce(lambda x, y:x*y%mod, range(n-k+1, n+1))

def factorial(n):
  return 1 if n == 0 else P(n, n)

X, Y = map(int, input().split())
L, S = max(X, Y), min(Y, X)
if (S-(L-S))%3 != 0 or S-(L-S) < 0:
  print(0)
else:
  s = (S-(L-S))//3
  l = (S-(L-S))//3+(L-S)
  bunshi = factorial(s+l)
  bunbo = (factorial(s)*factorial(l))%mod
  print((bunshi*pow(bunbo,mod-2, mod))%mod)

Submission status: Accepted

Solution code:
from functools import reduce
mod = 10**9+7

def P(n, k):
  return reduce(lambda x, y:x*y%mod, range(n-k+1, n+1))

def factorial(n):
  return P(n, n)

def C(n, k):
  k = min(k, n-k)
  if k == 0:
    return 1
  else:
    return (P(n, k)*pow(factorial(k), mod-2, mod))%mod

X, Y = map(int, input().split())
if (X+Y)%3 == 0:
  n = Y-(X+Y)//3
  m = X-(X+Y)//3
  if n < 0 or m < 0:
    print(0)
  else:
    print(C(n+m, n))
else:
  print(0)

Submission status: Accepted

Solution code:
mod = 10**9+7

def comb(n, r):
    if 2 * r > n: return comb(n, n-r)
    return fac[n] * inv[r] * inv[n-r] % mod

x, y = map(int, input().split())
if (x+y) % 3 != 0:
  print(0)
  exit()
     
n = (x+y)//3
x -= n
y -= n
if x<0 or y<0:
  print(0)
  exit()
  
fac = [1] * (n+2)
inv = [1] * (n+2)
for i in range(2, n+1):
    fac[i] = fac[i-1] * i % mod
inv[n] = pow(fac[n], mod - 2, mod)
for i in range(n-1, 1, -1):
    inv[i] = inv[i + 1] * (i + 1) % mod
  
print(comb(x+y, x) % mod)

Submission status: Accepted

Solution code:
mod = 10**9+7
n = 10**6

def comb(n, r):
    if 2 * r > n: return comb(n, n-r)
    return fac[n] * inv[r] * inv[n-r] % mod

x, y = map(int, input().split())
if (x+y) % 3 != 0:
  print(0)
  exit()
     
a = -(x-2*y)//3
b = (2*x-y)//3 
if a<0 or b<0:
  print(0)
  exit()
  
fac = [1] * (n+2)
inv = [1] * (n+2)
for i in range(2, n+1):
    fac[i] = fac[i-1] * i % mod
inv[n] = pow(fac[n], mod - 2, mod)
for i in range(n-1, 1, -1):
    inv[i] = inv[i + 1] * (i + 1) % mod
  
print(comb(a+b, a) % mod)

Submission status: Accepted

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

#----------------------------------------------------

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


if (X+Y)%3 == 0:
    L=(2*Y-X)//3
    R=(2*X-Y)//3

    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(cmb(L+R, min(L,R), p))
else:
    print(0)

Submission status: Accepted

Solution code:
i, j = map(int, input().split())

if (i + j) % 3 != 0 or (max(i, j) / min(i, j) > 2):
  print(0)
else:
  TW = (i + j) // 3
  W = (TW - (i-j)) // 2

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

  print(mod_cmb(TW, W))

Submission status: Accepted

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

class Combination:
    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):
        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):
        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

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

if (X+Y) % 3 != 0 or m < 0 or n < 0:
    print(0)
else:
    comb = Combination(10**6)
    print(comb(n+m,n))

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

def make_fac_tables_mod_p(n, p):
  fac = [0] * (n+1)
  fac_inv = [0] * (n+1)
  mod_inv = [0] * (n+1)
  fac[0] = fac[1] = 1
  fac_inv[0] = fac_inv[1] = 1
  mod_inv[1] = 1
  for i in range(2, n+1):
    fac[i] = (fac[i-1] * i) % p
    mod_inv[i] = p - mod_inv[p % i] * (p // i) % p
    fac_inv[i] = fac_inv[i-1] * mod_inv[i] % p
  return fac, fac_inv

def nCk_mod_p(fac, fac_inv, n, k, p):
  return ((fac[n] * fac_inv[n-k]) % p) * fac_inv[k] % p

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

ans = 0
q, r = divmod(X+Y, 3)
if r == 0 and (q <= X <= 2*q) and (q <= Y <= 2*q):
  n = q
  k = X - q
  fac, fac_inv = make_fac_tables_mod_p(n, MOD)
  ans = nCk_mod_p(fac, fac_inv, n, k, MOD)

print(ans)

Submission status: Accepted

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


X, Y = map(int, sys.stdin.readline().split())

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

if n.is_integer() and m.is_integer():
    n = int(n)
    m = int(m)

    ans = int(cmb(n + m, n, p))
    
    print(ans)
    
else:
    print(0)

Submission status: Accepted

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

X,Y=map(int,input().split())
ans=0
n=min(X,Y//2)
for i in range(n+1):
  XY=[X-i,Y-2*i]
  if XY[0]==2*XY[1]:
    j=XY[0]//2
    ans+=cmb(i+j,i,p)

print(ans)

Submission status: Accepted

Solution code:
def COM(n, r):
    fac = [1, 1]
    finv = [1, 1]
    inv = [0, 1]
    for i in range(2, MAX):
        fac.append(fac[i - 1] * i % MOD)
        inv.append(-inv[MOD % i] * (MOD // i))
        finv.append(finv[i - 1] * inv[i] % MOD)
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD
 
 
MOD = 10 ** 9 + 7
MAX = 10 ** 6

X, Y = map(int, input().split())
a = X + Y
if(a % 3 != 0 or X < (a // 3) or Y < (a // 3)):
  print(0)
else:
  b = a // 3
  x = X-b
  y = Y-b
  c = x+y
  print(COM(c, x))

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7

def cmb(n, k):
    if k < 0 or k > n: return 0 
    return fact[n] * fact_inv[k] % MOD * fact_inv[n-k] % MOD

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

U = 10 ** 6 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)
X, Y = lr()
if (X+Y)%3 != 0 or X > Y + Y or Y > X + X:
    print(0); exit()

time = (X+Y) // 3
diff = abs(X-Y)
a = (time-diff)//2
# timeCaが答え
answer = cmb(time, a)
print(answer%MOD)

Submission status: Accepted

Solution code:
def factorial(n, r, p):
    ret = 1
    for i in range(n, n - r, -1):
        ret = (ret * i) % p
    return ret


def comb(n, r, p):
    r = min(r, n - r)
    return (factorial(n, r, p) * pow(factorial(r, r, p), p - 2, p)) % p


mod = 10 ** 9 + 7
x, y = map(int, input().split())
a = (2 * y - x) // 3
b = (2 * x - y) // 3
if (x + y) % 3 != 0 or a < 0 or b < 0:
    ans = 0
else:
    ans = comb(a + b, a, mod)
print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
x, y = map(int, input().split())
a = (2 * y - x) // 3
b = (2 * x - y) // 3
if (x + y) % 3 != 0 or a < 0 or b < 0:
    print(0)
    exit()
n = a + b
r = min(a, b)
ans = 1
for i in range(r):
    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 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:
mod = 7+10**9
def ncr(n,c,mod):
  x = 1
  y = 1
  for i in range(n-c+1,n+1):
    x = x*i%mod
  for j in range(1,c+1):
    y = y*j%mod
  return (x * pow(y, 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 < 0 or m < 0:
  print(0)
  exit()

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

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
flag = True
for j in range(0,x//2+2):
    nup = j*2
    nright = (x-nup)
    if( j+2*nright == y)&(nright >= 0):
        flag = False
        break
        
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 )

    
if flag == False:
    a = cmb((j+nright),j ,mod)
    print(a)
    
else:
    print(0)

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
flag = False
n = int((2*x-y)/3)
m = int((2*y-x)/3)

if (n >= 0) & ( m >= 0 ) & ((x+y)%3 == 0):
    flag = True

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 )

    
if flag == True:
    a = cmb((m+ n),n ,mod)
    print(a)
    
else:
    print(0)

Submission status: Accepted

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

mod = 10 ** 9 + 7

def make_fact(n):#0~nの階乗を求める
    fact = [1]*(n+1)
    for i in range(1, n+1):
        fact[i] = fact[i-1]*i%mod
    return fact
fact = make_fact(10 ** 6) #＠
def make_fact_inv(n):#0~nの階乗のmodに関する逆元を求める
    fact_inv = [1]*(n+1)
    fact_inv[n] = pow(fact[n], mod-2, mod)#フェルマーの小定理
    for i in range(n, 0, -1):
        fact_inv[i-1] = fact_inv[i]*i%mod
    return fact_inv
fact_inv = make_fact_inv(10 ** 6)#＠
def comb(n, k):#nCk
    return fact[n]*fact_inv[k]*fact_inv[n-k]%mod





def solve():
    if (x + y) % 3 != 0:
        return 0
    ab = (x + y) // 3
    if x < ab or x > 2 * ab:
        return 0
    a = x - ab
    return comb(ab, a)

print(solve())

Submission status: Accepted

Solution code:
import math
X,Y=map(int,input().split())
mod=pow(10,9)+7
if (X+Y)%3!=0:
    print(0)
else:
    m=(X*2-Y)//3
    n=X-2*m
    if n<0 or m<0:
        print(0)
    else:
        def comb(a,b):
            x=1
            for i in range(a-b+1,a+1):
                x*=i
                x%=mod
            y=1
            for j in range(1,b+1):
                y*=j
                y%=mod
            return x*pow(y,mod-2,mod)%mod
        print(comb(n+m,n))

Submission status: Accepted

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

# (1,2)か(2,1)で割り切れる場合
if (2*y-x)%3 == 0 and (2*x-y)%3 == 0:
    m = (2*y-x)//3
    n = (2*x-y)//3

    # 連立方程式の解のそれぞれが0以上の時
    if n >= 0 and m >= 0:
        print( str(int(cmb(n+m,n, mod) % (10e9+7)) ))
    else:
        print(0)
# 到達できない場合
else:
    print(0)

Submission status: Accepted

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

if (2*y-x)%3 == 0 and (2*x-y)%3 == 0:
    m = (2*y-x)//3
    n = (2*x-y)//3

    if n >= 0 or m >= 0:
        print( str(int(cmb(n+m,n, mod) % (10e9+7)) ))
    else:
        print(0)
else:
    print(0)

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
if (x+y)%3!=0:
    print(0)
    exit()

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

n=(2*y-x)//3
m=(2*x-y)//3
if n<0 or m<0:print(0)
else:print(com(n+m,n))

Submission status: Accepted

Solution code:
def f(x,r,p):
  ans=1
  for i in range(x,x-r,-1):
    ans=(ans*i)%p
  return ans
def comb(x,r,p):
  r=min(r,x-r)
  return (f(x,r,p)*pow(f(r,r,p),p-2,p))%p
x,y=map(int,input().split())
if (2*y-x)%3!=0 or (2*x-y)%3!=0 or 2*y-x<0 or 2*x-y<0:
  print(0)
  exit()
s=(2*x-y)//3
t=(2*y-x)//3
mod=10**9+7
print(comb(s+t,s,mod))