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:
x,y = map(int, input().split())

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

if 2*y<x or y>2*x:
    print(0)
    exit()

dan = (x+y)//3+1
num=y-dan+1

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

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

ans = comb(dan-1,num)
print(int(ans))

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
ans = 0

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

if (x + y) % 3 == 0:
    k = (2 * x - y) // 3
    l = (2 * y - x) // 3
    if k >= 0 and l >= 0:
        fac = [1] * (k + l + 1)
        for i in range(2, k + l + 1):
            fac[i] = fac[i - 1] * i % mod
        ans = fac[k + l] * (pow(fac[k], mod - 2, mod) * pow(fac[l], mod - 2, mod) % mod) % mod

print(ans)

Submission status: Accepted

Solution code:
fac = [0] * 700000
finv = [0] * 700000
inv = [0] * 700000
mod = 1000000007

fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, 700000):
    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:
    k = (2 * x - y) // 3
    l = (2 * y - x) // 3
    if k >= 0 and l >= 0:
        print(fac[k + l] * (finv[k] * finv[l] % mod) % mod)
    else:
        print(0)
else:
    print(0)

Submission status: Accepted

Solution code:
def comb(n, r):
    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
MAXN=2000000+10
g1=[1, 1]
g2=[1, 1]
inverse=[0, 1]

for i in range(2, MAXN+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())
ans=0
if (X+Y)%3==0:
    a=(2*X-Y)//3
    b=(2*Y-X)//3
    ans=comb(a+b, a)
print(ans)

Submission status: Accepted

Solution code:
def main():
    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 or (2*X-Y)%3!=0:
        print(0)
    else:
        s=(2*Y-X)//3
        t=(2*X-Y)//3
        if s<0 or t<0:
            print(0)
        else:
            print(cmb(s+t,t,mod))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
X,Y = [int(i) for i in input().split()]
M = max(X,Y)
m = min(X,Y)
X = M
Y = m
p = 10 ** 9 + 7
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
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] % p
if (X+Y) % 3 != 0:
    print(0)
    exit()
else :
    N = (X+Y)//3
    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)
    d = X - N
    print(cmb(N,d,p))
    exit()

Submission status: Accepted

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


def Knight(X, Y):
    
    if (X+Y)%3 != 0:
        return 0
    
    else:    
        if X > Y:
            q = X // 2
            r = X % 2
            if Y < q*1 + r*2:
                return 0
        elif Y > X:
            q = Y // 2
            r = Y % 2
            if X < q*1 + r*2:
                return 0

    # 移動回数
    move = (X+Y) // 3
    if X >= Y:
        diff  = X - Y
        i2j1_move = move//2 + move%2 + diff//2
        i1j2_move = move//2 - diff//2
    else:
        diff  = Y - X
        i2j1_move = move//2 - diff//2
        i1j2_move = move//2 + move%2 + diff//2

    # 二項係数
    MOD = 10**9+7    
    fac = [1, 1]
    finv = [1, 1]
    inv = [0, 1]
    for i in range(2, move+1):
        fac.append((fac[-1] * i) % MOD)  
        inv.append((-inv[MOD % i] * (MOD//i)) % MOD)
        finv.append((finv[-1] * inv[-1]) % MOD)

    def COM(n, k):
        return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

    return COM(move, i2j1_move)


print(Knight(X, Y))

Submission status: Accepted

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

if (x + y) % 3 != 0:
    print(0)
else:
    s = (x + y) // 3
    k = (2 * x - y) // 3
    l = (-x + 2 * y) // 3
    if k < 0 or l < 0:
        print(0)
    else:
        a = 1
        b = 1
        for i in range(k + 1,k + l + 1):
            a *= i
            a %= m
        for j in range(1,l + 1):
            b *= j
            b %= m
        ans = a * pow(b,m-2,m)
        print(ans % m)

Submission status: Accepted

Solution code:
#17:23
x,y = map(int,input().split())
if (x+y) % 3 != 0:
  print(0)
elif x*2 < y or y*2 < x:
  print(0)
else:
  a = (x + y) // 3
  b = y - a
  mod = 10 ** 9 + 7
  def inv(x):
    y = 1
    while x != 1:
      y *= mod // x + 1
      y %= mod
      x -= mod % x
    return y
  ans = 1
  for i in range(b):
    ans *= a - i
    ans %= mod
    ans *= inv(b-i)
    ans %= mod
  print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e15)


def main():
    # sys.stdin = open("sample.txt")
    X, Y = Scanner.map_int()
    if (X + Y) % 3 != 0:
        print(0)
        return
    n = (X + Y) // 3
    X -= n
    Y -= n
    MAX = 670000
    fac = [0 for _ in range(MAX)]
    finv = [0 for _ in range(MAX)]
    inv = [0 for _ in range(MAX)]
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i-1] * inv[i] % MOD

    N = X + Y
    if N < X:
        print(0)
        return
    if N < 0 or X < 0:
        print(0)
        return
    ans = fac[N] * (finv[X] * finv[Y] % MOD) % MOD
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

mod = 10**9 + 7
n = (x+y) // 3
a = min(
    (2 * x - y) // 3, (2 * y - x) // 3
)


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


N = max(x, y)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

ans = cmb(n, a, mod)
print(ans)

Submission status: Accepted

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

if (x+y)%3 == 0:
    m = (2*y-x)//3
    n = (2*x-y)//3
    if m >= 0 and n >= 0:
        fac = [1]*(m+n+1)
        for i in range(2,m+n+1): 
            fac[i] = fac[i-1]*i % mod
        ans = fac[m+n]*(pow(fac[m],mod-2,mod)*pow(fac[n],mod-2,mod)%mod)%mod

print(ans)

Submission status: Accepted

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

MOD = 10**9+7
def pow(a, b):
    res = 1
    while b:
        if b & 1: res = res * a % MOD
        a = a**2 % MOD
        b >>= 1
    return res


def main():    
    X, Y = map(int, input().split())
    
    if (X+Y) % 3: print(0); sys.exit()
    
    n = (X+Y) // 3
    
    X -= n
    Y -= n
    
    if X < 0 or Y < 0: print(0); sys.exit()
    
    fac = [1] * (X+Y+1)
    for i in range(2, X+Y+1): fac[i] = fac[i-1] * i % MOD
    
    ans = (fac[X+Y] * pow(fac[X], MOD-2)) % MOD * pow(fac[Y], MOD-2)
    print(ans%MOD)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    vn = vk = vn_k = 1
    for i in range(1, n+1):
        vn = vn * i % modp
        if i == k:
            vk = vn
        if i == n-k:
            vn_k = vn
    return vn * get_inv(vk, modp) * get_inv(vn_k, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

def main():
    X,Y=mis()
    if (X+Y)%3 != 0:
        print(0)
    else:
        x, y = X - (X+Y)//3, Y - (X+Y)//3
        if x >= 0 <= y:
            print(comb(x+y, x, N1097))
        else:
            print(0)


main()

Submission status: Accepted

Solution code:
def main():
    mod = 10 ** 9 + 7
    X, Y = map(int, input().split(" "))
    if (2 * X - Y) % 3 == 0 and (2 * Y - X) % 3 == 0:
        s = (2 * X - Y) // 3
        t = (2 * Y - X) // 3
        if s < 0 or t < 0:
            print(0)
        else:
            numerator = 1
            denominator = 1
            for i in range(s + 1, s + t + 1):
                numerator = (numerator * i) % mod
            for i in range(1, t + 1):
                denominator = (denominator * i) % mod
            print(numerator * pow(denominator, mod - 2, mod) % mod)
            # math.factorialはTLEになりそう?
    else:
        print(0)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    mod = 10 ** 9 + 7
    X, Y = map(int, input().split(" "))
    if (2 * X - Y) % 3 == 0 and (2 * Y - X) % 3 == 0:
        s = (2 * X - Y) // 3
        t = (2 * Y - X) // 3
        if s < 0 or t < 0:
            print(0)
        else:
            s = s + t
            numerator = 1
            denominator = 1
            for i in range(s - t + 1, s + 1):
                numerator = (numerator * i) % mod
            for i in range(1, t + 1):
                denominator = (denominator * i) % mod
            print(numerator * pow(denominator, mod - 2, mod) % mod)
            # math.factorialはTLEになりそう?
    else:
        print(0)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	X,Y = MI()
	N3 = (2*Y-X)
	M3 = (2*X-Y)
	if(N3%3!=0 or M3%3!=0 or N3 < 0 or M3<0):
		print(0)
	else:
		N=N3//3
		M=M3//3

		K = min(N,M)

		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 #出力の制限
		L = 10**6
		g1 = [1, 1] # 元テーブル
		g2 = [1, 1] #逆元テーブル
		inverse = [0, 1] #逆元テーブル計算用テーブル

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

		print(cmb(N+M,K,mod))


main()

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

p = 10 ** 9 + 7
M = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, M + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

a, b = map(int, input().split())
N = (a+b)//3
A = (N -abs(a-b))//2
B = (N +abs(a-b))//2
if (a+b)%3!=0 or A<0 :
    print(0)
else :
    print(cmb(N, A, p))

Submission status: Accepted

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

mod = 10**9+7
N = 1333334
fac = [1]*(N+1)
rev = [1]*(N+1)
 
for i in range(1,N+1):
  fac[i] = i*fac[i-1]%mod
  rev[i] = pow(fac[i], mod-2, mod)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%mod

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

Submission status: Accepted

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

def cmb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

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

Submission status: Accepted

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

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

# 移動回数
if (X + Y) % 3 != 0:
    print(0)
    exit()

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

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


# 階乗、Combinationコンビネーション(numpyを使う)

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


# def mod_comb_k(n, k, mod):
    # return fact[n] * fact_inv[k] % mod * fact_inv[n-k] % mod

MOD = 10 ** 9 + 7
U = 10**6
fact, fact_inv = make_fact(U, MOD)
ans = fact[nm] * fact_inv[n] % MOD * fact_inv[nm-n] % MOD
print(ans)

Submission status: Accepted

Solution code:
def nCr(n, r):
  return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

x, y = map(int, input().split())
mod = 10 ** 9 +7
f = [1]
 
for i in range(10**6):
  f.append(f[-1] * (i+1) % mod)
  
if (x+y) % 3 != 0 or (x+y) // 3 < abs(x-y):
  print(0)
  exit()
  
n = (x+y)//3
r = n // 2 - abs(x-y) // 2
print(nCr(n, r))

Submission status: Accepted

Solution code:
import sys

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

def cmb(n, k, mod, fac, ifac):
    # nCkを計算する
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod

def make_tables(mod, n):
    # 階乗テーブル、逆元の階乗テーブルを作成する
    fac = [1, 1] # 階乗テーブル
    ifac = [1, 1] # 逆元の階乗テーブル
    inverse = [0, 1] # 逆元テーブル 0の階乗は1 0の逆元は0

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac

X, Y = lr()
MOD = 10 ** 9 + 7
if (X+Y)%3 != 0 or X > 2 * Y or Y > 2 * X:
    print(0)
    exit()
if X < Y:
    X, Y = Y, X
# Xが大きい
total_time = (X+Y)//3
x_time = (X - Y + total_time) // 2
# total_time C i_time
fac, ifac = make_tables(MOD, total_time)
answer = fac[total_time] * ifac[x_time] * ifac[total_time - x_time] % MOD
print(answer)
# 44

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
def inv(x, mod=1):
    return pow(x, mod-2, mod)

def fact(x, mod=1):
    res = 1 
    for i in range(1, x + 1): 
        res *= i
        res %= mod    
    return res

def comb(n, k, mod=1):
    return (fact(n, mod) * inv(fact(n-k, mod), mod) * inv(fact(k, mod), mod)) % mod

div = 10 ** 9 + 7
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()

ans = comb(X+Y, X, div)
print(ans)

Submission status: Accepted

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

mod = 10**9+7
def inv(x):
        return pow(x, mod-2, mod)
def fact(x):
        f = 1 
        for i in range(1, x + 1): 
                f *= i
                f %= mod    
        return f
def comb(n, r): 
        return (fact(n) * inv(fact(n-r)) * inv(fact(r))) % mod 

if (x + y) % 3 != 0 or y / x < 1/2 or y/x > 2:
    print(0)
else:
    n = (2*y-x)//3
    m = (2*x-y)//3
    res = comb(n+m, m)
    print(res)

Submission status: Accepted

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

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 [m+2*n,2*m+n] != [X,Y]:
    print(0)
else:
    print(cmb(m+n,n,10**9+7))

Submission status: Accepted

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

    a = (2*Y-X)//3
    b = Y-2*a
    s = (X+Y)//3
    if (2*Y-X)%3 == 0 and 0 <= a and 0 <= b:
        ans = 1
        for n in range(s-min(a,b)+1,s+1):
            ans = (ans*n)%mod
        div = 1
        for n in range(2,min(a,b)+1):
            div = (div*n)%mod

        ans = (ans*pow(div,1000000005,mod))%mod
        print(ans)
    else:
        print(0)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def nCm_mod(A, B, mod):
    mul_one = 1
    mul_two = 1

    for i in range(B):
        mul_one *= A - i
        mul_two *= i + 1
        mul_one %= mod
        mul_two %= mod
    
    return (mul_one * pow(mul_two, mod-2, mod)) % mod

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

if (x + y) % 3 != 0 or n < 0 or m < 0:
    print(0)
else:
    comb_num = nCm_mod(n+m, min(n,m), mod)
    print(comb_num)

Submission status: Accepted

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

tmp = max(X, Y)
Y = min(X, Y)
X = tmp
diff = X - Y

X -= 2 * diff
Y -= diff

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

c = X // 3

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

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

ans = g1[2*c + diff] * g2[c + diff] * g2[c] % mod

print(ans)
# print(c, diff)

Submission status: Accepted

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



MOD = 10 ** 9 + 7

def inv_fact(a,mod = MOD): #あるmod下における a ! の逆元を求める関数
    ans = 1
    for i in range(1,a + 1):
        ans *= pow(i, MOD - 2 ,MOD)
        ans %= MOD
    return ans



if (2 * X - Y ) % 3 == 0 and (2 * Y - X ) % 3 == 0 and  (2 * X - Y )  >= 0 and (2 * Y - X ) >= 0:  # 到達可能であれば
    a = (2 * Y - X ) //3
    b = (2 * X - Y) // 3
    a_inv = inv_fact(a)
    b_inv = inv_fact(b)
    ans = 1
    for i in range(1, a + b + 1):
        ans *= i
        ans %= MOD
    mul = (a_inv * b_inv )% MOD
    ans *= (mul)
    ans %= MOD
    print(ans)

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

a =  (  2 * x -  y )
b =  ( - x + 2 * y )

if a % 3 != 0 or b % 3 != 0:
    print(0)
    exit(0)

a = int(a/3)
b = int(b/3)

# print(a, b)

mod = 10**9 + 7 

ans = cmb((a+b),a,mod)

print(ans)

Submission status: Accepted

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

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

mod = 10**9+7
n = (x+y)//3
g1 = [1, 1]
g2 = [1, 1]
inv = [0, 1]
for i in range(2, 666667):
    g1.append((g1[-1] * i) % mod)
    inv.append((-inv[mod%i] * (mod//i)) % mod)
    g2.append((g2[-1] * inv[-1]) % mod)


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

res = nChoosem(a+b,a)
print(res)

Submission status: Accepted

Solution code:
import sys

x, y = map(int, input().split())
s, l = min(x,y), max(x,y)

if 2*s-l<0 or (2*s-l)%3!=0:
    print(0)
    sys.exit()

r = (2*s-l)//3
n = (s+l)//3
mod = 10**9+7
g1 = [1, 1]
g2 = [1, 1]
inv = [0, 1]
for i in range(2, n+1):
    g1.append((g1[-1] * i) % mod)
    inv.append((-inv[mod%i] * (mod//i)) % mod)
    g2.append((g2[-1] * inv[-1]) % mod)

def comb(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(comb(n, r))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
x,y=[int(x) for x in input().split()]
mod=10**9+7

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

if (2*x-y)<0 or (2*y-x)<0 or (2*x-y)%3 !=0 or (2*y-x)%3!=0:
    print(0)
else:
    # p+2q=x
    # 2p+q=y
    p=(2*y-x)//3
    q=(2*x-y)//3
    ans=1
    for i in range(q):
        ans*=(p+q-i)%mod
        ans%=mod
        ans*=inv(i+1,mod-2,mod)
        ans%=mod
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding utf-8 -*-

MOD = 10 ** 9 + 7
MAX = 10 ** 6

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

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

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
for i in range( 2, MAX + 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:
    n = (2 * Y - X)//3
    m = (2*X - Y)//3
    ans = comb(n + m, n)
else:
    ans = 0
print(ans)

Submission status: Accepted

Solution code:
import math
x,y = list(map(int, input().split()))
mod = 7 + (10**9)
ans = 0
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
#a/b = a*(b`)となるb`を求める
def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod
if (2 * x - y) % 3 != 0 or (2 * y - x) % 3 != 0:
    print(0)
    exit()
else:
    m = (2*x - y)//3
    n = (2*y - x)//3
    if n < 0 or m < 0:
        print(0)
        exit()
    #m+n C m を計算
    #(m+n)! / n! * m!を計算したいが、mod上で割り算できない。
    #逆元を使う
    factorial = [1]*(m+n+1)
    for i in range(1,m+n+1):
        factorial[i] = (factorial[i - 1] * i) % mod
    ans = factorial[m+n] * mod_inv(factorial[m], mod)
    ans %= mod
    ans *= mod_inv(factorial[n], mod)
    ans %= mod
    print(ans)

Submission status: Accepted

Solution code:
MOD = int(1e9+7)

def fast_power(b, e):
    res = 1
    while e > 0:
        if e % 2 == 1:
            res = res * b % MOD
        b = b * b % MOD
        e >>= 1
    return res

def mod_inverse(n):
    return fast_power(n, MOD-2)
def mul(x, y):
    return ((x % MOD) * (y % MOD) % MOD + MOD) % MOD
def multiply(x, y, z):
    return mul(mul(x, y), z)

def nCr(n, r):
    if r == 0:
        return 1
    fac = [1] * (n+1)
    for i in range(1, n+1):
        fac[i] = fac[i-1] * i % MOD
    # n! / (r! * (n-r)!)
    return multiply(fac[n], mod_inverse(fac[r]), mod_inverse(fac[n-r]))

x, y = map(int, input().split())
n = (2*x-y) // 3
m = (2*y-x) // 3
if min(n, m) < 0 or (x+y)%3 != 0:
    print(0)
    exit()
print(nCr(m+n, n))

Submission status: Accepted

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

def modpow(a, r, mod):
  k = 1
  for i in bin(r)[2:]:
    k = k ** 2 * a ** int(i)
    k %= mod
  return k

def fac(x, mod):
  k = 1
  for i in range(x):
    k *= i + 1
    k %= mod
  return k

def invfac(x, mod):
  k = modpow(fac(x, mod), mod-2, mod)
  return k  
  
def combi(n, r, mod):
  k = invfac(r, mod) * invfac(n-r, mod) * fac(n, mod)
  k %= mod
  return k
  
  
p = (2 * X - Y) // 3
q = (2 * Y - X) // 3
if (X + Y) % 3 != 0 or p < 0 or q < 0:
  print(0)
else:
  print(combi(p+q, p, Mod))

Submission status: Accepted

Solution code:
X,Y = [int(zz) for zz in input().split()]

mod = 10**9+7
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

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

if a != int(a):
    print(0)
    exit()

a = int(a)
b = int(b)
N = a+b

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

ans = cmb(N,a,mod)%(10**9+7)
print(int(ans))

Submission status: Accepted

Solution code:
def sq(a, b, mod):  # aのb乗を剰余,kは初期値#20191116-D-Knight
    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 nCk(n, k, mod=10 ** 9 + 7):
    x = max(k, n - k)
    y = min(k, n - k)
    kkai = 1
    for i in range(2, y + 1):
        kkai = (kkai * i) % mod
    nkkai = 1
    for i in range(x + 1, n + 1):
        nkkai = (nkkai * i) % mod
    answer = sq(kkai, mod - 2, mod) * nkkai % mod
    return answer


X, Y = map(int, input().split())
if (X + Y) % 3 != 0:
    print(0)
else:
    n = (2 * Y - X) // 3
    m = (2 * X - Y) // 3
    if n < 0 or m < 0:
        print(0)
    else:
        print(nCk(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())
ans = 0
if ((x+y)%3 == 0):
    X = (2*x - y)//3
    Y = (2*y - x)//3
    ans = cmb(X+Y,X,mod)
print(ans)

Submission status: Accepted

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

if (x + y) % 3 != 0:
    print(0)
else:
    time = (x + y) // 3
    if time > x or time > y:
        print(0)
    else:
        move_time = sorted([x - time, y - time])
        
        if move_time[0] == 0:
            print(1)
        else:
            ans = 1
            for i in range(2, time+1):
                ans *= i
                ans %= mod
            
            const = 1
            for i in range(1, move_time[1]+1):
                const *= i
                const %= mod
                
                if i == move_time[0]:
                    inv0 = pow(const, mod-2, mod)
                
            inv1 = pow(const, mod-2, mod)
        
            print((ans * inv0 * inv1) % mod)