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


def alg_combination_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
        molecule = 1
        for i in range(1, r + 1):
            molecule = (molecule * i) % mod
        return denominator * pow(molecule, mod - 2, mod) % mod


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    x, y = list(map(int, input().rstrip('\n').split()))
    if (x + y) % 3 == 0:
        cnt = (x + y) // 3
        for i in range(0, cnt + 1):
            if (cnt - i) + i * 2 == x and (cnt - i) * 2 + i == y and cnt - i >= 0:
                print(alg_combination_mod(cnt, i, mod))
                exit()
        print(0)
    else:
        print(0)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
mod = 10**9 + 7
if (x+y)%3 != 0:
    print(0)
    exit()
n = (x+y)//3
a = (2 * x - y) // 3
b = (2 * y - x) // 3
if a == 0 or b == 0:
    print(1)
    exit()
if a < 0 or b < 0:
    print(0)
    exit()
MAX = 700000
fac = [1,1] + [0] * MAX     #累積積
finv = [1,1] + [0] * MAX    #modにおける逆元
inv = [0,1] + [0] * MAX     #invの累積積
for i in range(2,MAX):
    fac[i] = fac[i-1] * i % mod
    inv[i] = -inv[mod%i] * (mod//i)%mod
    finv[i] = finv[i-1] * inv[i]%mod


def nCr(n,r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fac[n] * (finv[r] * finv[n-r]%mod)%mod

print(nCr(n,a))

Submission status: Accepted

Solution code:
x, y = map(int, input().split())
mod = 10**9 + 7
if (x + y) % 3 != 0:
    print(0)
    exit()
n = (x + y) // 3
a = (2 * y - x) // 3
b = (2 * x - y) // 3
if a == 0 or b == 0:
    print(1)
    exit()
if a < 0 or b < 0:
    print(0)
    exit()
MAX = 700000
fac = [1, 1] + [0] * MAX
finv = [1, 1] + [0] * MAX
inv = [0, 1] + [0] * MAX
for i in range(2, MAX):
    fac[i] = fac[i - 1] * i % mod
    inv[i] = -inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod


def nCr(n, r):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod


print(nCr(n, a))

Submission status: Accepted

Solution code:
import sys

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

def solver(x, y):


    if (x, y) == (0, 0):
        return 0
    if (x+y)%3 != 0:
        return 0
    k = (x+y)//3
    (xi, yi) = (k, 2*k)
    for i in range(k+1):
        if (xi, yi) == (x, y):
            return comb_num_mod(k, i) 
        else:
            (xi, yi) = (xi+1, yi-1)
    return 0

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

Submission status: Accepted

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


def ppp(a, b, m):  # a^b%modを求めたい
    if b == 0:
        return 1
    elif b % 2 == 0:
        return ppp(a, b // 2, m) ** 2 % m
    else:
        return ppp(a, (b - 1) // 2, m) ** 2 * a % m


def knight(x, y):
    mod = 10 ** 9 + 7
    x, y = min(x, y), max(x, y)

    if (x + y) % 3 != 0:
        return 0
    if y > 2 * x:
        return 0

    move = (x + y) // 3
    right = 2 * move - y
    up = move-right

    ans = 1
    tmp = 1
    for i in range(up):
        ans *= (move - i)
        tmp *= i + 1
        ans %= mod
        tmp %= mod
    ans *= ppp(tmp, mod - 2, mod)
    return ans % mod


if __name__ == "__main__":
    x, y = map(int, input().split())
    ans = knight(x, y)
    print(ans)

Submission status: Accepted

Solution code:
def knight(x, y):
    mod = 10 ** 9 + 7
    x, y = min(x, y), max(x, y)

    if (x + y) % 3 != 0:
        return 0
    if y > 2 * x:
        return 0

    move = (x + y) // 3
    right = 2 * move - y
    up = move-right

    ans = 1
    tmp = 1
    for i in range(up):
        ans *= (move - i)
        tmp *= i + 1
        ans %= mod
        tmp %= mod
    ans *= pow(tmp, mod - 2, mod)
    return ans % mod


if __name__ == "__main__":
    x, y = map(int, input().split())
    ans = knight(x, y)
    print(ans)

Submission status: Accepted

Solution code:
def knight(x, y):
    mod = 10 ** 9 + 7
    x, y = min(x, y), max(x, y)

    if (x + y) % 3 != 0:
        return 0
    if y > 2 * x:
        return 0

    move = (x + y) // 3
    right = 2 * move - y
    up = move-right

    ans = 1
    for i in range(up):
        ans *= (move - i)
        ans *= pow(i + 1, mod - 2, mod)
        ans %= mod

    return ans


if __name__ == "__main__":
    x, y = map(int, input().split())
    ans = knight(x, y)
    print(ans)

Submission status: Accepted

Solution code:
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

# ax ≡ 1 (mod m)

def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    #print(inv, q, gcd_val)
    return inv % m

def m(n,r):
    d=1
    e=1
    f=1
    for i in range(r):
        d=(n-i)
        e=(i+1)
        d%=(10**9+7)
        f = f*d*modinv(e,(10**9+7))%(10**9+7)
        
    return(f)

n=[int(i) for i in input().split()]
a=sum(n)
if a%3 != 0:print(0)

else:
    b=int(a/3)
    if b==1:
        print(1)
    else:
        c=n[0]-b
        d=n[1]-b
        if c<0 or d<0: print(0)

        else:
            if c==d:
                c=int(b/2)
            #d=m(b,min(c,d))
            print(m(b,min(c,d)))

Submission status: Accepted

Solution code:
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

# ax ≡ 1 (mod m)

def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    #print(inv, q, gcd_val)
    return inv % m

def m(n,r):
    d=1
    e=1
    f=1
    for i in range(r):
        d=(n-i)
        e=(i+1)
        d%=(10**9+7)
        f = f*d*modinv(e,(10**9+7))%(10**9+7)
        
    return(f)

n=[int(i) for i in input().split()]
a=sum(n)
if a%3 != 0:print(0)

else:
    b=int(a/3)
    if b==1:
        print(1)
    else:
        c=n[0]-b
        d=n[1]-b
        if c<0 or d<0: print(0)

        else:
            if c==d:
                c=int(b/2)
            d=m(b,min(c,d))
            print(d%(10**9+7))

Submission status: Accepted

Solution code:
import math
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

X,Y=LI()

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

FACT = FLIST(1000000)
if (2*X - Y)%3 == 0 and (2*Y - X)%3 == 0 and a >= 0 and b >= 0:
    print(DIV(DIV(FACT[a+b], FACT[a]), FACT[b]))
else:
    print(0)

Submission status: Accepted

Solution code:
def multiple_of_n(x, y, n=3):
    return (x - y) % n == 0

def combination(g1, g2, inverse, 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 make_inv(mod, N):
    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)
    return g1, g2, inverse

mod = 10 ** 9 + 7

x, y = map(int, input().split())
if multiple_of_n(2 * x, y) and multiple_of_n(2 * y, x):
    vertical = (2 * y - x) // 3
    horizontal = (2 * x - y) // 3
    total = vertical + horizontal
    g1, g2, inverse = make_inv(mod, total)
    print(combination(g1, g2, inverse, total, horizontal, mod))
else:
    print(0)

Submission status: Accepted

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

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

mod = 10**9 + 7

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

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

Submission status: Accepted

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

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

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

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

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

n=(X+Y)//3
k=Y-(X+Y)//3

if k<0 or k>n:
  print(0)
  exit()
  
#print("n,k:",n,k)
print(cmb(n,k,mod))

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

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

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

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

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
if (x+y)%3:
    print(0)
    exit()
x,y=min(x,y),max(x,y)
sa=y-x
wa=y+x
z=(x+y)//3
if sa>x:
    print(0)
    exit()


mod=10**9+7
fact=[1]
fact_inv=[1]
for i in range(10**6+1):
    new_fact=fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))

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

print(mod_comb(z,x-z,mod))

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
if (x+y)%3:
    print(0)
    exit()
x,y=min(x,y),max(x,y)
sa=y-x
wa=y+x
z=(x+y)//3
if sa>x:
    print(0)
    exit()


mod=10**9+7
fact=[1]
fact_inv=[1]
for i in range(10**6+5):
    new_fact=fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))

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

print(mod_comb(z,x-z,mod))

Submission status: Accepted

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

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

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

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

print(nCr((x+y)//3,n))

Submission status: Accepted

Solution code:
X, Y = list(map(int, input().split()))
s = (X + Y) // 3
if s * 3 < X + Y:
  print(0)
  exit()
a = Y - s
b = X - s
if a < 0 or b < 0:
  print(0)
  exit()
  
m = 1000000007

def qmul(x, k):
  if k == 0:
    return 1
  if k == 1:
    return x
  t = qmul(x, k // 2)
  t = t * t % m
  if k % 2 == 1:
    t = t * x % m
  return t
ans = 1
for i in range(a + b, a, -1):
  ans = ans * i % m
d = 1
for i in range(b):
  d = d * (i + 1) % m
ans = ans * qmul(d, m - 2) % m
print(ans)

Submission status: Accepted

Solution code:
mod = int(1e9 + 7)
x, y = map(int,input().split())
if(2*x < y or 2*y < x or (2*x-y)%3 or (2*y-x)%3): print(0)
else:
    x, y = (2*x-y)//3, (2*y-x)//3
    #print(x,y)
    fac = [0 for i in range(x+y+1)]
    fac[0] = 1
    for i in range(1,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,mod)%mod
    print(ans)

Submission status: Accepted

Solution code:
mod = int(1e9 + 7)
def powmod(a, b):
    ans = 1
    while(b):
        if(b&1): ans = ans*a%mod
        a = a*a%mod
        b >>= 1
    return ans
x, y = map(int,input().split())
if(2*x < y or 2*y < x or (2*x-y)%3 or (2*y-x)%3): print(0)
else:
    x, y = (2*x-y)//3, (2*y-x)//3
    #print(x,y)
    fac = [0 for i in range(x+y+1)]
    inv = [0 for i in range(x+y+1)]
    fac[0] = 1
    for i in range(1,x+y+1):
        fac[i] = fac[i-1]*i%mod
    inv[x+y] = powmod(fac[x+y],mod-2)
    for i in range(x+y-1,-1,-1):
        inv[i] = inv[i+1]*(i+1)%mod
    ans = fac[x+y]*inv[x]*inv[y]%mod
    print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())


mod=10**9+7 

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

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

Submission status: Accepted

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

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

mod=10**9+7 

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

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

print(nCr(a,n,mod))

Submission status: Accepted

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


MOD=10**9+7
def mod(a):
    return a%MOD

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

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

def po(a,b):
    if(b==0):return 1
    if(b==1):return mod(a)
    if(b%2==0):return mod(po(mod(a*a),b/2))
    return mod(po(a,b-1)*a)
    
def bunbo(a):
    return po(a,MOD-2)
    
def comb(a,b):
    res=kai[a]
    res=mod(res*bunbo(kai[b]))
    res=mod(res*bunbo(kai[a-b]))
    return res
    
N=(10**6)*2+5
#N=100
kai=[0]*N

kai[0]=1
for i in range(1,N-1):
    kai[i]=mod(kai[i-1]*i)

#print(kai)
print(comb(int(x+y),int(x)))
"""
for i in range(8):
    for j in range(i):
        print(comb(i,j),end=" ")
    print()
"""

Submission status: Accepted

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

mod = 10**9 + 7

# import math
# def comb(n,r):
#     return (math.factorial(n)//(math.factorial(n-r)*math.factorial(r)))

# def comb(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 comb_mod(n, r, mod):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    else:
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, n + 1):
            fac.append(fac[-1] * i % mod)
            inv.append(-inv[mod % i] * (mod // i) % mod)
            finv.append((finv[-1] * inv[-1]) % mod)
        return int(fac[n] * finv[r] * finv[n - r] % mod)


# def comb(n,r,mod):
# 	'''
# 	return nCr
# 	O(min{n-r, r})
# 	'''
# 	a=1
# 	b=1
# 	r = min(r,n-r)
# 	for i in range(r):
# 		a = a*(n-i)%mod
# 		b = b*(i+1)%mod
# 	return a*pow(b,mod-2,mod)%mod

if (x+y)%3!=0:
    print(0)
    exit()
else:
    m = int((2*x - y)/3)
    n = int((2*y - x)/3)
    if n>=0 and m>=0:
        print(comb_mod(n+m,n,mod))
        exit()
    else:
        print(0)
        exit()

Submission status: Accepted

Solution code:
p = 10**9 + 7

def pow_mod(p,a,n):
    res = 1
    while n > 0:
        if n % 2 == 1:
            res = (res * a) % p
        n = n // 2
        a = (a*a)%p
    return res


def comb_mod(n,k):
    global fac
    res = fac[n] * pow_mod(p,fac[k],p-2) * pow_mod(p,fac[n-k],p-2) % p
    return res

X,Y = map(int,input().split())
X,Y = max(X,Y),min(X,Y)
n = (X+Y)//3

fac = [1]
foo = 1
for i in range(1,n+1):
    foo = (foo*i)%p
    fac.append(foo)

k = 2*n - X
if (X+Y)%3 != 0 or n < k or k < 0:
    ans = 0
else:
    ans = comb_mod(n,k)

print(ans)

Submission status: Accepted

Solution code:
import sys

def comb(n,r,mod):
	'''
	return nCr
	O(min{n-r, r})
	'''
	a=1
	b=1
	r = min(r,n-r)
	for i in range(r):
		a = a*(n-i)%mod
		b = b*(i+1)%mod
	return a*pow(b,mod-2,mod)%mod



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

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

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

a = (X-d)//3
b = a + d
print(comb(a+b, b, 10**9+7))

Submission status: Accepted

Solution code:
a,b = map(int, input().split())
tried = (a + b)//3
p = 10**9 +7

if a < tried or b < tried or (a+b)%3 != 0:
    print(0)
    quit()
one = int((2 * a -  b)/3)
n = tried
r = min(one, tried-one)
n_fac = 1
r_fac = 1
n_r_fac = 1

for i in range(2,n+1):
    n_fac *= i
    n_fac %= p
for i in range(2,r+1):
    r_fac *= i
    r_fac %= p
for i in range(2,n-r+1):
    n_r_fac *= i
    n_r_fac %= p
r_fac_inverse = pow(r_fac, p-2, p)
n_r_fac_inverse = pow(n_r_fac, p-2, p)

print((n_fac * r_fac_inverse * n_r_fac_inverse)%p)

Submission status: Accepted

Solution code:
from collections import defaultdict


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

    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    for i in range(2, int(n ** 0.5) + 2):
        if primes[i]:
            for j in range(i * 2, n + 1, i):
                primes[j] = False
    primes = [i for i, b in enumerate(primes) if b]

    factors1 = defaultdict(lambda: 0)
    for p in primes:
        num = n
        q = p
        while q <= num:
            factors1[p] += num // q
            q *= p

    factors2 = defaultdict(lambda: 0)
    for p in primes:
        num = r
        q = p
        while q <= num:
            factors2[p] += num // q
            q *= p

    factors3 = defaultdict(lambda: 0)
    for p in primes:
        num = n - r
        q = p
        while q <= num:
            factors2[p] += num // q
            q *= p

    value = 1
    for p in factors1:
        value *= p ** (factors1[p] - (factors2[p] + factors3[p]))

    return value


X, Y = map(int, input().split())
if (2 * Y - X) % 3 != 0 or (2 * X - Y) % 3 != 0:
    print(0)
else:
    a = (2 * X - Y) // 3
    b = (2 * Y - X) // 3
    n = a + b
    print(nCr(n, a) % (10 ** 9 + 7))

Submission status: Accepted

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

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

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

if a < b:
    a, b = b, a

for i in range(a+b, a, -1):
    ans = ans*i
    ans %= MOD

for i in range(1, b+1):
    div = div*i
    div %= MOD

ans *= pow(div, MOD-2, MOD)
print(ans % MOD)

Submission status: Accepted

Solution code:
import sys

# import numpy as np
import math
from fractions import gcd
from collections import deque
import bisect

sys.setrecursionlimit(1000000)


def factorial(n):
    w = 10**9 + 7
    table = [1]*(n+1)
    for i in range(1, n+1):
        table[i] = table[i-1]*i % w
    return table


def modinv(a, m):
    b = m
    u = 1
    v = 0

    while b > 0:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u


def moddiv(x, y, m=10**9+7):
    y_inv = modinv(y, m)
    return x * y_inv % m


def perm(N1, N2):
    table = factorial(N1+N2)
    s = table[N1+N2]
    a = table[N1]
    b = table[N2]
    return moddiv(moddiv(s, a), b)


def main():
    # map(int, input().split())
    # l = list(map(int, input().split()))

    x, y = map(int, input().split())
    diff = abs(x-y)

    if diff == 0:
        if x % 3 != 0:
            print(0)
            return
        cnt = x // 3
        ret = perm(cnt, cnt)
    else:
        if (min(x, y)-diff) % 3 != 0 or min(x, y) - diff < 0:
            print(0)
            return
        cnt = (min(x, y) - diff) // 3
        ret = perm(cnt, cnt+diff)

    print(ret)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def cnb(n,k,p):
  if k>n:
    return 0
  if k>n-k:
    k=n-k
  c,d=1,1
  for i in range(n-k+1,n+1):
    c = (c*i)%p
  for i in range(1,k+1):
    d = (d*i)%p
  return (c*pow(d,p-2,p))%p

p=10**9+7
ans=0
if X > 2*Y or Y > 2*X:
  pass
elif (X+Y)%3:
  pass
else:
  ans=cnb((X+Y)//3,(2*Y-X)//3,p)

print(ans)

Submission status: Accepted

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

def getComb(a,b,mod):
  if b > a:
    return 0
  if a - b > b :
    b = a - b
  comb = 1
  for i in range(b+1,a+1):
    comb = (comb * i) % mod
  d = 1
  for i in range(1,a-b+1):
    d = (d * i) % mod
  comb *= pow(d,mod-2,mod)
  return comb % mod

if x > 2*y or y > 2*x:
  print(0)
  exit()
if (x+y)%3 != 0:
  print(0)
  exit()
times = (x+y)//3
tmp = abs(x-y)
xtimes = (times - tmp) //2
ans = getComb(times,xtimes,mod)
print(ans)

Submission status: Accepted

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

#nCrのmodを求める
def nCrmod(n,r,mod):
	if r<0 or r>n:
		ans=0
	else:
		if r>n-r:
			r=n-r
		kaijo=[1] #階乗リスト作成
		for i in range(1,n+1):
			kaijo.append(kaijo[-1]*i%mod) #これで、kaijo[i]≡i!となる。
		gyakugen=[pow(kaijo[n-r],mod-2,mod)] #逆限リスト作成
		for i in reversed(range(1,n-r+1)):
			gyakugen.append(gyakugen[-1]*i%mod) #これで、gyakugen[i]=n-r-iの逆元 となる。
		ans=kaijo[n]*gyakugen[0]*gyakugen[n-2*r]%mod
	return(ans)


if ((x%3)+(y%3))%3!=0:
	print(0)
else:
	n=int((x+y)/3)
	r=y-n
	mod=1000000007
	print(nCrmod(n,r,mod))

Submission status: Accepted

Solution code:
[x,y]=list(map(int,input().split()))
if ((x%3)+(y%3))%3!=0:
	print(0)
else:
	n=int((x+y)/3)
	r=y-n
	if r<0 or r>n:
		print(0)
	else:
		if r>n-r:
			r=n-r
		mod=1000000007
		kaijo=[1]
		for i in range(1,n+1):
			kaijo.append(kaijo[-1]*i%mod) #これで、kaijo[i]=i!となる。
		gyakugen=[pow(kaijo[n-r],mod-2,mod)]
		for i in reversed(range(1,n-r+1)):
			gyakugen.append(gyakugen[-1]*i%mod) #これで、gyakugen[i]=n-r-iの逆元となる
		kotae=kaijo[n]*gyakugen[0]*gyakugen[n-2*r]%mod

		print(kotae)

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

# -*- coding: utf-8 -*-


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret

    def perm(self, n, r):
        """
        nPrの値を返す
        """
        ret = self.f[n] * self.inv[n-r]
        ret %= self.mod
        return ret


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

x = (2*Y-X)/3
y = (2*X-Y)/3

if 0 <= x and x == int(x) and 0 <= y and y == int(y):
    x = int(x)
    y = int(y)
    F = FactMod(x+y+1, 10**9+7)
    ans = F.comb(x+y, x)
else:
    ans = 0
print(ans)

Submission status: Accepted

Solution code:
import sys
import math

mod = 10 ** 9 + 7

X, Y = map(int, input().split())
if ((2 * Y - X) % 3) != 0 or ((2 * X - Y) % 3) != 0:
  print(0)
  sys.exit()

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

# nCk mod p を求める
# n = m + l
# k = m
# p = 10 ** 9 + 7

maximum = 700000

fac = [0] * maximum
finv = [0] * maximum
inv = [0] * maximum

fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, maximum):
  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, k):
  if n < k:
    return 0
  if n < 0 or k < 0:
    return 0
  return fac[n] * (finv[k] * finv[n - k] % mod) % mod

print(com(m + l, m))
# print(com(100, 1))

Submission status: Accepted

Solution code:
MOD = 1000000007
MAX = 10**6  # max n

fac = [0 for _ in range(MAX)]  # = n! (mod MOD)
finv = [0 for _ in range(MAX)]  # = 1/r! (mod MOD)
inv = [0 for _ in range(MAX)]  # = 1/r (mod MOD)


# init
def COMinit():
    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


# nCk, n < [0, MAX), k < [0, n]
def COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

def main():
    # input
    x, y = map(int, input().split())
    if (x+y)%3 == 0:
        num = (x+y)//3
        for i in range(num+1):
            if i + 2*(num-i) == x and 2*i + (num-i) == y:
                break
        else:
            print(0)
            return
    else:
        print(0)
        return

    # calc
    COMinit()
    print(COM(num, i))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 1000000007
MAX = 10**6  # max n

fac = [0 for _ in range(MAX)]  # = n! (mod MOD)
finv = [0 for _ in range(MAX)]  # = 1/r! (mod MOD)
inv = [0 for _ in range(MAX)]  # = 1/r (mod MOD)


# init
def COMinit():
    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


# nCk, n < [0, MAX), k < [0, n]
def COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

def main():
    # input
    x, y = map(int, input().split())
    if (x+y)%3 == 0:
        num = (x+y)//3
        for i in range(num+1):
            if x==2*y:
                move = i
                break
            x-=1
            y-=2
        else:
            print(0)
            return
    else:
        print(0)
        return

    # calc
    COMinit()
    print(COM(num, move))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

x,y = map(int, input().split())
# (i,j)->(i+1,j+2) continues a times.
# (i,j)->(i+2,j+1) continues b times.
temp = 2*x-y

a = -1
b = -1
if temp%3==0 and temp>=0:
  b = temp//3
  if x-2*b>=0:
    a = x-2*b

if a==-1 or b==-1:
  print(0)
else:
  #このままではansは非常に大きい数になりメモリ使用量が大きくなる。
  #よって、メモリ使用量削減のために"逆元とフェルマーの小定理"を活用する。
  A = 1
  B = 1
  mod = 10**9+7
  for i in range(min(a,b)):
    A *= a+b-i
    A %= mod
    B *= i+1
    B %= mod
  print(A*pow(B,mod-2,mod)%mod)

Submission status: Accepted

Solution code:
from itertools import permutations, combinations,combinations_with_replacement,product

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

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

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

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

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

print(int(combination(m + n, n)) % MOD)

Submission status: Accepted

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

MOD = 1000000007


def combination(n, r):
    r = min(r, n - r)

    num = 1
    den = 1

    for i in range(1, r + 1):
        num = num * (n + 1 - i) % MOD
        den = den * i % MOD

    return num * pow(den, MOD - 2, MOD) % MOD


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

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

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

print(int(combination(m + n, n)) % MOD)

Submission status: Accepted

Solution code:
X,Y=map(int,input().split())
mod=10**9+7
if (X+Y)%3!=0:
    print(0);exit()
if X*2<Y or Y*2<X:
    print(0);exit()
t=(X+Y)//3
f=[1]
for i in range(1,t+100):
    f.append(f[-1]*i%mod)
def comb(a,b,m):
    return f[a]*pow(f[b],m-2,m)*pow(f[a-b],m-2,m)%m
print(comb(t,X-t,mod))

Submission status: Accepted

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

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

n_right = (-X + 2 * Y) / 3
n_up = (2 * X - Y) / 3
if n_right < 0 or n_up < 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, g2, inverse = [1, 1], [1, 1], [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)

n_right, n_up = int(n_right), int(n_up)
print(cmb(n_right + n_up, min((n_right, n_up)), mod))

Submission status: Accepted

Solution code:
X,Y=map(int,input().split())
A,B=1,1
mod=10**9+7
if (X+Y)%3 ==0:
    x=(2*Y-X)//3
    y=(2*X-Y)//3
    if min(x,y) >= 0:
      for i in range(min(x,y)):
        A*=(x+y-i)
        A%=mod
        B*=(i+1)
        B%=mod
      print(A*pow(B,mod-2,mod)%mod)
    else:
      print(0)
else:
  print(0)

Submission status: Accepted

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

def getComb(a,b,mod):
  if b > a:
    return 0
  if a - b > b :
    b = a - b
  comb = 1
  for i in range(b+1,a+1):
    comb = (comb * i) % mod
  d = 1
  for i in range(1,a-b+1):
    d = (d * i) % mod
  comb *= pow(d,mod-2,mod)
  return comb % mod

if x > 2*y or y > 2*x:
  print(0)
  exit()
if (x+y)%3 != 0:
  print(0)
  exit()
times = (x+y)//3
tmp = abs(x-y)
xtimes = (times - tmp) //2
ans = getComb(times,xtimes,mod)
print(ans)

Submission status: Accepted

Solution code:
import sys


def alg_combination_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
        molecule = 1
        for i in range(1, r + 1):
            molecule = (molecule * i) % mod
        return denominator * pow(molecule, mod - 2, mod) % mod


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    x, y = list(map(int, readline().split()))
    if (x + y) % 3 != 0 or x <0 or y < 0:
        print(0)
    else:
        c = (x + y) // 3
        for i in range(c+1):
            xv = i * 1 + (c - i) * 2
            yv = i * 2 + (c - i) * 1
            if xv == x and yv == y:
                print(alg_combination_mod(c, i, mod))
                exit()
        print(0)


if __name__ == '__main__':
    solve()