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:
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
X,Y=[int(x) for x in input().split()]
a = X%3
b = Y%3
mod = 10**9+7
if a==b==0:
  if X==Y:
    c = X//3
    #print(c)
    N = c*2
    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(c*2,c,mod))
  else:
    if X>Y:
      l = X-Y
      d = (Y-l)//3
      N = l+d*2
      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(l+d*2,d,mod))
    else:
      l = Y-X
      d = (X-l)//3
      N = l+d*2
      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(l+d*2,d,mod))
elif a==2 and b==1:
  x =X-2
  y =Y-1
  if x==y:
    c = x//3
    N = c*2+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 )
    print(cmb(c*2+1,c,mod))
  else:
    if x>y:
      l = x-y
      d = (y-l)//3
      N = l+d*2+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 )
      print(cmb(l+d*2+1,d,mod))
    else:
      l = y-x
      d = (x-l)//3
      N = l+d*2+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 )
      print(cmb(l+d*2+1,d+1,mod))
elif a==1 and b==2:
  x =X-1
  y =Y-2
  if x==y:
    c = x//3
    N = c*2+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 )
    print(cmb(c*2+1,c,mod))
  else:
    if x>y:
      l = x-y
      d = (y-l)//3
      N = l+d*2+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 )
      print(cmb(l+d*2+1,d+1,mod))
    else:
      l = y-x
      d = (x-l)//3
      N = l+d*2+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 )
      print(cmb(l+d*2+1,d,mod))
else:
  print(0)

Submission status: Accepted

Solution code:
import itertools
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:
  Answer = 0
else:
  m = int(X-(X+Y)/3)
  n = int(Y-(X+Y)/3)
  Answer = cmb(m+n,n,mod)
  
print(Answer)

Submission status: Accepted

Solution code:
import sys
import math
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
a,b=map(int,input().split())
c=int((2*a-b)/3)
if (a+b)%3!=0:
    print('0')
    sys.exit()
if c<0 or (a+b)//3<c:
    print('0')
    sys.exit()
print(cmb((a+b)//3,c)%1000000007)

Submission status: Accepted

Solution code:
from math import factorial
M = 10**9 + 7
X, Y = map(int, input().split())
cnt = 0
while True:
    # print(X, Y)
    if X == 0 or Y == 0 or X / Y == 2:
        break
    cnt += 1
    X -= 1
    Y -= 2
if X == 0 and Y == 0:
    print(1)
elif X == 0 or Y == 0:
    print(0)
else:
    cnt2 = min(X, Y)
    maxcnt = max(cnt, cnt2)
    mincnt = min(cnt, cnt2)
    ans = 1
    for i in range(maxcnt+1, cnt+cnt2+1):
        ans = (ans * i) % M
    N = mincnt
    inv_t = [0]+[1]
    for i in range(2,mincnt+1):
        inv_t += [inv_t[M % i] * (M - int(M / i)) % M]
        ans = (ans * inv_t[i]) % M
    print(ans)

Submission status: Accepted

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

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)

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

def Fac(n, k1, k2):
    t = 1
    kmax = max(k1, k2)
    kmin = min(k1, k2)
    for i in range(1, kmin+1):
        t = t * (kmax+i) * modinv(i, 10**9+7) 
        t = t % (10**9 + 7)
    if n > kmax+kmin:
        for j in range(kmax+kmin+1, n+1):
            t *= j
            t = t % (10**9 + 7)
    return t

s = min(X, Y) - abs(Y - X)

if min(X, Y) - abs(Y - X) < 0:
    print(0)

else:
    if s % 3 != 0:
        ans = 0
    else:
        a = s//3 * 2
        b = abs(Y - X)
        ans = Fac(a+b, a//2, a//2 + b)
        
    print(ans)

Submission status: Accepted

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


count2=0
mod=1000000007
X,Y=map(int,input().split())
flag=0
count=0
for i in range(min(X,Y)//3):
    if min(X,Y)*2==max(X,Y):
        flag=1
        count2=min(X,Y)
        break
    X-=3
    Y-=3
    count+=1
    #print(X,Y)

if min(X,Y)*2==max(X,Y):
    flag=1

if flag==0:
    print('0')
    exit(0)

print(cmb(count*2+count2,count)%mod)

Submission status: Accepted

Solution code:
def comb(a,b,m):
	if b == 0 or b == a:
		ret = 1
	else:
		ret = 1
		for i in range(a-b+1,a+1):
			ret = (ret * i) % m
		for i in range(1,b+1):
			ret = (ret * pow(i,m-2,m) ) % m
	return ret % m

mod = 10**9+7
x, y = [ int(v) for v in input().split() ]

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

Submission status: Accepted

Solution code:
d = 10**9 + 7

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

def numerator(n, k, p):
    l = 1;
    for j in range(k+1,n+1):
        l = (l*j)%p;
    return l

def denominator(n, k, p):
    l = 1;
    for j in range(2,n-k+1):
        l = (l*j)%p;
    return l


def power(a, k, p):
    if (k == 0):
        return 1
    r = power((a*a)%p,k>>0x01,p);
    if ((k&0x01) == 0x01): #odd number
        r = (r*a)%p;
    return r


def n_choose_K(n, k, p):
    num = numerator(n,k,p)
    den = denominator(n,k,p)
    return (num*power(den,p-2,p))%p
    

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

if n-int(n) != 0 or m-int(m) != 0:
    print(0)
elif n<0 or m<0:
    print(0)
else:
    n = int(n)
    m = int(m)
    ans = n_choose_K(n+m,n,d)
    print(int(ans))

Submission status: Accepted

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

str_list = input().split(' ')
int_list = [int(x) for x in str_list]

X, Y = int_list[0], int_list[1]
if not (X+Y)%3==0:
    print(0)
    exit()


if X==Y:
    large_count = X//3
    small_count = X//3
else:
    large_count = np.abs(X-Y)
    small_count = int( (X+Y-3*large_count)/3/2 )
    large_count += small_count
#print(large_count, small_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 #出力の制限
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(large_count+small_count, small_count, mod)
print(a)

Submission status: Accepted

Solution code:
import math
from scipy.misc import comb

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

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



if (X+Y) % 3 == 1 or (X+Y) % 3 == 2:
  print(0)
else:
  if 2*X < Y or 2*Y < X:
    print(0)
  else:
    if X >= Y:
      #print()
      #print()
      a = cmb(int((X+Y)/3), int((2*Y-X)/3))
      #print(a)
      q, mod = divmod(a, 10**9+7)
      print(mod)
    else:
      a = cmb(int((X+Y)/3), int((2*X-Y)/3))
      #print(a)
      q, mod = divmod(a, 10**9+7)
      print(mod)

Submission status: Accepted

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

P_MOD = 10 ** 9 + 7

bit = []
tmp = P_MOD - 2
for i in range(64):
    if tmp < 1: break
    bit.append(tmp % 2)
    tmp >>= 1
    
def myinv(arg):
    N_bit = len(bit)
    #
    ret = 1
    arg_tmp = arg
    for i in range(N_bit):
        if bit[i] == 1:
            ret = (ret * arg_tmp) % P_MOD
        arg_tmp = (arg_tmp * arg_tmp) % P_MOD
    #
    return ret

if ((2 * X - Y) % 3 > 0) or ((2 * Y - X) % 3 > 0):
    print(0)
else:
    num_a = min((2 * Y - X) // 3, (2 * X - Y) // 3)
    num_b = max((2 * Y - X) // 3, (2 * X - Y) // 3)
    if num_a < 0 or num_b < 0:
        print(0)
    else:
        ans = 1
        for i in range(num_a):
            ans = (ans * (num_b + i + 1)) % P_MOD
        for i in range(num_a):
            ans = (ans * myinv(i + 1)) % P_MOD
        #
        print(ans)

Submission status: Accepted

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

flag=False
if (x+y)%3 == 0:
    k = (x+y)//3
    if abs(x-y) <=k :
        l = abs(x-y)
        if (k-l)%2==0:
            flag=True
            a = (k+l)//2
            #b = (k-l)//2
            c = comb(k,a ,10**9+7)

if flag:
    print(c)
else:
    print(0)

Submission status: Accepted

Solution code:
# 2019-11-16 21:01:15(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
from functools import reduce
import operator as op
# from scipy.misc import comb # float
# import numpy as np 


mod = 10 ** 9 + 7

def comb(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():
    x, y = [int(x) for x in sys.stdin.readline().split()]
    # n(+1, +2), m(+2, +1)
    n, m = (2 * y - x) / 3, (2 * x - y) / 3

    if n != abs(int(n)) or m != abs(int(m)):
        print(0)
        sys.exit()
    else:
        n, m = int(n), int(m)
        ans = comb(n+m, n) % mod
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

a =[]
a = list(map(int,input().split()))
x=a[0]
y=a[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

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:
    k=(x+y)//3
    i=(2*x-y)//3
    a=cmb(k,i,mod)
    print(a)

Submission status: Accepted

Solution code:
import numpy as np
v=np.array(list(map(int, input().split())) )
mod = 10**9 +7
import math
def cmb(n, r,mod):
    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 = (result*int(numerator[k]))%mod

    return result
  
A = np.array([[2,1],[1,2]])
inv_A = np.linalg.inv(A)

k = np.dot(inv_A,v)

if abs(round(k[0])-k[0])<10**(-10) and abs(round(k[1])-k[1])<10**(-10) and k[0]* k[1] >=0:
  print(int(cmb(int(round(k[0]+k[1])),int(round(k[0])),mod)))
else:
  print(0)

Submission status: Accepted

Solution code:
#from math import factorial as f

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

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

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

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


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

if a % 1 or b % 1:
    print(0)
else:
    a = int(a)
    b = int(b)
    n = a + b
    ans = cmb(n, a, mod)
    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
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 = (int(i) for i in input().split())
if((X+Y) % 3 == 0):
    A = (2*Y-X)//3
    B = (2*X-Y)//3
    print(cmb(A+B,A,mod))
else:
    print(0)

Submission status: Accepted

Solution code:
import sys

X, Y = map(int, input().split())
if X > Y:
    X, Y = Y, X

ni1 = 0
ni2 = 0
while Y > X:
    ni1 += 1
    X -= 1
    Y -= 2
if X % 3 != 0:
    print(0)
    sys.exit()
ni1 += X // 3
ni2 += X // 3

MAX = ni1 + ni2
MOD = 10**9 + 7
fac = [0] * (MAX + 1)
finv = [0] * (MAX + 1)
inv = [0] * (MAX + 1)
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD

n = ni1 + ni2
k = ni1
if n < k or n < 0 or k < 0:
    ans = 0
else:
    ans = fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
print(ans)

Submission status: Accepted

Solution code:
x, y = [int(_) for _ in input().split(' ')]

M = int(1e9+7)

def modpow(a, n):
    if n == 0:
        return 1
    elif n == 1:
        return a
    elif n % 2 == 0:
        tmp = modpow(a, n // 2)
        return (tmp * tmp) % M
    else:
        tmp = modpow(a, n // 2)
        return (tmp * tmp * a) % M

def modinv(a):
    return modpow(a, M - 2)

if (x + y) % 3 == 0:
    a, b = (-x + 2 * y) // 3, (2 * x - y) // 3

    if a >= 0 and b >= 0:
        f = [1] * (a + b + 1)
        for i in range(1, a + b + 1):
            f[i] = f[i - 1] * i % M

        answer = (f[a + b] * modinv(f[a]) * modinv(f[b])) % M
        print(answer)
    else:
        print(0)
else:
    print(0)

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())
if (2*y-x)%3==0 and (2*x-y)%3==0 and  (2*y-x)/3>=0 and (2*x-y)/3>=0 :
    a=(2*y-x)//3
    b=(2*x-y)//3
    ans=cmb(a+b,a)
    print(ans%(10**9+7))
else:
    print('0')

Submission status: Accepted

Solution code:
import sys

X, Y = list(map(lambda x: int(x), list(input().split())))

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

a = int((X+Y)/3)
b = 0
while True:
    if a*2 + b == Y:
        break
    elif a == 0:
        print(0)
        sys.exit(0)

    b += 1
    a -= 1

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

r = cmb(a+b,a)%(10**9+7)

print(r)

Submission status: Accepted

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

NNN = (10**6+1)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

import sys
if (x+y)%3:
    print(0)
    sys.exit()
c = (x+y)//3
if x < c or y < c:
    print(0)
    sys.exit()

x,y=x-c,y-c
print(cmb(x+y,x,mod))

Submission status: Accepted

Solution code:
import sys

def comb_mod(n, r, MOD=10**9+7):
    if n < 0 or r < 0 or n < r:
        return 0

    factrial = [1] * (n+1)
    for k in range(1, n+1):
        factrial[k] = (factrial[k-1] * k) % MOD

    fact_inv = [1] * (n+1)
    fact_inv[n] = pow(factrial[n], MOD - 2, MOD)
    for k in range(n-1, -1, -1):
        fact_inv[k] = (fact_inv[k+1] * (k+1)) % MOD

    return (factrial[n] * fact_inv[r] * fact_inv[n-r]) % MOD

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    X, Y = map(int, input().split())

    x1, x2 = 0, 0
    while min(X, Y) > 0:
        if 2*X == Y:
            x1 += X
            n = x1 + x2
            r = min(x1, x2)
            return comb_mod(n, r, MOD)
        
        elif X == 2*Y:
            x2 += Y
            n = x1 + x2
            r = min(x1, x2)
            return comb_mod(n, r, MOD)

        elif X >= Y:
            x2 += 1
            X -= 2
            Y -= 1
        
        else:
            x1 += 1
            X -= 1
            Y -= 2

    return 0

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
import math

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

def pow_mod(a, b, p):
    if b == 0:
        return 1
    elif b % 2 == 0:
        d = pow_mod(a, b//2, p)
        return (d**2) % p
    else:
        return (a*pow_mod(a, b-1, p)) % p


def factorial_mod(n, p):
    tmp = 1
    for i in range(1, n+1):
        tmp *= i
        tmp %= p
    return tmp

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

j = -1
for i in range(X//2 +1):
    x = X - i*2
    y = Y - i
    if y == x*2:
        j = x
        break

if j == -1:
    print(0)
else:
    ans = factorial_mod(i+j, MOD)
    ans *= pow_mod(factorial_mod(i, MOD), MOD-2, MOD)
    ans *= pow_mod(factorial_mod(j, MOD), MOD-2, MOD)
    ans %= MOD
    print(ans)

Submission status: Accepted

Solution code:
import math
import itertools

x,y=map(int, input().split()) 
v=x+y
if v%3!=0:
    print(0)
    exit()

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

v1=(v//3-abs(x-y))//2+abs(x-y)
v2=v//3-v1

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

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

a = cmb(v//3,v1)
a//(math.factorial(v2))

print(a%(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())
sum = 0
if x%2 == 1:
  for k in range((x+1)//2):
    k = 2*k +1
    l = (x-k)//2
    if l+2*k == y:
      sum += cmb(k+l,l,mod)
      sum = sum%mod
  print(sum)
if x%2 == 0:
  for k in range(x//2):
    k = 2*k
    l = (x-k)//2
    if l+2*k == y:
      sum += cmb(k+l,l,mod)
      sum = sum%mod
  print(sum)

Submission status: Accepted

Solution code:
import math ,sys
x,y = map(int,input().split())
if (x+y)%3!=0:
  print(0)
  sys.exit()
n=(x+y)//3
r=y-n
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n]*g2[r] *g2[n-r] % mod

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

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

a = cmb(n,r,mod)

print(a)

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 )


# a = comb(n, r)
x,y=map(int,input().split())
a=(-x+2*y)//3
b=(2*x-y)//3
if a+2*b==x and 2*a+b==y:
  c = cmb(a+b,a,mod)
  print(c)
else:
  print(0)

Submission status: Accepted

Solution code:
import math
from operator import mul
from functools import reduce

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())
if y>2*x:
    print(0)
    exit()
if y<x/2:
    print(0)
    exit()
if (x+y)%3!=0:
    print(0)
    exit()
if (-x+2*y)/3%1!=0:
    print(0)
    exit()
if (-y+2*x)/3%1!=0:
    print(0)
    exit()

x_=int((-x+2*y)/3)
y_=int((2*x-y)/3)

print(cmb(x_+y_,x_)%(10**9+7))

Submission status: Accepted

Solution code:
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
x, y = map(int, input().split())
inf = 10**9+7
if (x+y)%3 > 0:
  print(0)
else:
  n = (x+y)//3
  c = [1 for i in range(n+1)]
  invc = [1 for i in range(n+1)]
  for i in range(1, n+1):
    c[i] = c[i-1]*i % inf
    invc[i] = modinv(c[i], inf)
  cnt=-1
  for i in range(n+1):
    if (i+2*(n-i)==x)&(2*i+(n-i)==y):
      cnt = i
      break
  if cnt < 0:
    ans = 0
  else:
    ans = (c[n] * invc[cnt] * invc[n-cnt]) % inf
  print(ans)

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

if (x + y) % 3 != 0:
    print(0)
else:
    xn = int((x + y) / 6 + (x - y) / 2)
    yn = int((x + y) / 6 + (y - x) / 2)
    # print(xn, yn)
    if xn * yn < 0:
        print(0)
    else:
        n = cmb((xn + yn), xn)
        s = pow(int(n), 1, 1000000007)
        print(s)

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 = [int(i) for i in input().split()]

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

Submission status: Accepted

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

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

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

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

Z=X+Y
if Z%3 == 0:
    D=int(Z/3)
    d=min(X,Y)
    print(cmb(D,d-D,MOD))
else:
    print(0)

Submission status: Accepted

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


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

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


if (Y>2*X) or (Y < X/2) or ((X+Y)%3)!=0:
    ans=0
else:
    n=((X+Y)//3)
    r=min((abs(X-(X+Y)//3)),abs(Y-(X+Y)//3))
    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, r, mod)

print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]


    X,Y = LMIIS()
    MOD = 10**9 + 7



    # def cmb(n,r):  #nCr = n!/(n-r)!r!
    #     retVal = 1
    #     for i in range(n-r+1,n+1):
    #         retVal *= i
    #         retVal %= MOD
    #     div = 1
    #     for i in range(2,r+1):
    #         div *= i
    #         div %= MOD
    #     return retVal // div

    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:
        level = (X+Y) // 3 
        diff = level * 2 - X
        print(cmb(level,diff,mod))












if __name__ == '__main__':
    main()