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:
#!/usr/bin/env python
import sys
from math import modf

class Bigint:
    def __init__(self,n,mod=10**9+7):
        self.n = n % mod
        self.mod = mod
        return
    #
    def __str__(self):
        return str(self.n)
    #
    def __add__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        return Bigint(self.n+other.n,self.mod)
    #
    def __iadd__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        self.n = (self.n + other.n) % self.mod
        return self
    #
    def __sub__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        return Bigint(self.n-other.n,self.mod)
    #
    def __isub__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        self.n = (self.n - other.n) % self.mod
    #
    def __mul__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        return Bigint(self.n*other.n,self.mod)
    #
    def __imul__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        self.n = ( self.n * other.n ) % self.mod
        return self
    #
    def __pow__(self,other):
        assert type(other)==int, "power should be integer"
        #
        if other<0: return self ** ( other % ( self.mod-1 ) )
        ret = Bigint(1,self.mod)
        now = Bigint(self.n,self.mod)
        while other>0:
            if other%2==0: pass
            else: ret *= now
            other//=2
            now*=now
        return ret
    #
    def __truediv__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        return self * ( other ** (other.mod-2) )
    #
    def __itruediv__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        self*= ( other ** (other.mod-2) )
        return self


def _ia(): return [ int(x) for x in sys.stdin.readline().strip().split() ]

def main():
    x,y = _ia()

    b = (2*x - y)/3
    if b.is_integer():
        b = int("{:.0f}".format(b))
        if b<0: return 0
    else:
        return 0

    a = x - 2*b
    if a<0: return 0
    n = a + b
    m = min(a,b)
    ans = Bigint(1)
    for i in range(m,0,-1):
        ans *= Bigint(n)
        ans /= Bigint(i)
        n -= 1
    #
    return ans
#
if __name__=="__main__":
    print(main())

Submission status: Accepted

Solution code:
import math
import sys


sys.setrecursionlimit(1000000)

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

# いけない
if (X + Y) % 3 != 0:
    print(0)
    exit()
if 2*Y < X:
    print(0)
    exit()
if Y > 2*X:
    print(0)
    exit()

# 何段目
dan = (X + Y) // 3

# 端から
x = X + Y
y = 0
while True:
    x -= 1
    y += 1
    if x - 2*y == 0:
        break


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


dic = {}


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(comb(dan, x - X) % 1000000007)
print(cmb(dan, x - X, mod))

Submission status: Accepted

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

from operator import mul
from functools import reduce

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] #逆元テーブル

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

else:
    a = (x + y)//3
    b = x-a

    if x-a <0 or y-a <0:
        ans = 0
    else:
        mod = 10**9+7 #出力の制限
        N = a+b
        g1 = [1, 1] # 元テーブル
        g2 = [1, 1] #逆元テーブル
        inverse = [0, 1] #逆元テーブル計算用テーブル

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

        ans = cmb(a, b, mod)

print(int(ans))

Submission status: Accepted

Solution code:
mod=10**9+7

def framod(n, mod, a=1):
  for i in range(1,n+1):
    a=a * i % mod
  return a
  
def power(n, r, mod):
  if r == 0: return 1
  if r%2 == 0:
    return power(n*n % mod, r//2, mod) % mod
  if r%2 == 1:
    return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
  a=framod(n, mod)
  b=framod(k, mod)
  c=framod(n-k, mod)
  return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod
  
X, Y=map(int, input().split())
a=round(-X/3+2*Y/3, 6)
b=round(2*X/3-Y/3, 6)
if not (a.is_integer() and b.is_integer() and a>=0 and b>=0):
  print(0)
else:
  print(comb(int(a+b), int(a), mod))

Submission status: Accepted

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

if a3%3!=0 or b3%3!=0:
  print(0)
else:
  a=a3//3
  b=b3//3
  if a>b:
    a,b=b,a
  
  N=a+b

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

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

  ans = cmb(N,a,MOD)
  print(ans%MOD)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

X, Y = MAP()

x, y = 0, 0
while (X!=0 or Y!=0):
	if X * 2 == Y:
		x += X
		break

	elif Y * 2 == X:
		y += Y
		break

	elif X >= 3 and Y >= 3:
		x += 1
		y += 1
		X -= 3
		Y -= 3
	else:
		if X-1 == 0 and Y-2==0:
			y += 1
			break
		elif X-2 == 0 and Y-4==0:
			y += 2
			break

		elif X-2==0 and Y-1==0:
			x += 1
			break
		elif X-4==0 and Y-2==0:
			x += 2
			break
		else:
			print(0)
			sys.exit()

H = 10**6//2
W = 10**6//2
factorial = [1]
for i in range(1, H+W):
	factorial.append(factorial[i-1] * i % mod)


def power(x, y):
	if y == 0:
		return 1
	elif y == 1:
		return x % mod
	elif y % 2 == 0:
		return power(x, int(y/2)) ** 2 % mod
	else:
		return power(x, int((y-1)/2)) ** 2 * x % mod
def C(n, r):
	return (((factorial[n] * x_inv[r]) % mod) * x_inv[n-r]) % mod

x_inv = [0] * (H+W)
x_inv[-1] = power(factorial[-1], mod-2)
for i in range(H+W-2, -1, -1):
	x_inv[i] = x_inv[i+1] * (i+1) % mod

# print(x, y)
if x == 0 or y == 0:
	print(1)
else:
	print(C(x+y, y))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
import time

t1 = time.time()

x,y = map(int,input().split())
kyori = x+y
if kyori % 3 !=0:
    print(0)
    exit()
    
mod = 10**9+7

nagasa = kyori // 3
dif = x - y

n_x = (nagasa + dif) // 2
n_y = nagasa - n_x

#print(nagasa,n_x,n_y)

if x != n_x * 2 + n_y * 1 or y != n_x * 1+ n_y*2:
    print(0)
    exit()

if n_x < 0 or n_y < 0:
    print(0)
    exit()
#H, W, A, B = map(int, raw_input().split())

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

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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


a = kj(nagasa,n_x,n_y,mod)
print(a)

Submission status: Accepted

Solution code:
X,Y=map(int,input().split())
N=10**9+7
def kaizyou(n):
    l=[1]
    for i in range(1,n+1):
        ll=(l[i-1]*i)%N
        l.append(ll)
    return l
def modpow(a,n,p):#a^n mod p ,O(log n)
    res=1
    while n>0:
        if n&1:#１とのビット論理積が１、つまり奇数
            res=res*a%p
        a=a*a%p
        n>>=1
        #ビットの右シフト_2進数表記のnを小数点を固定して右に１桁ずらす_１桁小さくなる
    return res
if (2*X-Y)%3==0 and (2*Y-X)%3==0 and 2*X-Y>=0 and 2*Y-X>=0:
    nx=int((2*X-Y)/3)
    ny=int((2*Y-X)/3)
    l=kaizyou(nx+ny)
    nxdv=modpow(l[nx],N-2,N)
    nydv=modpow(l[ny],N-2,N)
    ans=l[-1]*nxdv%N
    ans=ans*nydv%N
    print(ans)
else:
    print(0)

Submission status: Accepted

Solution code:
def mod_pow(a, x, p):
    res = 1
    while x > 0:
        if x % 2 != 0:
            res = (res * a) % p
        a = (a * a) % p
        x //= 2
    return res


def mod_inv(a, p):
    return mod_pow(a, p-2, p)


def mod_binomial(n, k, p):
    numerator = 1
    for i in range(k):
        numerator = (numerator * (n-i)) % p

    denominator = 1
    for i in range(1, k+1):
        denominator = (denominator * i) % p

    return (numerator * mod_inv(denominator, p)) % p


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

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

if a >= 0 and b >= 0 and a == int(a) and b == int(b):
    a = int(a)
    b = int(b)

    print(mod_binomial(a+b, a, 10**9+7))
else:
    print(0)

Submission status: Accepted

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

mod = 10**9+7
def frac(limit):
    frac = [1]*limit
    for i in range(2,limit):
        frac[i] = i * frac[i-1]%mod
    fraci = [None]*limit
    fraci[-1] = pow(frac[-1], mod -2, mod)
    for i in range(-2, -limit-1, -1):
        fraci[i] = fraci[i+1] * (limit + i + 1) % mod
    return frac, fraci
frac, fraci = frac(1341398)
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[b]*fraci[a-b]%mod

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

ans = 0

ta = 2*Y - X
if ta%3 == 0:
    a = ta//3
    db = X - a
    if db % 2 == 0:
        b = db//2
        if 0 <= a and 0 <= b:
            ans = comb(a+b, a)

print(ans)

Submission status: Accepted

Solution code:
mod = 10**9 + 7


def pwr(p, q):
    if q == 1:
        return p%mod
    elif q % 2 == 0:
        return (pwr(p, q//2)%mod)**2%mod
    else:
        return (pwr(p, q//2)%mod)**2*p%mod

x, y = map(int,input().split())
if (2*x-y)%3 != 0 or (2*y-x)%3 != 0:
    print(0)
else:
    n = (2*x-y)//3
    m = (2*y-x)//3
    if m == 0 or n == 0:
        print(1)
    elif m < 0 or n < 0:
        print(0)
    else:
        s1 = 1
        s2 = 1
        for i in range(m+1, n+m+1):
            s1 *= i
            s1 %= mod
        for i in range(n):
            s2 *= (i+1)
            s2 %= mod

        print(s1*pwr(s2, mod-2)%mod)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

def calc(x, y):
	a = 2 * y - x
	
	if a < 0 or a % 3 != 0:
		return 0
	
	a //= 3
	b   = y - 2 * a
	
	if b < 0:
		return 0
		
	for i in range( 2, a + b + 1 ):
		g1.append( ( g1[-1] * i ) % mod )
		inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
		g2.append( (g2[-1] * inverse[-1]) % mod )
		
	
		
	return cmb(a + b, a, mod)

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

print(calc(x, y) % mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans=count=0


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)

#!/usr/bin/env python3
import sys, math
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans=count=0
mod=10**9+7
x,y=map(int,input().split())
a=b=0
n=10**6
while x>0 and y>0:
    if x>=y:
        x-=2
        y-=1
        a+=1
    else:
        x-=1
        y-=2
        b+=1
    # print(x,y,a,b)
if not (x==0 and y==0):
    print(0)
    exit()
a%=mod
b%=mod
# print(math.factorial(a+b)%mod//math.factorial(a)%mod//math.factorial(b)%mod)
print(cmb(a+b, b, mod))

Submission status: Accepted

Solution code:
import math
import itertools

def read():
    X, Y = list(map(int, input().strip().split()))
    return X, Y

def init_mod_combinations(MAX=500000, MOD=1000000007):
    fac = [0 for _ in range(MAX)]
    finv = [0 for _ in range(MAX)]
    inv = [0 for _ in range(MAX)]
    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
    return fac, finv, inv

def mod_combinations(n, k, MOD=1000000007):
    fac, finv, inv = init_mod_combinations(MAX=n+1, MOD=MOD)
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD


def solve(X, Y):
    # X = 2p + q, Y = p + 2q
    p = (2 * X - Y) // 3
    q = (2 * Y - X) // 3
    if 2*p+q!=X or p+2*q!=Y:
        # 到達不可能
        return 0
    # p+q 回の移動で到達可能
    # 移動パターンの総数は(p+q)Cp
    return mod_combinations(p+q, p)

if __name__ == '__main__':
    inputs = read()
    output = solve(*inputs)
    print("%d" % output)

Submission status: Accepted

Solution code:
x, y = map(int, input().split())
U = 2*10**6
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
  fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U],MOD-2,MOD)
 
for i in range(U,0,-1):
  fact_inv[i-1] = (fact_inv[i]*i)%MOD
 
def comb(n,k):
  if k < 0 or k > n:
    return 0
  z = fact[n]
  z *= fact_inv[k]
  z %= MOD
  z *= fact_inv[n-k]
  z %= MOD
  return z

if (x+y)%3 != 0:
  print(0)
else:
  m = (x+y)//3
  l = x-m
  ans = comb(m, l)
  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+50
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)
else:
  m = (X+Y)//3
  a = (2*Y-X)//3
  print(cmb(m,a, mod))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod
def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

x,y=map(int,input().split())
y,x=min(x,y),max(x,y)
if x>2*y or (x+y)%3!=0:
    #print(1)
    print(0)
else:
    print(comb((x+y)//3, min(x,y)-(x+y)//3,10**9+7))

Submission status: Accepted

Solution code:
import math
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/2>y:
 print(0)
else:
 if y/2>x:
  print(0)
 else:
  if (x+y)%3==0:
   a=(2*x-y)/3
   b=(2*y-x)/3
   c = cmb(int(a+b),int(a),mod)
   print(int(c))
  else:
   print(0)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Nov 16 19:44:49 2019
ABC145D
@author: maezawa
"""

#MAX = 5*10**5+1
MAX = 10**6+1
MOD = 10**9+7

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

# テーブルを作る前処理
fac[0] = 1
fac[1] = 1
finv[0] = 1
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

# 二項係数計算
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


#n, r = list(map(int, input().split()))
#ans = COM(n, r)
#print(ans)

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

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

Submission status: Accepted

Solution code:
def prepare(n, MOD):
 
    # n! の計算
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f
     
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return fn, invs
X,Y = map(int,input().split())
A = X * 2 - Y
B = Y * 2 - X

if A < 0 or A % 3 != 0 or B % 3 != 0 or B < 0:
    print(0)
else:
    AB = (A + B) // 3
    M = max(A,B) // 3
    N,r = prepare(AB,10**9+7)
    print((N * r[M]*r[AB-M]) % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
import sys
MOD = 10**9+7

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])
            result %= MOD
    return result % MOD

X,Y = map(int,input().split())
if (2*X-Y) % 3 != 0 or (2*Y-X) % 3 != 0:
    print(0)
    sys.exit()
n = (2*X-Y)//3
m = (2*Y-X)//3
k = n + m
if n < 0 or m < 0:
    print(0)
    sys.exit()
if n == 0 and m == 0:
    print(0)
    sys.exit()

print(cmb(k,n) % MOD)

Submission status: Accepted

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

if (X+Y)%3!=0 or Y<X//2 or Y>X*2:
    print(0)
    exit()

n = (X+Y)//3
k = Y-n  # k = 0...n

mod = 10**9+7

def modpow(n,p,mod):
    retval = 1
    i=0
    while p>>i:
        if (p>>i)&1 : retval = retval*n%mod
        n=n*n%mod
        i+=1
        
    return retval

modfacts = [1]
pre = 1
for i in range(1,n+1):
    pre = pre*i%mod
    modfacts.append(pre)

ans = modfacts[n] * modpow(modfacts[n-k], mod-2, mod) * modpow(modfacts[k], mod-2, mod)
print(ans%mod)

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
if y > 2*x:
   print(0)
   exit()
elif (2*x-y) % 3 != 0:
    print(0)
    exit()
else:
   h = x - (2*x-y) // 3 * 2
   v = (2*x-y) // 3
   #print(h,v)
# calcurate h+vCv
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 = cmb((h+v),h,mod)
print(a)

Submission status: Accepted

Solution code:
X, Y = [int(_) for _ in input().split()]
mod = 10**9 + 7

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

if (2 * Y - X) % 3 == (2 * X - Y) % 3 == 0:
    a = (2 * Y - X) // 3
    b = (2 * X - Y) // 3
    if a < 0 or b < 0:
        print(0)
        exit()
    f = [1] * (a + b + 1)
    for i in range(1, a + b + 1):
        f[i] = i * f[i - 1] % mod
    fi = [1] * (a + b + 1)
    fi[-1] = pow(f[-1], mod - 2, mod)
    for i in range(a + b - 1, 1, -1):
        fi[i] = (i + 1) * fi[i + 1] % mod

    def comb(x, y):
        return (f[x] * fi[y] * fi[x - y]) % mod

    print(comb(a + b, b))
    exit()
print(0)

Submission status: Accepted

Solution code:
def ncr(n, r):
    r = min(r, n - r)
    if r == 0: return 1;
    if r == 1: return n;
    numerator = [n - r + i + 1 for i in range(r)]
    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
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= numerator[k]
            if result >10**9+7:
                result = result%(10**9+7)
    return result
x,y=map(int,input().split())
if (x+y)%3!=0 or 2*x<y or 2*y<x:
    print(0)
else:
    a=(2*y-x)//3
    b=(2*x-y)//3
    print(int(ncr(a+b,a)%(10**9+7)))

Submission status: Accepted

Solution code:

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]]


def mod_inv(a, m):
    x = extgcd(a, m)[0]
    return (m+x % m) % m


def mod_e(n, p):
    res = 0
    while n >= p:
        res += n//p
        n = n//p
    return res


def mod_fact(n, p):
    if n == 0:
        return 1

    res = mod_fact(n//p, p)

    if n//p % 2 != 0:
        return res*(p-fact[n % p]) % p
    return res*fact[n % p] % p


# nCk mod p
def mod_comb(n, k, p):
    if n < 0 or k < 0 or n < k:
        return 0
    e1 = mod_e(n, p)
    e2 = mod_e(k, p)
    e3 = mod_e(n-k, p)
    #pで割り切れる場合
    if e1 > e2 + e3:
        return 0

    #pで割り切れない場合
    a1 = mod_fact(n, p)
    a2 = mod_fact(k, p)
    a3 = mod_fact(n-k, p)
    return a1 * mod_inv(a2*a3 % p, p) % p

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

# print(x, y)

if (2 * Y - X) % 3 != 0 or (2 * X - Y) % 3 != 0:
    print(0)
    exit()
else:
    x = int(x)
    y = int(y)

if x < 0 or y < 0:
    print(0)
    exit()
# print(x,y)
if x < y:
    x, y = y, x

#pは素数とする
p = 10**9+7

#fact[i] : i! modp (0<= i <p) O(p)
#上だとO(p)なのでnまでにして O(n)にする
fact = [1]
k = 1
for i in range(1, 10**6+100):
    k = k*i % p
    fact.append(k)

#10000C4000 mod 10**9+7
print(mod_comb(x + y, y, p))

Submission status: Accepted

Solution code:
import sys

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

# 直交座標に直す
if X > 2 * Y or Y > 2 * X or \
        (2 * X - Y) % 3 != 0 or (2 * Y - X) % 3 != 0:
    print(0)
    sys.exit()
x, y = (2 * X - Y) // 3, (2 * Y - X) // 3


def comb_inv(n, k, mod):
    f = [1 for _ in range(n + 1)]
    inv = [1 for _ in range(n + 1)]
    finv = [1 for _ in range(n + 1)]

    for i in range(2, n + 1):
        f[i] = f[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod
    return f[n] * (finv[k] * finv[n - k] % mod) % mod


print(comb_inv(x + y, x, 10 ** 9 + 7))

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())
mod = 10**9 + 7
a = abs(x-y)
b = min(x,y) - a
if b%3 != 0:
    print(0)
    exit()
    
print(int(cmb(a+b//3+b//3, b//3, mod)))

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

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

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

def calc(x, y):
	a = 2 * y - x
	
	if a < 0 or a % 3 != 0:
		return 0
	
	a //= 3
	b   = y - 2 * a
	
	if b < 0:
		return 0
		
	for i in range( 2, a + b + 1 ):
		g1.append( ( g1[-1] * i ) % mod )
		inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
		g2.append( (g2[-1] * inverse[-1]) % mod )
		
	return cmb(a + b, a, mod)

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

print(calc(x, y))

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

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

x,y = inpl()
x,y = max(x,y),min(x,y)
if (x+y)%3 or y*2 < x:
    print(0)
    quit()
n = (x+y)//3 + 1
k = x-n+2


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

a = cmd(n-1,k-1)%mod
print(a)

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

    return g1[n] * g2[r] * g2[n-r] % mod

if (x+y)%3 != 0:
    print(0)
else:
    n = (x+y)//3
    r = 2*n - x
    print(cmb(n, r, mod))

Submission status: Accepted

Solution code:
MOD = 10**9+7


def main():
    X, Y = map(int, input().split())
    if X > Y:
        tmp = X
        X = Y
        Y = tmp
    if (X - (Y-X)) % 3 != 0:
        print("0")
        exit()
    Xleft = (X-(Y-X)) // 3
    Yleft = (X-(Y-X)) // 3 + (Y-X)
    Xkaijou = 1

    for i in range(1, Xleft+1):
        Xkaijou = (Xkaijou*i)%MOD
    Ykaijou = Xkaijou
    for i in range(Xleft+1, Yleft+1):
        Ykaijou = (Ykaijou*i)%MOD
    zenbu = Ykaijou
    p = 0
    for i in range(Yleft+1, Xleft+Yleft+1):
        zenbu = (zenbu*i) % MOD
        p += 1
    ans = (zenbu * (pow(Xkaijou, MOD-2, MOD) * pow(Ykaijou, MOD-2, MOD) % MOD) % MOD)
    print(int(ans))
    # print(Xkaijou, Ykaijou, zenbu)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

x, y = map(int, input().split())
if ((2*x - y) % 3 != 0) or ((2*y - x)% 3 != 0):
    print(0)
else:
    mod = 10**9 + 7
    s = (2*x - y) // 3
    t = (2*y - x) // 3
    val = cmb(s+t, s, mod)
    print(val)

Submission status: Accepted

Solution code:
import functools, sys

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

mod = 10 ** 9 + 7

def modpow(x, y):
    z = 1
    while y > 0:
        if y % 2 == 0:
            x = (x * x) % mod
            y //= 2
        else:
            z = (z * x) % mod
            y -= 1
    return z

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

def c(n, r):
    if n == r or r == 0:
        return 1

    fct = [None] * (n + 1)
    fct[0] = 1
    for i in range(1, n + 1):
        fct[i] = fct[i - 1] * i % mod
    return fct[n] * (modinv(fct[n - r]) * modinv(fct[r]) % mod) % mod

def f():
    if 2 * y - x < 0 or (2 * y - x) % 3 != 0:
        return 0
    a = (2 * y - x) // 3
    b = y - 2 * a
    if b < 0:
        return 0
    
    return c(a + b, a)

print(f())

Submission status: Accepted

Solution code:
i = input().split(" ")
x = int(i[0])
y = int(i[1])

xx = 2 * x + (-1) * y
yy = (-1) * x + 2 * y

if (xx % 3) != 0 or (yy % 3) != 0:
  res = 0
else:
  xx = xx / 3
  yy = yy / 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 )

  res = cmb(int(xx+yy),int(yy),mod)
  
print(int(res))

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
if x > y*2 or y > x*2 or (x+y)%3 != 0:
  print(0)
  exit()
n = (x+y)//3
r = min(x-n,2*n-x)

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

Submission status: Accepted

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

# (1, 2) * a + (2, 1) * b = (x, y)
#
# a + 2 * b = x
# 2 * a + b = y
# b = y - 2 * a
# a = x - 2 * b
# b = y - 2 * (x - 2 * b)
#   = y - 2 * x + 4 * b
# 3 * b = - y + 2 * x

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

def fact(n):
    ans = n
    for i in range(1, n):
        ans *= i
        if ans >= M:
            ans %= M
    return ans

def pm(value, n):
    if n == 0:
        return 1
    if n % 2:
        return pm(value, n - 1) * value % M
    else:
        return pm(value, n // 2) ** 2 % M

# A * B ^ (M-2)
print(fact(a + b) * pm(fact(a) * fact(b) % M, M - 2) % M)