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 cmb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  return fac[n]*finv[r]*finv[n-r]%p

N = pow(10,6)
MOD = pow(10,9)+7

fac = [-1]*(N+1); fac[0] = 1; fac[1] = 1 #階乗
finv = [-1]*(N+1); finv[0] = 1; finv[1] = 1 #階乗の逆元
inv = [-1]*(N+1); inv[0] = 0; inv[1] = 1 #逆元
for i in range(2,N+1):
  fac[i] = fac[i-1]*i%MOD
  inv[i] = MOD - inv[MOD%i]*(MOD//i)%MOD
  finv[i] = finv[i-1]*inv[i]%MOD


X,Y = map(int,input().split())
if (X+Y)%3 != 0:
  print(0)
  exit()
n = (X+Y)//3
if min(X,Y) < n:
  print(0)
  exit()

ans = cmb(n,min(X,Y)-n,MOD)
print(ans)

Submission status: Accepted

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

MAX_NUM = 10**6 + 1
MOD = 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 % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def combinations(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

if (X+Y)%3 != 0:
    answer = 0
else:
    up = -(X+Y)//3+Y
    right = -(X+Y)//3+X
    answer = combinations(up+right,up)
print(answer)

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
a=-1
p=10**9+7
for i in range(x//2+1):
  if i+2*(x-2*i)==y:
    a=i
    break
if a==-1:
  print(0)
  exit()
elif a==0:
  print(1)
else:
  gyaku=[0,1]
  for i in range(2,a+1):
    gyaku.append(((p//i)*-gyaku[p%i])%p)
  com=[1]
  for i in range(1,a+1):
    com.append(com[-1]*gyaku[i]*(x-a+1-i)%p)
  print(com[-1])

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
a=-1
p=10**9+7
for i in range(x//2+1):
  if i+2*(x-2*i)==y:
    a=i
    break
if a==-1:
  print(0)
  exit()
elif a==0:
  print(1)
  exit()
else:
  gyaku=[0,1]
  for i in range(2,a+1):
    gyaku.append(((p//i)*-gyaku[p%i])%p)
  com=[1]
  for i in range(1,a+1):
    com.append(com[-1]*gyaku[i]*(x-a+1-i)%p)
print(com[-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def make_fact_list(n, MOD):
    # make factorial list from 0 to n
    fact = [0] * (n+1)
    inv = [0] * (n+1)
    factinv = [0] * (n+1)

    fact[0]=fact[1]=1
    inv[1]=1
    factinv[0]=factinv[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
    
    return fact, factinv

def cbn(n, k, MOD, fact = [], factinv = []):
    if len(fact) == 0 and len(factinv) == 0:
        fact, factinv = make_fact_list(n, MOD)
    return fact[n] * factinv[n-k] * factinv[k] % MOD


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

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

    fact, factinv = make_fact_list(s + t + 1, MOD)
    print(cbn(s+t, s, MOD, fact, factinv) % MOD)

Submission status: Accepted

Solution code:
fact = [1 for _ in range(1000000)]
inv = [1 for _ in range(1000000)]
fact_inv = [1 for _ in range(1000000)]

P = 10**9+7
for i in range(2, 1000000):
    fact[i] = (fact[i-1]*i) % P
    inv[i] = P - (inv[P % i] * (P // i)) % P
    fact_inv[i] = (fact_inv[i-1] * inv[i]) % P

X, Y = map(int, input().split())
res = 0
if (X+Y) % 3 == 0:
    a = (-X+2*Y) // 3
    b = (2*X-Y) // 3
    if a >= 0 and b >= 0:
        res = fact[a+b] * ((fact_inv[a] * fact_inv[b]) % P) % P
print(res)

Submission status: Accepted

Solution code:
# 73

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

a = 2*y - x
b = 2*x - y

fac_l = [0] * (int((a + b) / 3) + 1)
inv_l = [0] * (int((a + b) / 3) + 1)
finv_l = [0] * (int((a + b) / 3) + 1)


def com_init():
    fac_l[1] = 1
    inv_l[0] = 1
    inv_l[1] = 1
    finv_l[0] = 1
    finv_l[1] = 1
    for i in range(2, a+b+1):
        fac_l[i] = (fac_l[i-1] * i) % MOD
        inv_l[i] = MOD - (inv_l[MOD % i] * int(MOD / i)) % MOD
        finv_l[i] = (finv_l[i-1] * inv_l[i]) % MOD

def ncr(n, r):
    return (fac_l[n] * (finv_l[r] * finv_l[n-r]) % MOD) % MOD


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

    com_init()
    print(ncr(a+b, a))

Submission status: Accepted

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

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

def modinv(x):
    return modpow(x, MOD - 2)

def modf(x):
    ret = 1
    for i in range(2, x + 1):
        ret *= i
        ret %= MOD
    return ret

ans = 0
if (X + Y) % 3 == 0:
    m = (2 * X - Y) // 3
    n = (2 * Y - X) // 3
    if m >= 0 and n >= 0:
        ans = modf(m + n) * modinv(modf(n) * modf(m))
        ans %= MOD
print(ans)

Submission status: Accepted

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

import sys
if (X + Y) % 3 != 0:
    print(0)
    sys.exit()
offset = (X+Y)//3
X, Y = X-offset, Y-offset

if X<0 or Y<0:
    print(0)
    sys.exit()
    
X, Y = max(X, Y), min(X, Y)

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

print(C(X+Y, Y, mod))

Submission status: Accepted

Solution code:
class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""
    def __init__(self, n, mod):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % mod)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], mod - 2, mod)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % mod
        self.mod = mod

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.mod

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.mod

    def combination_large(self, k, r):
        """kCrを求める O(r) kが大きいが、r <= nを満たしているときに使用"""
        if k < r:
            return 0
        res = 1
        for l in range(r):
            res *= (k - l)
            res %= self.mod
        return (res * self.inv_fact[r]) % self.mod



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

if (x+y)%3 != 0:
    print(0)
    exit(0)
i = (2*x-y)//3
j = (2*y-x)//3
n = i+j
r = i
if not 0 <= r <= n:
    print(0)
    exit(0)
print(comb.combination(n, r))

Submission status: Accepted

Solution code:
kMod = 1000000007

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

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

offset = (X+Y)//3
X, Y = X-offset, Y-offset
if X < 0 or Y < 0:
    print(0)
    exit()

X, Y = max(X, Y), min(X, Y)

ans = 1
for i in range(X+1, X+Y+1):
    ans *= i
    ans %= kMod

for i in range(2, Y+1):
    ans *= pow(i, kMod-2, kMod)
    ans %= kMod

print(ans)

Submission status: Accepted

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


def f(n):
    res = n
    for i in range(1, n):
        res *= i
        res %= MOD
    return res


def solve():
    ans = 0
    if (X + Y) % 3 == 0:
        n = (2 * X - Y) // 3
        m = (2 * Y - X) // 3
        if n == 0 or m == 0:
            ans += 1
        elif n > 0 and m > 0:
            ans += (f(n + m) * pow(f(n), MOD - 2, MOD) * pow(f(m), MOD - 2, MOD)) % MOD

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

mod = 10**9+7
def factorial(N):
    if N==1 or N==1:
        return 1
    else:
        ans = N
        for i in range(1, N):
            ans*=N-i
            ans%=mod
        return ans

if 2*Y-X>=0 and (2*Y-X)%3==0 and 2*X-Y>=0 and (2*X-Y)%3==0:
    s = (2*X-Y)//3
    t = (2*Y-X)//3
    if s==0 and t==0:
        print(0)
    elif s==0:
        print(1)
    elif t==0:
        print(1)
    else:
        a = factorial(s+t)
        b = pow(factorial(s), mod-2, mod)
        c = pow(factorial(t), mod-2, mod)
        #print(a, b, c)
        print((a*b*c)%mod)
else:
    print(0)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

# ジャンプa : (i + 1, j + 2)
# ジャンプb : (i + 2, j + 1)

X,Y = map(int,readline().split())
DIV = 10 ** 9 + 7

from functools import reduce
def nCr(n,r,DIV):
  if r < n - r:
    r = n - r
  if r == 0:
    return 1
  f = lambda x,y:x*y%DIV
  X = reduce(f,range(n-r+1, n+1))
  Y = reduce(f,range(1, r+1))
  return X * pow(Y, DIV - 2, DIV) % DIV

# ジャンプaの回数は0～X回。これを全探索する
for a in range(X + 1):
  b = Y - a * 2
  if b < 0:
    continue
  if a + b * 2 == X and a * 2 + b == Y:
    print(nCr(a + b, a, DIV))
    break
else:
  print(0)

Submission status: Accepted

Solution code:
def mod_fact(N,p):
    mod=1
    for n in range(1,N+1):
        mod = (mod*(n%p))%p
        
    mod = mod%p
    
    return mod

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

Z = X+Y

ans=0

if Z%3 != 0:
    ans=0
    
elif min(X,Y) >= Z//3:
    b=0
    for z in range(Z//3,((Z//3)*2)+1):
        if z == X:
            break
        b+=1
    a = Z//3 - b 
    
    p=(10**9)+7

    Z_= mod_fact(Z//3 , p)
    a_= mod_fact(a , p)
    b_= mod_fact(b , p)

    a_= pow(a_,p-2,p)
    b_= pow(b_,p-2,p)

    ans=(Z_*(a_*b_))%p
    
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc145/tasks/abc145_d

X, Y = list(map(int, input().split()))
MOD = int(1e9 + 7)

def combination(n, r, mod=MOD):
    def modinv(a, mod=MOD):
        return pow(a, mod-2, mod)
    # nCr with MOD
    r = min(r, n - r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# 1回の移動で3増えるので，X+Yは3の倍数 (0, 0) start
if (X + Y) % 3 != 0:
    ans = 0
    print(0)
else:
    # X+Yは3の倍数
    # (+1, +2)をn回，(+2, +1)をm回実行
    # n + 2m = X
    # 2n + m = Y
    # 3 m = 2 X - Y
    # m = (2 X - Y) // 3
    # n = X - 2 * m
    
    m = (2 * X - Y) // 3
    n = X - 2 * m

    if m < 0 or n < 0:
        print(0)
    else:
        print(combination(m + n, m, MOD))

Submission status: Accepted

Solution code:
inp=list(map(int,input().split()))
x=inp[0]
y=inp[1]
if (x+y)%3!=0:
  print (0)
else:
  flag=0
  z=(x+y)//3
  n=x-z
  m=y-z
  if m<0 or n<0:
    print (0)
    flag=1
  else:
    arr=[1]
    v=pow(10,9)+7
    for i in range(1,m+n+1):
      arr.append((arr[-1]*i)%v)
    a=arr[m+n]
    b=(arr[m]*arr[n])%v
    print ((a*pow(b,v-2,v))%v)

Submission status: Accepted

Solution code:
X, Y = [int(x) for x in input().split()]
M = 10**9+7
if (X + Y) % 3:
  print(0)
else:
  x = X - (X+Y)//3
  y = Y - (X+Y)//3
  if x < 0 or y < 0:
    print(0)
  else:
    #print(x, y)
    #x+y c x
    #(x+y)!/x!/y!
    ans = 1
    for j in range(y):
      #print(j)
      #print(x+j+1, j+1)
      ans *= (x+j+1) * pow(j+1, -1, M)
      ans %= M
    print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
import heapq

sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD


def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD


def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def kaijyo(n):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * i)% MOD)
    return ret

def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid

    def pos(self, x, y):
        return y * (self.w + 2) + x + 1

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]

        ans = 0
        for i in range(1, self.h + 1):
            for j in range(1, self.w + 1):
                pass # ここから何か書いてね

def solve():
    x, y = getList()
    if (x + y) % 3 != 0 or 2 * x < y or 2 * y < x:
        print(0)
        return

    a = (2 * x - y) // 3
    b = (2 * y - x) // 3
    # print(a, b)
    fac, finv = fact_and_inv(max(x,y))
    print((fac[a+b] * divide(fac[a]) * divide(fac[b])) % MOD)



def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
#####################################################
# 組み合わせを10**9+7で割った余り、を高速に求めるアルゴリズム
# https://drken1215.hatenablog.com/entry/2018/06/08/210000
# https://qiita.com/derodero24/items/91b6468e66923a87f39f
# 全然理解できていない
MOD = 10**9 + 7


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

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())

# X+Yが3の倍数のマスしか通りえない
if not (X + Y) % 3:

    # (1,2)移動をn回、(2,1)移動をm回したとする
    # n+2m = X, 2n+m = Y
    # → n+m = (X+Y)/3
    # n = (2n+m)-(n+m) = X - (X+Y)/3 = (-X+2Y)/3
    # mも同様
    n = (2 * Y - X) // 3
    m = (2 * X - Y) // 3

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

# X+Yが3の倍数でない場合
else:
    print(0)

Submission status: Accepted

Solution code:
from functools import reduce

def mycmb(n,r,p):
    r = min(r,n-r)
    if r == 0:
        return 1
    over = reduce(lambda x,y:x*y%p,range(n,n-r,-1))
    under = reduce(lambda x,y:x*y%p,range(1,r+1))
    return (over * pow(under,p-2,p))%p


mod = 10**9+7

x,y = map(int, input().split())
n = (2*x-y) // 3
m = (2*y-x) //3

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

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

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

Submission status: Accepted

Solution code:

from functools import reduce
def comb(n, max_k, mod):
    """
    (n,k) := n個からk個選ぶ組み合わせ
    k = 0~max_Kまでを計算して返す
    """
    res = [1]*(max_k+1)
    t = 1
    for i in range(max_k+1):
        res[i] *= t
        t *= n-i
        t %= mod

    n = reduce(lambda x,y: (x*y)%mod, range(1,max_k+1), 1)
    n = pow(n, mod-2, mod)

    for i in reversed(range(max_k+1)):
        res[i] *= n
        res[i] %= mod
        n *= i
        n %= mod
    return res

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

d = X+Y

if d%3 != 0:
    print(0)
else:
    n = d//3
    if X < n or 2*n < X:
        res = 0
    else:
        res = comb(n,X-n, 10**9+7)[X-n]
    print(res)

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    X, Y = map(int, readline().split())
    if X%3==Y%3==1 or X%3==Y%3==2:
        print(0)
        sys.exit()
    a = (2*Y-X)//3
    b = (2*X-Y)//3


    N = a+b
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]

    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)

    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, a, MOD))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

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

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


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

#calculate (a+b)!/a!b!

fac = [1, 1]
for i in range(2, a+b+1):
    fac.append(fac[-1] * i % MOD)

print(fac[a+b] * pow(fac[a] * fac[b], MOD-2, MOD) % MOD)

Submission status: Accepted

Solution code:
def prepare(n, MOD):

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

def solve(x,y):
    MOD=10**9+7
    if (x+y)%3!=0:
        return 0
    L=(x+y)//3
    if x<L or y<L:
        return 0
    i=min(x,y)-L
    if i==0 or i==L:
        return 1
    fn,invs=prepare(L,MOD)
    ret=(fn*invs[i])%MOD
    ret=(ret*invs[L-i])%MOD
    return ret

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

Submission status: Accepted

Solution code:
class Combination():
    def __init__(self, n, mod=10**9+7):
        self.mod = mod
        self.fac = [1]*(n+1)
        for i in range(1,n+1):
            self.fac[i] = self.fac[i-1] * i % self.mod
        self.invfac = [1]*(n+1)
        self.invfac[n] = pow(self.fac[n], self.mod - 2, self.mod)
        for i in range(n-1, 0, -1):
            self.invfac[i] = self.invfac[i+1] * (i+1) % self.mod

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

    def permutation(self, n, r):
        return self.factorial(n) * self.invfactorial(n-r) % self.mod

    def factorial(self, i):
        return self.fac[i]

    def invfactorial(self, i):
        return self.invfac[i]

def main():
    import sys

    def input(): return sys.stdin.readline().rstrip()

    x, y= map(int, input().split())
    if 2*x-y < 0 or 2*y-x < 0 or (2*x-y)%3 != 0 or (2*y-x)%3 != 0:
        print(0)
        return
    l = (2*x-y)//3
    k = (2*y-x)//3
    c = Combination(l+k)
    print(c.combination(l+k, l))

    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def mycmb(n,r,p):
    r = min(r,n-r)
    if r == 0:
        return 1
    over = reduce(lambda x,y:x*y%p,range(n,n-r,-1))
    under = reduce(lambda x,y:x*y%p,range(1,r+1))
    return (over * pow(under,p-2,p))%p

x, y = MAP()
a = 2*x - y
b = 2*y - x

if a >= 0 and b >= 0 and a % 3 == 0 and b % 3 == 0:
    a //= 3
    b //= 3
    ans = mycmb(a+b, a, 10**9+7)
else:
    ans = 0

print(ans)

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

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()
a = 2*x - y
b = 2*y - x

if a >= 0 and b >= 0 and a % 3 == 0 and b % 3 == 0:
    a //= 3
    b //= 3
    ans = cmb(a+b, a, 10**9+7)
else:
    ans = 0

print(ans)

Submission status: Accepted

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

a = (2*x-y)/3
b = (2*y-x)/3
if not (a.is_integer() and  b.is_integer()) or 2*x<y or 2*y<x:
    print(0)
    sys.exit()
    
a = int(a)
b = int(b)

from functools import reduce
def mycmb(n,r,p):
    r = min(r,n-r)
    if r == 0:
        return 1
    over = reduce(lambda x,y:x*y%p,range(n,n-r,-1))
    under = reduce(lambda x,y:x*y%p,range(1,r+1))
    return (over * pow(under,p-2,p))%p

mod = 10**9+7
print(mycmb(a+b,a,mod))

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
import sys
sys.setrecursionlimit(10**6)



a = (2*x-y)/3
b = (2*y-x)/3
if not (a.is_integer() and  b.is_integer()) or 2*x<y or 2*y<x:
    print(0)
    sys.exit()
    
a = int(a)
b = int(b)

from functools import reduce
def mycmb(n,r,p):
    r = min(r,n-r)
    if r == 0:
        return 1
    over = reduce(lambda x,y:x*y%p,range(n,n-r,-1))
    under = reduce(lambda x,y:x*y%p,range(1,r+1))
    return (over * pow(under,p-2,p))%p

mod = 10**9+7
print(mycmb(a+b,a,mod))

Submission status: Accepted

Solution code:
from functools import reduce

def combination2(n, r, MOD=10**9+7):
    if not 0 <= r <= n: return 0
    r = min(r, n - r)
    numerator = reduce(lambda x, y: x * y % MOD, range(n, n - r, -1), 1)
    denominator = reduce(lambda x, y: x * y % MOD, range(1, r + 1), 1)
    return numerator * pow(denominator, MOD - 2, MOD) % MOD

X, Y = map(int, input().split())
if (2*X-Y)%3 or (2*Y-X)%3:
    print(0)
    exit()
x, y = (2*X-Y)//3, (2*Y-X)//3
print(combination2(x+y,x))

Submission status: Accepted

Solution code:
# 20-7-30 再トライ
import sys

def binomial_p(n, k, p):
    k = min(k, n - k)
    if k == 0: return 1
    numer = 1
    denom = 1
    for i in range(k):
        numer = numer * (n - i) % p
        denom = denom * (k - i) % p
    return numer * pow(denom, p - 2, p) % p


X, Y = [int(x) for x in input().split()]
p = 10 ** 9 + 7

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

m = (2 * X - Y) // 3
n = (2 * Y - X) // 3
print(binomial_p(m + n, m, p))

Submission status: Accepted

Solution code:
import sys
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
X,Y=map(int,input().split())
if (X+Y)%3!=0:
  print(0)
  sys.exit()
c=(X+Y)//3
if c>X or c>Y:
  print(0)
  sys.exit()
b=X-c
a=Y-c
mod = 10**9+7
N =a+b
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1] 

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

Submission status: Accepted

Solution code:
from math import factorial as fac
x,y=map(int,input().split())
a=(2*y-x)/3
b=(2*x-y)/3
mod=10**9+7
if a>=0 and b>=0 and a==int(a) and b==int(b):
  a=int(a)
  b=int(b)
  a1=1
  a2=1  
  n3=10**9+7
  for i in range(a):
    a1*=a+b-i
    a2*=i+1
    a1%=n3
    a2%=n3
  a2=pow(a2,n3-2,n3)
  print((a1*a2)%n3)
else:
  print(0)

Submission status: Accepted

Solution code:
from math import factorial as fac
x,y=map(int,input().split())
a=2*y-x
b=2*x-y
mod=10**9+7
if a>=0 and b>=0 and a%3==0 and b%3==0:
  a=a//3
  b=b//3
  a1=1
  a2=1  
  n3=10**9+7
  for i in range(a):
    a1*=a+b-i
    a2*=i+1
    a1%=n3
    a2%=n3
  a2=pow(a2,n3-2,n3)
  print((a1*a2)%n3)
else:
  print(0)

Submission status: Accepted

Solution code:
import sys

X, Y = map(int, input().split())
mod = int(1e9) + 7
N = 10**6
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]


# 組み合わせ(1e9+7で割る場合)
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


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に符合すれば組み合わせ計算、それ以外であれば没
kake = 0
ans = 0
while X >= 0:
    temp = X
    if temp*2 + kake*1 == Y:
        ans += cmb(temp + kake, kake, mod)
    kake += 1
    X -= 2
print(ans)

Submission status: Accepted

Solution code:
import sys

X, Y = map(int, input().split())
mod = int(1e9) + 7
N = 10**6
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]


# 組み合わせ(1e9+7で割る場合)
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


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

n = (-X + 2*Y) // 3
m = (2 * X - Y) // 3
if n < 0 or m < 0:
    print(0)
    sys.exit()

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

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
import bisect
mod = 10**9+7
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
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 __name__ == "__main__":
    x,y = map(int,input().split())
    if (x+y)%3 != 0:
        print(0)
        sys.exit()
    n = (2*y-x)//3
    m = (2*x-y)//3
    ans = cmb(int(n+m),int(n),mod)
    print(ans)

Submission status: Accepted

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

def modpow(a,n):
    if n<1:
        return 1
    ans=modpow(a,n//2)
    ans=(ans*ans)%mod
    if n%2==1:
        ans*=a
    return ans%mod
    
def conb(n,i):
    inv,ans=1,1
    for j in range(1,i+1):
        ans=ans*(n-j+1)%mod
        inv=inv*j%mod
    return (ans*modpow(inv,mod-2))%mod


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

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
if (2*y-x)%3==0 and(2*x-y)%3==0 and (2*y-x)>=0 and (2*x-y)>=0:
  
      a=(2*y-x)//3
      b=(2*x-y)//3
      numerator=1
      denominator=1
      for i in range(a):
          numerator=(numerator*(a+b-i))%(10**9+7)
          denominator=(denominator*(a-i))%(10**9+7)
      print((numerator*pow(denominator,10**9+5,10**9+7))%(10**9+7))

else:
    print(0)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc145/tasks/abc145_d
import math
X, Y = list(map(int, input().split()))

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


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

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


def comb(n, k):
    c = 1
    for i in range(k):
        c *= n - i
        c %= MOD
    d = 1
    for i in range(1, k + 1):
        d *= i
        d %= MOD
    return (c * pow(d, MOD - 2, MOD)) % MOD

MOD = 10 ** 9 + 7
result = comb(n+m, n)
print(result)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

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 not (X+Y) % 3:
    m = (2*X - Y)//3
    n = (2*Y - X)//3
    if n >= 0 and m >= 0:
        print(comb(n+m,n))
    else:
        print(0)
else:
    print(0)

Submission status: Accepted

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

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

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

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

if (X+Y)%3!=0:
    print(0)
else:
    if X>(Y*2):
        print(0)
    else:
        N=(X+Y)//3
        H=(N-(X-Y))//2
        print(cmb(N,H,10**9+7))
        #print(N,H)