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


mod = 10**9+7
division = (x+y)//3

#combを求める前処理（階乗とその逆数）

g1 = [1, 1] #元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
for i in range( 2, division + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#################################

r = min(x,y)-division
ans = cmb(division,r,mod)

print(ans)

Submission status: Accepted

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

mod = 10**9+7

division = (x+y)//3

if [x%3,y%3] in [[1,1],[2,2]]:
    print(0)
    exit()

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 )



r = min(x,y)-division
ans = cmb(division,r,mod)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
D - Knight
https://atcoder.jp/contests/abc145/tasks/abc145_d

"""
import sys


def modinv(a, m):
    b, u, v = m, 1, 0
    while b:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= m
    return u if u >= 0 else u + m


def solve(X, Y):
    MOD = 10**9 + 7
    if (X + Y) % 3:
        return 0
    n = (X - 2 * Y) / -3.0
    m = (Y - 2 * X) / -3.0
    if not n.is_integer() or not m.is_integer() or n < 0 or m < 0:
        return 0
    n, m = int(n), int(m)
    x1 = 1
    for i in range(2, n + m + 1):
        x1 = (x1 * i) % MOD
    x2 = 1
    for i in range(2, n+1):
        x2 = (x2 * i) % MOD
    for i in range(2, m+1):
        x2 = (x2 * i) % MOD
    ans = (x1 * modinv(x2, MOD)) % MOD
    return ans


def main(args):
    X, Y = map(int, input().split())
    ans = solve(X, Y)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

if x < y:
    x, y = y, x

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

a = x - 2 * b
if a < 0:
    print(0)
    exit()

MOD = 10 ** 9 + 7
a %= MOD
b %= MOD

MAX = 10 ** 6 * 2 + 2
fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]

def comInit(mod):
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 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

def com(n, r, mod):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod
    
comInit(MOD)
print(com(a + b, b, MOD))

Submission status: Accepted

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

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

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


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


print(cmb(n+m, n))

Submission status: Accepted

Solution code:
import math

I=list(map(int,input().split()))
X=(2*I[1]-I[0])//3
Y=(2*I[0]-I[1])//3
n=X+Y
r=X

if (X<0 or Y<0 or (I[0]+I[1])%3!=0):
    print(0)
    exit()

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)

print(cmb(n, r, p))

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 = list(map(int,input().split()))
if (X+Y)%3 != 0:
    print(0)
    exit()
N = (X+Y)//3
K = min(2*N-X,X-N)
print(cmb(N,K,mod))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    x,y=map(int, input().split())
    if (2*y-x)%3!=0 or (2*x-y)%3!=0:
        print(0)
    else:
        a=(2*y-x)//3
        b=(2*x-y)//3
        c=a+b

        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 = c
        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(c, min(a,b), p))
resolve()

Submission status: Accepted

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

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

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

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

mod = 10**9+7

def prepare(n, mod):
    facts = [1]*(n+1)
    for i in range(1, n+1):
        facts[i] = facts[i-1]*i%mod
    invs = [1]*(n+1)
    invs[n] = pow(facts[n], mod-2, mod)
    for i in range(0, n)[::-1]:
        invs[i] = invs[i+1] * (i+1) % mod
    return facts, invs
facts,invs = prepare(a+b,mod)
def make_combi(facts,invs,n,r,mod):
    return facts[n]*invs[r]*invs[n-r]%mod
print(make_combi(facts,invs,a+b,a,mod))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


class CmbMod:
    def __init__(self, n, p):
        """
        二項係数nCr(n個の区別できるものからr個のものを選ぶ組み合わせの数)をpで割った余りを求める
        """
        self.n = n
        self.p = p
        self.fact = [1, 1]
        self.factinv = [1, 1]
        self.inv = [0, 1]

    def cmb_mod(self, n, r):
        """
        二項係数nCr(mod p)をO(r)にて計算。nが大きいがrは小さい時に使用。
        """
        numer, denom = 1, 1
        for i in range(r):
            numer = (numer * (n - i)) % self.p
            denom = (denom * (i + 1)) % self.p
        return (numer * pow(denom, self.p - 2, self.p)) % self.p

    def prep(self):
        """
        二項係数nCr(mod p)をO(1)で求める為の前処理をO(N)にて実行。
        """
        for i in range(2, self.n + 1):
            self.fact.append((self.fact[-1] * i) % self.p)
            self.inv.append((-self.inv[self.p % i] * (self.p // i)) % self.p)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % self.p)

    def cmb_mod_with_prep(self, n, r):
        """
        二項係数nCr(mod p)をO(1)で求める。事前にprepを実行する事。
        """
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return self.fact[n] * self.factinv[r] * self.factinv[n - r] % self.p


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

    cnt = (X + Y) // 3
    left = 0
    right = 0
    for i in range(cnt):
        if (i * 1 + (cnt - i) * 2 == X and i * 2 + (cnt - i) * 1 == Y) or (
                i * 1 + (cnt - i) * 2 == Y and i * 2 + (cnt - i) * 1 == X):
            left = i
            right = cnt - i
            break
    else:
        print(0)
        exit()

    cmb = CmbMod(cnt, mod)
    res = cmb.cmb_mod(cnt, min(left, right))
    print(res)


if __name__ == '__main__':
    resolve()

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

M = (X+Y)//3 #M回動く必要がある。
D = abs(X-Y) #D回差がある。
A = (M-D)//2
#print(M,D,A)
ans = cmb(M,A,MOD)
print(ans)

Submission status: Accepted

Solution code:
import sys
x,y=map(int,input().split())
MOD=10**9+7
if (2*y-x)%3!=0 or 2*y-x<0 or 2*x-y<0:
  print(0)
  sys.exit()
a=(2*x-y)//3
if (a+1)*3<=(2*x-y):
  a+=1
a=(2*x-y)//3
if (a+1)*3<=(2*x-y):
  a+=1
b=(2*y-x)//3
if (b+1)*3<=(2*y-x):
  b+=1
p=1
for i in range(1,a+b+1):
  p=(p*i)%MOD
q=1
for i in range(1,a+1):
  q=(q*i)%MOD
q=pow(q,MOD-2,MOD)
r=1
for i in range(1,b+1):
  r=(r*i)%MOD
r=pow(r,MOD-2,MOD)
print((p*q*r)%MOD)

Submission status: Accepted

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

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 )

step1_cnt = 0
step2_cnt = 0
if Y == X:
    if Y % 3 == 0:
        step1_cnt = step2_cnt = Y//3
        print(cmb(step1_cnt+step2_cnt,step1_cnt,mod))
    else:
        print(0)
if Y > X:
    step1_cnt = Y-X
    Y = Y - step1_cnt*2
    X = X - step1_cnt
    if Y % 3 == 0:
        step1_cnt += Y//3
        step2_cnt += Y//3
        print(cmb(step1_cnt+step2_cnt,step1_cnt,mod))
    else:
        print(0)

if X > Y:
    step2_cnt = X - Y
    Y = Y - step2_cnt
    X = X - step2_cnt*2
    if Y % 3 == 0:
        step1_cnt += Y//3
        step2_cnt += Y//3
        print(cmb(step1_cnt+step2_cnt,step1_cnt,mod))
    else:
        print(0)

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
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,input().split())
if ((x+y)%3!=0):
  print(0)
else:
  xx=(2*x-y)//3
  yy=(2*y-x)//3
  if (xx<0 or yy<0):
    print(0)
  else:
    ans=cmb(xx+yy,xx,p)
    print(ans)

Submission status: Accepted

Solution code:
def nCr(n,r):
  dividend,divisor = 1,1
  for i in range(r):
    dividend *= n-i
    divisor *= 1+i
    dividend %= MOD
    divisor %= MOD

  return (dividend * pow(divisor, MOD-2, MOD)) % MOD

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

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

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

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

print(nCr(n+m, n))

Submission status: Accepted

Solution code:
def comb(n, m, p=10**9+7):
    if n < m:
        return 0
    if n < 0 or m < 0:
        return 0
    m = min(m, n-m)
    top = bot = 1
    for i in range(m):
        top = top*(n-i) % p
        bot = bot*(i+1) % p
    bot = pow(bot, p-2, p)
    return top*bot % p


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

j = 2*x-y
if j % 3:
    print(0)
    exit()
j //= 3
i = x - 2*j
if i < 0 or j < 0:
    print(0)
    exit()

ans = comb(i+j, i)
print(ans)

Submission status: Accepted

Solution code:
# (+1,+2)をn回，(+2,+1)をm回とすると
#  n + 2m = X
# 2n +  m = Y でn,mが求まる．
# このとき答えは(n+m)Cn通り

def combination(n,r):
	"""
    高速な組み合わせの計算．
	nCrは必ず整数になるため分母を全部約分で1にしてから残った分子の積を求める．
	[参考]https://kadzus.hatenadiary.org/entry/20081211/1229023326
    """

	if n-r < r: r = n-r
	if r == 0: return 1
	if r == 1: return int(n)

	numerator = [i+1 for i in range(n-r, n)]
	denominator = [i+1 for i in range(r)]

	for p in range(2,r+1):
		pivot = denominator[p-1]
		if pivot > 1:
			offset = (n-r)%p
			for k in range(p-1, r, p):
				numerator[k-offset] /= pivot
				denominator[k] /= pivot
	
	ans = 1
	for i in range(r):
		if numerator[i] > 1:
			ans *= numerator[i]
			if ans >= 1e9+7: ans %= 1e9+7
	
	return int(ans)

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

if (X+Y)%3 != 0:
	ans = 0
else:
	n = int((2*Y-X)/3)
	m = int(Y-2*n)
	if n<0 or m<0:
		ans = 0
	else:
		ans = combination(n+m, n)

print(ans)

Submission status: Accepted

Solution code:
# (+1,+2)をn回，(+2,+1)をm回とすると
#  n + 2m = X
# 2n +  m = Y でn,mが求まる．
# このとき答えは(n+m)Cn通り

def combination(n,r):
	"""
    高速な組み合わせの計算．
	nCrは必ず整数になるため分母を全部約分で1にしてから残った分子の積を求める．
	[参考]https://kadzus.hatenadiary.org/entry/20081211/1229023326
    """

	if n-r < r: r = n-r
	if r == 0: return 1
	if r == 1: return int(n)

	numerator = [i+1 for i in range(n-r, n)]
	denominator = [i+1 for i in range(r)]

	for p in range(2,r+1):
		pivot = denominator[p-1]
		if pivot > 1:
			offset = (n-r)%p
			for k in range(p-1, r, p):
				numerator[k-offset] /= pivot
				denominator[k] /= pivot
	
	ans = 1
	for i in range(r):
		if numerator[i] > 1:
			ans *= numerator[i]
			ans %= 1e9+7
	
	return int(ans)

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

if (X+Y)%3 != 0:
	ans = 0
else:
	n = int((2*Y-X)/3)
	m = int(Y-2*n)
	if n<0 or m<0:
		ans = 0
	else:
		ans = combination(n+m, n)

print(ans)

Submission status: Accepted

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

con = (X + Y) // 3
dif = M - m
n = (con - dif) // 2

if (X + Y) % 3 != 0 or n < 0:
  print(0)
  
else:
  def comb(n, r):
    n += 1
    over = 1
    under = 1
    for i in range(1,r + 1):
      over = over * (n - i) % mod
      under = under * i % mod
    #powでunder ** (mod - 2) % modを実現、逆元を求めている
    return over * pow(under,mod - 2,mod) % mod
  
  ans = comb(con,n)
  
  print(ans)

Submission status: Accepted

Solution code:
import sys
# N = int(input())
X, Y = [int(i) for i in input().split()]
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 )

a_3 = 2 * Y - X
b_3 = 2 * X - Y
if a_3 % 3 != 0 or b_3 % 3 != 0 or a_3 < 0 or b_3 < 0:
    print(0)
    sys.exit(0)
a = a_3//3
b = b_3//3
print(cmb(a+b,a,mod))

Submission status: Accepted

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

if (2*X-Y)%3==0 and (2*Y-X)%3==0:
    a = (2*X-Y)//3
    b = (2*Y-X)//3
    if a>=0 and b>=0:
        MOD = 10**9+7
        n = a+b+1
        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
        print(comb(a+b, a))
    else:
        print(0)
else:
    print(0)

Submission status: Accepted

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

cnt1 = cnt2 = 0
for i in range(x + 1):
    x_left = x - i
    y_left = y - 2 * i
    if x_left == y_left * 2:
        cnt1 = i
        cnt2 = y_left

if cnt1 == cnt2 == 0:
    ans = 0
else:
    ans = 1
    for i in range(1, cnt1 + 1):
        ans *= (cnt1 + cnt2 - i + 1)
        ans %= mod
        ans *= pow(i, mod - 2, mod)
        ans %= mod

print(ans)

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
N = 2 * 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, input().split())
#(1, 2)の回数をn, (2, 1)の回数をmとする。
n = (-X + 2 * Y) / 3
m = (-Y + 2 * X) / 3
#いけない場合を除外
if n % 1 != 0:
  print(0)
  quit()
elif m % 1 != 0:
  print(0)
  quit()
#n + m C nで答え  
ans = cmb(int(n + m), int(n), p)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
X, Y = map(int, input().split())
if (X + Y) % 3:
    exit(print(0))
m = (2*X - Y) // 3
n = X - 2*m
if n < 0 or m < 0:
    exit(print(0))

## class
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 power(a, b, c):
    try:
        return pow(a, b, c)
    except (ValueError, TypeError) as e:
        if b < 0:
            return pow(modinv(a, c), -b, c)
        else:
            print(e)

class Factorial:
    def __init__(self, n, mod):
        self.f = f =[0] * (n + 1)
        f[0] = b = 1
        for i in range(1, n + 1):f[i] = b = b * i % mod
        self.inv = inv = [0] * (n + 1)
        inv[n] = b = power(self.f[n], -1, mod)
        for i in range(n,0,-1):inv[i-1] = b = b * i % mod
        self.mod = mod
    def factorial(self, i):
        return self.f[i]
    def ifactorial(self, i):
        return self.inv[i]
    def comb(self, n, k):
        if n >= k:return self.f[n] * self.inv[n - k] * self.inv[k] % self.mod
        else:return 0

def nCr(n, r, mod = None, limit = None):
    if mod and limit:
        return Factorial(limit, mod).comb(n, r)
    elif mod:
        r = min(r, n - r)
        a = 1
        for i in range(r):
            a = a * (n - i) * power(i + 1, mod - 2, mod) % mod
        return a
    else:
        from math import factorial as f
        return f(n) // (f(n - r) * f(r))

MOD = 10**9+7
print(nCr(m + n, n, MOD, 2*10**6))

Submission status: Accepted

Solution code:
import math

def modpow(a,b,mod=10**9+7):
    res=1
    a%=mod
    leng=int(math.log2(b))
    for i in range(leng,-1,-1):
        res=(res*res)%mod
        if (b>>i)&1:
            res=(res*a)%mod
    return res

def fact(x):
    ans=1
    for i in range(2,x+1):
        ans = (ans*i)%(10**9+7)
    return ans

def comb(n,r):
    return fact(n)*modpow(fact(r),10**9+5)*modpow(fact(n-r),10**9+5)%(10**9+7)

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

Submission status: Accepted

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

def comb(n,k):
    if n<k:
        return 0
    if n-k<k:
        k=n-k
    comb=1
    for x in range(n-k+1,n+1):
        comb=(comb*x)%mod
    d=1
    for x in range(1,k+1):
        d =(d*x)%mod
    comb*=pow(d,mod-2,mod)
    return comb%mod

ans=0
if (x+y)%3==0:
    n=int((x+y)/3)
    r=int((2*x-y)/3)
    if n-r>=0 and r>=0:
        ans=comb(n,r)%mod
print(ans)

Submission status: Accepted

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

move = x+y
if move %3 !=0:
  print(0)
  exit()
move //= 3
  
x,y = x-move, y-move

if x < 0 or y < 0:
  print(0)
  exit()
  
ans = 1
for i in range(min(x,y)):
  ans *= (x+y-i)
  ans *= pow(i+1,mod-2,mod)
  ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import math
import numpy as np

def cmb(n, r, mod):
  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 (x+y) % 3 == 0:

  A = np.array([[1, 2],
                [2, 1]])

  b = np.array([x, y])

  N = np.linalg.solve(A, b)


  if N[0].is_integer() == True and N[1].is_integer() == True and N[0] >=0 and N[1] >=0:
        
      print(cmb(int(N[0]+N[1]),int(N[0]),mod))

  else:
      print(0)

else:
  print(0)

Submission status: Accepted

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

def comb(n,k):
    if n<k:
        return 0
    if n-k<k:
        k=n-k
    comb=1
    for x in range(n-k+1,n+1):
        comb=(comb*x)%mod
    d=1
    for x in range(1,k+1):
        d =(d*x)%mod
    comb*=pow(d,mod-2,mod)
    return comb%mod

ans=0
if (x+y)%3==0:
    n=int((x+y)/3)
    r=int((2*x-y)/3)
    if n-r>=0 and r>=0:
        ans=comb(n,r)%mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

def getComb(n, k, MOD):
    if n < k:
        return 0
    if n-k < k:
        k = n-k
    comb = 1
    for x in range(n-k+1, n+1):
        comb = (comb * x) % MOD
    d = 1
    for x in range(1, k+1):
        d = (d * x) % MOD
    comb *= pow(d, MOD-2, MOD)
    return comb % MOD

ans = 0
if (X+Y)%3 == 0:
    N = (X+Y)//3
    k = (2*Y-X)//3
    if k >= 0:
        ans = getComb(N, k, MOD)

print(ans)

Submission status: Accepted

Solution code:
mod = 10**9 + 7
fact = []
ifact = []
def setFact(n, mod):
    global fact
    global ifact
    fact.append(1)
    for i in range(1, n+1):
        fact.append((fact[-1] * i) % mod)
    ifact = [0] * (n+1)
    ifact[-1] = pow(fact[-1] , mod-2, mod)
    for i in range(n, 0, -1):
        ifact[i-1] = ifact[i] * i % mod
def combination(n, k, mod):
    if k <0 or k>n:
        return 0
    return (fact[n]* ifact[k]* ifact[n-k]) %mod
X, Y = map(int, input().split())
if (X+Y)%3 != 0:
    print(0)
    exit()
N = int((X+Y)/3)
Nx = int((N + X - Y) /2)
Ny = int((N - X + Y) /2)
if Nx < 0 or Ny < 0:
    print(0)
    exit()
setFact(N, mod)
print(combination(N, Nx, mod))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
mod=pow(10,9)+7
if (2*x-y)%3!=0 or (2*y-x)%3!=0:
  print(0)
  exit(0)
a=(2*x-y)//3
b=(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

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 )

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

Submission status: Accepted

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

if x >= y:
    if not (2 * y - x) % 3:  
        ch2 = int((2 * y - x) / 3)
        if ch2 < 0:
            print(0)
            exit()
        ch1 = ch2 + x - y
    else:
        print(0)
        exit()

elif x < y:
    if not (2 * x - y) % 3:  
        ch1 = int((2 * x - y) / 3)
        if ch1 < 0:
            print(0)
            exit()
        ch2 = ch1 + y - x 
    else:
        print(0)
        exit()

def cmb(s, t, r):
    x = 1
    y = 1
    for i in range(t):
        x = (x*(s-i))%r
        y = (y*(i+1))%r
 
    y_inverse = pow(y, r-2, r)
    return (x*y_inverse)%r

mod = 10 ** 9 + 7

print(cmb(ch1+ch2,ch1,mod))

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

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

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

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

cnt = (x + y) // 3
x_cnt = x - cnt
y_cnt = y - cnt
min_cnt = min(x_cnt, y_cnt)

def nCr(n, r, mod):
    return g1[n] * g2[r] * g2[n - r] % mod

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

print(nCr(cnt, min_cnt, mod))

Submission status: Accepted

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


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 (x + y) % 3 != 0:
    print(0)
else:
    res = 0
    m, n = 0, 0
    while m * 2 <= x:
        n = x - m * 2
        if 2 * n + m == y:
            res += cmb(m + n, m, mod)
        m += 1
    print(res)

Submission status: Accepted

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
x,y=n1()

def comb(n,k):
    nCk = 1
    MOD = 10**9+7

    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= MOD

    for i in range(1,k+1):
        nCk *= pow(i,MOD-2,MOD)
        nCk %= MOD
    return nCk

if (x+y)%3!=0:
    print(0)
else:
    n=(x+y)//3
    if x-n>=0 and y-n>=0:
        ans=comb(n,x-n)
        print(ans)
    else:
        print(0)

Submission status: Accepted

Solution code:
import sys

input = lambda: sys.stdin.readline().rstrip()


def solve():
    X, Y = map(int, input().split())
    sm = min(X, Y)
    lg = max(X, Y)
    mod = 10**9 + 7
    m = [0] * (sm + 1)
    n = [-1] * (sm + 1)
    m[0] = 1
    n[0] = pow(m[0], mod - 2, mod)

    for i in range(1, sm + 1):
        m[i] = m[i - 1] * i % mod

    ans = 0
    for i in range(sm + 1):
        if (sm - i) % 2 == 0:
            b = (sm - i) // 2
            if b + i * 2 == lg:
                if n[i] == -1:
                    n[i] = pow(m[i], mod - 2, mod)
                if n[b] == -1:
                    n[b] = pow(m[b], mod - 2, mod)
                ans = (ans + m[i + b] * n[i] * n[b]) % mod

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def fer(n, r, p):
    # calculate n_C_k mod p
    # a,pが互いに素のとき a ^ (p-2) = a ^ -1 (mod p)
    x, y = 1, 1
    for i in range(r):
        x *= (n - i)
        x %= p
        y *= (i + 1)
        y %= p
    # x -> n * (n-1) * ... * (n-r+1)
    # y -> 1 * 2 * ... * r
    return x * pow(y, p - 2, p) % p


def main():
    x, y = map(int, input().split())

    if x/y < 1/2 or x/y > 2 or (x + y) % 3 != 0:
        print(0)
        exit()

    n, m = (2*y-x)//3, (2*x-y)//3
    ans = fer(n+m, n, 10 ** 9 + 7)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

fac=[1,1]
inv_t=[0,1]
finv=[1,1]
for i in range(2,MAX):
    fac.append(fac[-1]*i%mod)
    inv_t += [inv_t[mod % i] * (mod - mod // i) % mod]
    finv.append(finv[i-1]*inv_t[i]%mod)

x=2*X-Y
y=2*Y-X

if x%3!=0 or y%3!=0 or x*y<0:
    print(0)
else:
    x=x//3
    y=y//3
    n=x+y
    r=min(x,y)
    print((fac[n]*finv[r]*finv[n-r])%mod)

Submission status: Accepted

Solution code:
def nCr(n_, r_, m_):
  c = min(r_ , n_ - r_)
  bunshi = 1
  bunbo = 1
  for i in range(1,c+1):
    bunshi = bunshi * (n_+1-i) % m_
    bunbo = bunbo * i % m_
  return bunshi * pow(bunbo, m_-2, m_) % m_


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

Submission status: Accepted

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

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

tmp=(x+y)//3
x=x-tmp
y=y-tmp
sosu=10**9+7
if x<0 or y<0:
    print(0)
    sys.exit()

def combination(x,y):
    n=x+y
    r=min(x,y)
    upper=1
    lower=1
    for i in range(r):
        upper=(upper*(n-i))%sosu
        lower=(lower*(i+1))%sosu
    return (upper * pow(lower,sosu-2,sosu))%sosu
print(combination(x,y))

Submission status: Accepted

Solution code:
import sys

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

if (2 * X - Y) % 3 != 0 or (2 * Y - X) % 3 != 0:
    # 整数解がない場合
    print(0)
    sys.exit()


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

# これか？
if m < 0 or n < 0:
    print(0)
    sys.exit()

u = m + n
fact = [1] * (u+1)

for i in range(1, u+1):
    fact[i] = (fact[i-1] * i) % mod

fact_inv1 = pow(fact[n], mod-2, mod)
fact_inv2 = pow(fact[m], mod-2, mod)

res = (((fact[u] * fact_inv1) % mod) * fact_inv2) % mod

print(res)

Submission status: Accepted

Solution code:
import sys

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

# if (2 * X - Y) % 3 != 0 or (2 * Y - X) % 3 != 0:
if (X + Y) % 3 != 0:
    # 整数解がない場合
    print(0)
    sys.exit()


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

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

u = m + n
fact = [1] * (u+1)

for i in range(1, u+1):
    fact[i] = (fact[i-1] * i) % mod

fact_inv1 = pow(fact[n], mod-2, mod)
fact_inv2 = pow(fact[m], mod-2, mod)

res = (((fact[u] * fact_inv1) % mod) * fact_inv2) % mod

print(res)