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:
import sys
sys.setrecursionlimit(10**6)

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

MOD = 10 ** 9 + 7

import functools
import math

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

# 方程式を解けば解が一意に定まるため、全パターンを試すのは無駄
def solver_not_good():
    factorial = [0] * (10 ** 6 + 1)
    inverse = [0] * (10 ** 6 + 1)
    factorial[0] = 1
    inverse[0] = 1
    for i in range(1, 10 ** 6 + 1):
        factorial[i] = (i * factorial[i-1]) % MOD
        inverse[i] = mpow(factorial[i], MOD - 2) % MOD

    total = 0
    twopath_maxnum = x // 2
    for twopath_num in range(twopath_maxnum + 1):
        onepath_num = x - twopath_num * 2
        if (onepath_num * 2 + twopath_num * 1) == y:
            a = factorial[onepath_num + twopath_num]
            b = inverse[onepath_num]
            c = inverse[twopath_num]
            total += (a * b * c) % MOD
    return total

def solver_better():
    # 剰余演算を都度挟みたいため、math.factorialは使えない
    factorial = [0] * (10 ** 6 + 1)
    factorial[0] = 1
    for i in range(1, 10 ** 6 + 1):
        factorial[i] = (i * factorial[i-1]) % MOD

    # x + y が3の倍数でないときは到達できない
    if ((x + y) % 3) != 0:
        return 0

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

    # x座標/y座標のどちらかに先に到達してしまう
    if a < 0 or b < 0:
        return 0

    return (factorial[a+b] * (mpow(factorial[a], MOD - 2) % MOD) * (mpow(factorial[b], MOD -2) % MOD)) % MOD

solver = solver_not_good
#solver = solver_better
print(solver())

Submission status: Accepted

Solution code:
import numpy as np
from math import factorial
MOD = 10 ** 9 + 7

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

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



U = 10**6
fact, fact_inv = make_fact(U,MOD)

X, Y = map(int, input().split())
if (X + Y) % 3 != 0:
    print(0)
    exit()
time = (X+Y) // 3
diff = X - Y
if abs(diff) > time:
    print(0)
    exit()
x_time = (time+diff) // 2

answer = fact[time] * fact_inv[x_time] % MOD * fact_inv[time-x_time] % MOD
print(answer)

Submission status: Accepted

Solution code:
#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a//b, b, a%b
        x0, x1 = x1, x0 -q*x1
        y0, y1 = y1, y0 -q*y1
    return a, x0, y0

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

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

    divider = 10**9 + 7

    m = 2 * X - Y
    n = 2 * Y - X

    if m%3 != 0 or n%3 != 0 or n < 0 or m < 0:
        print(0)
        return
    m //= 3
    n //= 3

    if m < n:
        m, n = n, m

    ans = 1
    for i in range(m+n, m, -1):
        ans *= i
        ans %= divider

    for i in range(n, 0, -1):
        ans *= modinv(i, divider)
        ans %= divider

    print(ans)

# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc145","d",main)

Submission status: Accepted

Solution code:
#!/usr/bin/python

import sys
from pprint import pprint

import math

def nCr(n, r):
    v = 10**9 + 7
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n - r, r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def cmb_mod(n, r, mod):
    r = min(n - r, r)
    if r == 0:
        return 1
    else:
        denominator = 1
        for i in range(n, n - r, -1):
            denominator = (denominator * i) % mod
        numerator = 1
        for i in range(1, r + 1):
            numerator = (numerator * i) % mod
        return denominator * pow(numerator, mod - 2, mod) % mod 

x, y = map(int, sys.stdin.readline().strip().split(" "))

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

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

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

# print(n, m)
# print(nCr(n+m, n) % (10**9+7))
print(cmb_mod(n + m, n, 10**9 + 7))

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce

X,Y = map(int,input().split()[:2])

if (X + Y) % 3 or not (X <= 2*Y and Y <= 2*X):
    print(0)
    exit()

x_tmp=X+1
y_tmp=Y+2

x_count=0
y_count=0

while x_tmp*2 != y_tmp:
    x_tmp-=2
    y_tmp-=1
    x_count+=1

y_count = y_tmp//2 - 1

sum = x_count + y_count

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

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

ret = cmb(sum,x_count,mod)
print(ret)

Submission status: Accepted

Solution code:
#互いに素な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は互いに素であることが前提)
def mod_inv(a,m):
    if a%m!=0:
      x = extgcd(a,m)[0]
      return (m+x%m)%m
      

#nCk mod m を計算する(デフォルトの引数は10**9+7)
def c_mod(n,k,m=10**9+7):
  res = 1
  for i in range(1,n+1):
      if (i%m)!=0:
        res = res*i%m
      else:
        res=res/i%m
  for i in range(1,k+1):
      if (i%m)!=0:
        res = res*mod_inv(i,m)%m
      else:
        res=res/i%m
  for i in range(1,n-k+1):
      if (i%m)!=0:
        res = res*mod_inv(i,m)%m
      else:
        res=res/i%m
  return res


x,y=map(int,input().split())
if (2*x-y)%3==0 and (2*y-x)%3==0 and (2*y-x)>=0 and (2*x-y)>=0 :
  l=int((2*x-y)/3)
  k=int((2*y-x)/3)
  ans=c_mod(l+k,k)

else:
  ans=0
print(ans)

Submission status: Accepted

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

x,y=map(int,input().split())
if (2*x-y)%3==0 and (2*y-x)%3==0 and (2*x-y)>=0 and (2*y-x)>=0 :
  l=int((2*x-y)/3)
  k=int((2*y-x)/3)
  ans=c_mod(l+k,k)

else:
  ans=0
print(ans)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce
import sys
x,y = map(float,input().split())
m = (2*x - y)/3
n = (y - m)/2
if not (m.is_integer() and n.is_integer()):
  print(0)
  sys.exit()
if n < 0 or m < 0:
  print(0)
  sys.exit()
m = int(m)
n = int(n)
mod = 10**9 + 7
def cmb(h, r):
    if h - r < r: r = h - r
    if r == 0: return 1
    if r == 1: return h
    r = int(r)

    humerator = [h - r + k + 1 for k in range(r)]
    dehominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = dehominator[p - 1]
        if pivot > 1:
            offset = (h - r) % p
            for k in range(p-1,r,p):
                k = int(k)
                offset = int(offset)
                humerator[k - offset] /= pivot
                dehominator[k] /= pivot

    result = 1
    for k in range(r):
        if humerator[k] > 1:
            result *= int(humerator[k])

    return result
if (x + y) % 3 != 0:
  print(0)
else:
  print(cmb(n + m,n)%mod)

Submission status: Accepted

Solution code:
X,Y = list(map(int,input().split()))
def nCk(n, k, mod=10 ** 9 + 7):
    if n < k:
        return 0
    k = min(k, n - k)
    numer = 1
    for x in range(n - k + 1, n + 1):
        numer = (numer * x) % mod
    denom = 1
    for x in range(1, k + 1):
        denom = (denom * x) % mod
    return numer * pow(denom, mod - 2, mod) % mod
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, m)%(7+10**9))

Submission status: Accepted

Solution code:
X,Y = map(int,input().split())
 
c1 = (2*Y-X)
rest = c1%3
c1 = c1//3
if (rest!=0)or((X-c1)<0)or((Y-2*c1)<0)or(c1<0):
  print(0)

else:
  c2 = Y-2*c1
  c3 = c1+c2+1
  mod = 10**9+7
  c4 = min(c1,c2)
  x = 1
  y = 1
  for i in range(1,c4+1):
    x = x * (c3-i) % mod
    y = y * i % mod
    
  result = x * pow(y,mod-2,mod) % mod
 
  print(result)

Submission status: Accepted

Solution code:
from functools import reduce

def main():
    mod = 10 ** 9 + 7

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

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

    if (X + Y) % 3 != 0 or a < 0 or b < 0:
        print(0)
        quit(0)

    n, k = a + b, a
    k = min(k, n - k)
    mod_mul = lambda a, b: a * b % mod
    numer = reduce(mod_mul, range(n - k + 1, n + 1), 1)
    denom = reduce(mod_mul, range(1, k + 1), 1)

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

main()

Submission status: Accepted

Solution code:
from functools import reduce

def main():
    def nCk(n, k, mod=10 ** 9 + 7):
        if n < k:
            return 0
        k = min(k, n - k)
        mod_mul = lambda a, b: a * b % mod
        numer = reduce(mod_mul, range(n - k + 1, n + 1), 1)
        denom = reduce(mod_mul, range(1, k + 1), 1)
        return numer * pow(denom, mod - 2, mod) % mod

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

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

    if (X + Y) % 3 != 0 or a < 0 or b < 0:
        print(0)
    else:
        print(nCk(a + b, a))

main()

Submission status: Accepted

Solution code:
from functools import reduce

def nCk(n, k, mod=10 ** 9 + 7):
    if n < k:
        return 0
    k = min(k, n - k)
    mod_mul = lambda a, b: a * b % mod
    numer = reduce(mod_mul, range(n - k + 1, n + 1), 1)
    denom = reduce(mod_mul, range(1, k + 1), 1)
    return numer * pow(denom, mod - 2, mod) % mod

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

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

if (X + Y) % 3 != 0 or a < 0 or b < 0:
    print(0)
else:
    print(nCk(a + b, a))

Submission status: Accepted

Solution code:
## D
import numpy as np
import math

def cmb(n, k, mod):
    numerator = 1
    for i in range(k):
        numerator = (numerator * (n-i)) % mod
 
    denominator = 1
    for i in range(1, k+1):
        denominator = (denominator * i) % mod
 
    return (numerator * pow(denominator, mod-2, mod)) % mod
    
    return int((n_frac * n_r_ifrac * r_ifrac) % mod)

mod = 10**9+7
x,y = map(int, input().split()) 
is_ok = True
b = (2 * x - y) / 3
a = x - 2 * b
if not (a.is_integer() and b.is_integer()):
    ans = 0
    is_ok = False
    
a = int(a)
b = int(b)
if a < 0 or b < 0:
    ans = 0
    is_ok = False
if is_ok:    
    ans = cmb(a+b, a, mod)
print(ans)

Submission status: Accepted

Solution code:
def nCk(n, k, mod=10 ** 9 + 7):
    if n < k:
        return 0
    k = min(k, n - k)
    numer = 1
    for x in range(n - k + 1, n + 1):
        numer = (numer * x) % mod
    denom = 1
    for x in range(1, k + 1):
        denom = (denom * x) % mod
    return numer * pow(denom, mod - 2, mod) % mod

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

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

if (X + Y) % 3 != 0 or a < 0 or b < 0:
    print(0)
else:
    print(nCk(a + b, a))

Submission status: Accepted

Solution code:
#Beginner COnetst 145 /2019/11/16
#Probrem A
from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

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

def calc(x,y):
    if (x*2-y)%3 != 0 or (y*2-x)%3 != 0: return 0
    m = (x*2-y)//3
    n = (y*2-x)//3
    if m < 0 or n < 0:return 0
    #return combinations_count(m+n,m)
    return cmb(m+n,m,mod)

DEBUG = 0

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 DEBUG:print(X,Y)

print(calc(X,Y))

Submission status: Accepted

Solution code:
from numpy.linalg import solve


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


MOD = 10 ** 9 + 7
MAX = 10**6
x, y = map(int, input().split())
if (x + y) % 3 != 0:
    print(0)
    exit(0)
l = solve([[2, 1], [1, 2]], [x, y])
if l[0] < 0 or l[1] < 0:
    print(0)
    exit(0)
print(COM(int(l[0]+l[1]), int(l[0])))

Submission status: Accepted

Solution code:
import numpy as np
from operator import mul
from functools import reduce

MOD = 10**9+7
def calc(a,b=MOD-2):
    if b==0: return 1
    elif b%2==0: return (calc(a,b/2)**2)%MOD
    else: return (a*calc(a,b-1))%MOD

X,Y = list(map(int,input().split()))
i, j = (X-2*Y), (-2*X+Y)

if i%3==0 and i<=0 and j%3==0 and j<=0:
    i,j = -i//3,-j//3
    i,j = min(i,j), max(i,j)
    n,m = 1,1
    for k in range(i): n = (n * (i+j-k))%MOD
    m = calc(np.math.factorial(i))%MOD
    print((n*m)%MOD)
else: print(0)

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)

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

if not float.is_integer(a) or not float.is_integer(b):
    print(0)
    exit()

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

Submission status: Accepted

Solution code:
import math

x, y = map(int,input().split())
mod = 10**9+7 #出力の制限

def cmb(n, k,MOD):
    if k > n - k:
        k = n - k
    ans = 1
    for i in range(1, k + 1):
        ans *= n + 1 - i
        ans *= pow(i, MOD - 2, MOD)
        ans %= MOD
    return ans

if (x+y)%3 != 0:
    ans = 0
else:
    m = (2*x - y) //3
    n = x - 2*m
    # print(m,n)
    if m <0 or n < 0 :
        ans = 0
    else:
        ans = cmb(n+m, m, mod)
print(ans)

Submission status: Accepted

Solution code:
def main():
    def nCk(n, k, mod=10 ** 9 + 7):
        def xgcd(a, b):
            if b == 0:
                return (1, 0)
            x, y = xgcd(b, a % b)
            return (y, x - (a // b) * y)
        p, q = 1, 1
        for i in range(n - k + 1, n + 1):
            p = (p * i) % mod
        for i in range(2, k + 1):
            q = (q * i) % mod
        return p * (xgcd(q, mod)[0] % mod) % mod


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

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

    if (X + Y) % 3 != 0 or a < 0 or b < 0:
        print(0)
    else:
        print(nCk(a + b, a))

main()

Submission status: Accepted

Solution code:
mod = 10**9+7

def fact(n):
    ans = 1
    for i in range(2,n+1):
        ans *= i
        ans %= mod
    return ans
    
X,Y = list(map(int,input().split()))

# a+2b = X
# 2a+b = Y を解く
# -> a = (2Y-X)/3, b = (2X-Y)/3
# (i+1,j+2) の移動が a 回
# (i+2,j+1) の移動が b 回

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

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

# a回とb回の移動の組み合わせは (a+b)!/a!b!
print(fact(int(a+b)) * pow(fact(int(a)),mod-2,mod) * pow(fact(int(b)),mod-2,mod) % mod)

Submission status: Accepted

Solution code:

a, b = map(int, input().split())

aa=int(0)
x=max([a, b])
y=min([a, b])

if (x+y)%3 ==0 and x <= y*2:
    aa=int(1)

n=int((x+y)/3)
k=int((n-(x-y))/2)


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

if aa==1:
    print(comb(n,k))
else:
    print(aa)

Submission status: Accepted

Solution code:
def nCk(n, k, mod=10 ** 9 + 7):
    def xgcd(a, b):
        if b == 0:
            return (a, 1, 0)
        g, x, y = xgcd(b, a % b)
        return (g, y, x - (a // b) * y)
    p, q = 1, 1
    for i in range(n - k + 1, n + 1):
        p = (p * i) % mod
    for i in range(2, k + 1):
        q = (q * i) % mod
    return p * (xgcd(q, mod)[1] % mod) % mod


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

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

if (X + Y) % 3 != 0 or a < 0 or b < 0:
    print(0)
else:
    print(nCk(a + b, a))

Submission status: Accepted

Solution code:
#import sys

#input = sys.stdin.readline
import math
import itertools
#import bisect

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

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

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def main():
#    h,w,a,b = map(int, input().split())
    x,y = map(int,input().split())
    a=max(x,y)
    b=min(x,y)

    t=a//2
    if b<t:
       ans=0
    elif (b-t)%3==0 and a%2==0:
       aa=a//2
       bb=(b-t)//3*2
       aa-=(b-t)//3
       ans=1
       ans=cmb(aa+bb,bb)

    elif (b-t+1)%3==0 and a%2!=0:
       aa=a//2
       bb=(b-t)//3*2+1
       aa -= (b - t) // 3
       ans=1
       ans=cmb(aa+bb,bb)

    else:
        ans=0


#    print(ans)
    print(ans%(10**9+7))
if __name__ == "__main__":
    main()

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

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

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

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

n = a + b
r = min(a, b)

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)

print(cmb(n, r, mod))

Submission status: Accepted

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

if (x+y)%3!=0:
    print(0)
else:
    a = x-(x+y)//3
    b = y-(x+y)//3
    print(cmb(a+b,a,mod))

Submission status: Accepted

Solution code:
x, y = map(int, input().split())
if (x+y)%3 != 0:
    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 )
 
 
# a = (2*x-y)//3
# b = (2*y-x)//3
a = y - (x+y)//3
b = x - (x+y)//3
n = a+b
r = a
res = cmb((x+y)//3,r,mod)
print(res)

Submission status: Accepted

Solution code:
import sys

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

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

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

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

MOD = 10**9 + 7

MAX = max(x,y)
MIN = min(x,y)

if (2*MAX - MIN) % 3 != 0 or MAX / MIN > 2:
	print(0)
	sys.exit()

c1 = (2*MAX - MIN) // 3
c2 = MAX - 2*c1

c1 %= MOD
c2 %= MOD

ans = cmb(c1 + c2 , c1)
print(ans%MOD)

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    x, y = map(int, args[0].split())
    ret = 0
    mod = 1000000007

    if (x+y) % 3 == 0 and not (x > 2*y or y > 2*x):
        ret = 1
        a = (2*y-x)//3
        b = (2*x-y)//3
        for n in range(a+b, a, -1):
            ret = (ret * (n % mod)) % mod

        div = 1
        for k in range(b, 1, -1):
            div = (div * (k % mod)) % mod

        ret = (ret * pow(div, mod-2, mod)) % mod

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

Solution code:
# import math
# from operator import mul
# from functools import reduce
x,y = map(int, input().split())
n = (x+y)//3
r = (2*x-y)//3
mod = 10**9+7
N = 10**6
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
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)
elif 2*x-y<0:
    print(0)
elif -x+2*y<0:
    print(0)
else:
    # print((math.factorial((x+y)//3)//(math.factorial((2*x-y)//3)*math.factorial((2*y-x)//3)))%mod)
    # print(combinations_count(n,r)%mod)
    print(cmb(n,r,mod))

Submission status: Accepted

Solution code:
MOD = 10**9 + 7


def comb(n, k, MOD):
    if n < k or n < 0 or k < 0:
        return 0
    if k > n - k:
        k = n - k
    ans = 1
    for i in range(1, k + 1):
        ans *= n + 1 - i
        ans %= MOD
        ans *= pow(i, MOD - 2, MOD)  # a //= i
        ans %= MOD
    return ans


x, y = map(int, input().split())
a = 2 * y - x
b = 2 * x - y

if a < 0 or b < 0:
    ans = 0
elif a % 3 != 0 or b % 3 != 0:
    ans = 0
else:
    a //= 3
    b //= 3
    # print(a, b)
    ans = comb(a + b, a, MOD)

print(ans)

Submission status: Accepted

Solution code:
x, y = map(int, input().split())
if (x+y)%3 != 0:
    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 )
 
 
# a = (2*x-y)//3
# b = (2*y-x)//3
a = y - (x+y)//3
b = x - (x+y)//3
n = a+b
r = a
res = cmb(n,r,mod)
print(res)

Submission status: Accepted

Solution code:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    
    return result
        
X, Y = map(int, input().split(' '))
a = -1
b = -1
    
if (2*Y-X)%3 == 0 and (2*X-Y)%3 == 0:
    a = (2*X-Y)//3
    b = (2*Y-X)//3
    
    
    
if a < 0 or b < 0:
    ans = 0
else:
    ans = cmb(a+b, b)
print(ans % 1000000007)

Submission status: Accepted

Solution code:
import math

MAX=1000000
MOD=1000000007

fac=[1,1]
finv=[1,1]
inv=[1,1]

for i in range(2,MAX):
	fac.append(fac[i-1] * i % MOD)
	inv.append(MOD - inv[ MOD % i ] * (int(MOD / i)) % MOD)
	finv.append(finv[i - 1] * inv[i] % MOD)

def COM(nnn, kkk):
	if nnn < kkk:
		return 0
	
	if nnn < 0 or kkk < 0:
		return 0
	
	return fac[nnn] * (finv[kkk] * finv[nnn-kkk] % MOD) % MOD


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

n = 2 * x - y
m = 2 * y - x

ans = 0
if n % 3 == 0:
	if m % 3 == 0:
		nn = int(n / 3)
		mm= int(m / 3)
		ans = COM(nn+mm,nn)

print(ans)

Submission status: Accepted

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

mod = 10**9+7 #出力の制限
N = 10**6+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 )

x,y=map(int,input().split())
if (x+y)%3==0 and x<=2*y and y<=2*x:
    a=abs(2*y-x)//3
    b=abs(y-2*x)//3
    print(cmb(a+b,min(a,b),mod))
else:print(0)

Submission status: Accepted

Solution code:
x, y = map(int, input().split())
if (x+y)%3 != 0:
    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 )
 
 
a = (2*x-y)//3
b = (2*y-x)//3
n = a+b
r = a
res = cmb(n,r,mod)
print(res)

Submission status: Accepted

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

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

if a<0 or b<0:
  print(0)
  sys.exit()
  
f=[1]
for i in range(1,a+b+1):
    f.append(f[-1]*i%mod)

if a+2*b==x and 2*a+b==y:
    print(f[a+b]*pow(f[a],mod-2,mod)*pow(f[b],mod-2,mod)%mod)
else:
    print(0)

Submission status: Accepted

Solution code:
def combinations_count(n, k, M):
    if k == 0:
        return 1
    fn = 0
    fk = 0
    fnk = 0
    cur = 1
    M = int(1e9+7)
    for i in range(1, n+1):
        cur = (cur * i) % M
        if i == n:
            fn = cur
        if i == n-k:
            fnk = cur
        if i == k:
            fk = cur
 
    return (fn * (modpow(fk , (M-2), M)) * modpow(fnk , (M-2), M))%M

def modpow(a,b,M):
    if b == 1:
        return a % M
    if b % 2 == 1:
        return (modpow(a,(b-1)//2,M)**2 * a)%M
    return (modpow(a,b//2,M) ** 2) % M 

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

if ((x+y)%3!=0 or (2<max(x,y)/min(x,y))):
    print(0)
    exit(0)

max_value=max(x,y)
min_value=min(x,y)

base_max=max_value//2
base_min=max_value%2

diff_value=min_value-base_min*2-base_max

base_max-=diff_value//3
base_min+=diff_value//3*2

print(combinations_count(base_max+base_min,min(base_max,base_min),10**9+7))

Submission status: Accepted

Solution code:
MOD = 10**9 + 7


def comb(n, k, MOD):
    if k > n - k:
        k = n - k
    ans = 1
    for i in range(1, k + 1):
        ans *= n + 1 - i
        ans *= pow(i, MOD - 2, MOD)  # a //= i
        ans %= MOD
    return ans


x, y = map(int, input().split())
a = 2 * y - x
b = 2 * x - y

if a < 0 or b < 0:
    ans = 0
elif a % 3 != 0 or b % 3 != 0:
    ans = 0
else:
    a //= 3
    b //= 3
    # print(a, b)
    ans = comb(a + b, a, MOD)

print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7


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


x, y = map(int, input().split())
a = 2 * y - x
b = 2 * x - y

if a < 0 or b < 0:
    ans = 0
elif a % 3 != 0 or b % 3 != 0:
    ans = 0
else:
    a //= 3
    b //= 3
    # print(a, b)
    ans = comb(a + b, a)

print(ans)

Submission status: Accepted

Solution code:
A,B=map(int,input().split())

if B>A:
    A,B=B,A

X=A-B

Y=B-X

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

Z=(Y*2)//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(Z+X,Z//2,mod))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def get_z(y, x): # y/x (mod 1000000007)
    inv_x = pow(x, MOD - 2, MOD)
    return y * inv_x % MOD

def comb_mod(n, k):
    if n == 0:
        return 0
    k = min(k, n - k)
    a = 1
    b = 1
    for i in range(k):
        a = a * (n - i) % MOD
        b = b * (i + 1) % MOD
    ret = get_z(a, b)
    return ret


def solve(X: int, Y: int):
    d = X - Y
    s = (X + Y) // 3
    x = (s + d) // 2
    y = (s - d) // 2
    if (X + Y) % 3 or (s + d) % 2 or x < 0 or y < 0 \
            or x * 2 + y != X or x + y * 2 != Y:
        print(0)
        return
    ret = comb_mod(x + y, min(x, y))
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(X, Y)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import reduce

def cmb(n, r):
    r = min(r, n - r)
    if r == 0:
        return 1
    over = reduce(lambda a, b: a * b % mod, range(n, n - r, -1))
    under = reduce(lambda a, b: a * b % mod, range(1, r + 1))
    return over * pow(under, mod-2, mod) % mod

x, y = [int(i) for i in input().split()]
if (x + y) % 3 or x > 2 * y or y > 2 * x:
    print(0)
else:
    mod = 10**9 + 7
    print(cmb((x + y) // 3, (2 * x - y) // 3))