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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

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

# nCr
def nCr(n,r):
  if n<r:
    return 0
  return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

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

  if min(x,y)*2<max(x,y):
    return 0

  sm=x+y
  if sm%3!=0:
    return 0

  cnt=sm//3
  ac=cnt//2-((x-y)//2)
  bc=cnt-ac

  # print(ac)
  # print(bc)

  return cmb(cnt,ac)%mod


# main()
print(main())

Submission status: Accepted

Solution code:
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
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)
else:
  n = (x+y)//3
  r = min(abs(2*n-x),abs(n-x))
  if 2*n < x or x < n:
    print(0)
  else:
    a = cmb(n,r,mod)
    print(a)

Submission status: Accepted

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

m = 10**9+7

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]
# aの逆元(mod m)を求める。
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m


nlist=[1]*(10**6)
rlist = [1]*(10**6)

nor = 1
res = 1
for i in range(1,10**6):
    nor = nor*i%m
    res = res*mod_inv(i,m)%m
    nlist[i] = nor
    rlist[i] = res

ans = 0
if (x+y)%3!=0:
    ans=0
else:
    keynum = (x+y)//3
    if x>keynum*2:
        ans=0
    elif x<keynum:
        ans = 0
    else:
        h = y - keynum
        w = keynum-h
        
        #res = 1
        """for i in range(1,int(h+w+1)):
            res = res*i%m
        for i in range(1,int(h+1)):
            res = res*mod_inv(i,m)%m
        for i in range(1,int(h+1)):
            res = res*mod_inv(i,m)%m"""
        
        res = nlist[h+w]*rlist[h]*rlist[w]%m
        ans = res
        
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 = map(int,input().split())

if (X+Y)%3==0:
  _sum = (X+Y)//3
  a = Y-_sum
  b = X-_sum
  print(cmb(_sum,a,1000000007))
  
else:
  print(0)

Submission status: Accepted

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

Submission status: Accepted

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


# modしながらコンビネーションを求める
def mod_cmb(n, r, mod):
    p, q = 1, 1
    for i in range(r):
        p = p * (n - i) % mod
        q = q * (i + 1) % mod
    return p * mod_inverse(q, mod) % mod


# modしたa^bを求める
def mod_pow(a, p, mod):
    if p == 0:
        return 1
    elif p % 2 == 1:
        return a * mod_pow(a, p - 1, mod)
    else:
        return (mod_pow(a, p // 2, mod) % mod) ** 2 % mod


# aで割りたいときはa^(p-2)をかければよい（pは素数かつmodで使うやつ）
def mod_inverse(a, mod):
    return mod_pow(a, (mod - 2), mod)


# 移動1, 2を使う回数
n, m = 0, 0

for i in range(10 ** 6):
    if X - i == (Y - 2 * i) * 2 == 0 or X - i == (Y - 2 * i) * 2 != 0:
        n = i
        m = Y - 2 * n
        break
else:
    print(0)
    exit()

print(mod_cmb(n + m, n, mod))

Submission status: Accepted

Solution code:
import math

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def powd(x, n, m):
  ans = 1
  while(n > 0):
    if(bin(n & 1) == bin(1)):
      ans = (ans*x)%m
    x = x*x % m
    n = n >> 1 #ビットシフト
  return ans

mod = 1000000007

#a = list(map(int, input().split()))
X,Y = list(map(int, input().split()))

com=[1 for i in range(1000002)]
inv=[1 for i in range(1000002)]

for ii in range(1000000):
    i = ii+1
    com[i+1] = (com[i]*(i+1))%mod



#print(com[0:8])
#print(inv[0:8])

def invc(n,mo):
    return powd(com[n],mo-2,mo)

#print("a",com[4],invc(4,mod),com[4]*invc(4,mod)%mod)

if((X+Y)%3 != 0 or Y/X <0.49999999 or Y/X > 2.00000001):
    print(0)
else:
    level = (X+Y)//3
    b = (level-abs(X-Y))//2
    #print(level,b)
    ans= com[level] * powd(com[level-b],mod-2,mod) * powd(com[b],mod-2,mod) % 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 = map(int, input().split())

if (X + Y) % 3 != 0 or 2*Y < X or Y > 2*X:
    ans = 0
else:
    n = (X+Y) // 3
    r = X - n

    ans = cmb(n, r, mod)

print(ans)

Submission status: Accepted

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

from math import factorial
mod = 10**9+7
def nCr(fact, inv, n, r):
    return fact[n] * inv[r] * inv[n-r] % mod

def main():
    X, Y = map(int, input().split())
    if Y < (X/2) or Y > (2*X):
        print(0)
        return
    if (Y+X) % 3 != 0:
        print(0)
        return
    n = (X+Y)//3
    m = (2*Y-X)//3

    N = n
    fact = [1]
    for i in range(1, N+1):
        fact.append(fact[i-1] * i % mod)
    inv = [0] * (N+1)
    inv[N] = pow(fact[N], mod-2, mod)
    for i in range(N, 0, -1):
        inv[i-1] = inv[i] * i % mod

    print(nCr(fact, inv, n, abs(n-m)) % mod)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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 and x <= 2*y and y <= 2*x:
    jump = (x+y)//3
    jump12 = y-jump
    
    print(cmb(jump,jump12,mod))
else:
    print(0)

Submission status: Accepted

Solution code:
import math
import sys

m=10**9 + 7 
sys.setrecursionlimit(1000010)
(x,y) = map(int,input().split())

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


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

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

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

print(comb(a+b,a,m))

Submission status: Accepted

Solution code:
def answer():
    def cmb(n, r, mod):
        r = min(r, n - r)
        return g1[n] * g2[r] * g2[n - r] % mod

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

    if (2 * x - y) % 3 == 0 and a >= 0 and b >= 0:
        a = int(a)
        b = int(b)

        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)

        result = int(cmb(n, a, mod))
    else:
        result = 0

    print(result)


if __name__ == '__main__':
    answer()

Submission status: Accepted

Solution code:
import math
a,b=map(int,input().split())
x=max(a,b)
y=min(a,b)
p=abs(x-y)

P = 10**9 + 7
N = 1000000
inv_t = [0]+[1]
for i in range(2,N):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

if (x+y)%3!=0:
    print(0)
elif x>y*2:
    print(0)
else:
    n=(x+y)//3
    q=(2*x-y)//3
    r=(2*y-x)//3
    
    #print(math.factorial(q+r)//math.factorial(q)//math.factorial(r)%(10**9+7))
    ans=1
    qq=1
    rr=1
    for i in range(1,q+r+1):
        ans*=i
        ans%=10**9+7
    for i in range(1,q+1):
        ans*=inv_t[i]
        ans%=10**9+7
    for i in range(1,r+1):
        ans*=inv_t[i]
        ans%=10**9+7
            
            
    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())
mod = 10**9 + 7

if (X + Y)%3 != 0:
  result = 0
else:
  n1 = (2*Y - X)//3
  n2 = (2*X - Y)//3
  if n1 < 0 or n2 < 0:
    result = 0
  else:
    result = comb(n1+n2, n1, mod)

print(result)

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


a,s=map(int,input().split())
if (2*a-s)%3==0 and max(a,s)<=2*min(a,s):
  n=(a+s)//3
  r=(2*a-s)//3
  print((cmb(n,r))%(10**9+7))
else:print(0)

Submission status: Accepted

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

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

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

N = 10**6

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 )

def test(X, Y):
  if ((X+Y)%3 != 0):
    return 0
  if not(X <= 2*Y <= 4*X):
    return 0
  n = (X+Y)//3
  r = X - n
  return cmb(n,r,mod)

print(test(X,Y))

Submission status: Accepted

Solution code:
X,Y=map(int,input().split())
a=(2*Y-X)/3
b=(2*X-Y)/3
check=False
if a%1!=0 or b%1!=0:
  check=True
n=a//1
r=b//1
def cmb(n, r, mod):
    if (r<0 or r>n):
        return 0
    r = min(r, n-r)
    n=int(n)
    r=int(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((-1*inverse[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1]*inverse[-1]) % mod)
ans=cmb(n+r,r,mod)
print(ans if not check else 0)

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


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

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


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

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

    a, b = x-(x+y)//3, y-(x+y)//3
    print(cmb(a+b, a) % mod)


if __name__ == '__main__':
    main()

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
  
mod = int(1e9+7)
X, Y = map(int, input().split())
if (X+Y)%3 != 0:
    print(0)
else:
    total_steps = (X+Y)//3
    dif_steps = abs(X-Y)
    if dif_steps > total_steps:
        print(0)
    else:
        up_steps = (total_steps - dif_steps)//2
        fn, invs = prepare(total_steps, mod)
        print((fn*invs[up_steps]*invs[total_steps-up_steps])%mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

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



if (X + Y) % 3 == 0:
    C = (X + Y) // 3
    x1 = C*2
    y1 = C*1

    x2 = C*1
    y2 = C*2

    if (x1-X) >= 0 and (y2-Y) >= 0:
        c1 = x1 - X
    
        for i in range(2, C+1):
            g1.append( ( g1[-1] * i ) % mod )
            inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
            g2.append( (g2[-1] * inverse[-1]) % mod )

        a = cmb(C,c1,mod)
        print(a)

    else:
        print(0)

else:
    print(0)

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import os
import sys


def main():
    X, Y = read_ints()
    print(solve(X, Y))


MOD = 10 ** 9 + 7


def mpow(a, n):
    p = a
    v = 1
    while n > 0:
        if n & 1:
            v *= p
            v %= MOD
        n >>= 1
        p *= p
        p %= MOD
    return v


def solve(X, Y):
    s = X + Y
    if s % 3 != 0:
        return 0
    s //= 3

    a = 2 * s - X
    b = 2 * s - Y
    if a < 0 or b < 0:
        return 0

    c = a + b

    facts = [0] * (c + 1)
    facts[0] = 1
    for i in range(1, c + 1):
        facts[i] = (facts[i - 1] * i) % MOD

    return (facts[c] * mpow(facts[a], MOD - 2) * mpow(facts[b], MOD - 2)) % MOD


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

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
MOD = 1000000007  # type: int

def factorial(n):
    f = 1
    while n>0:
        f*=n
        f = f%MOD
        n-=1
    return f

def solve(X: int, Y: int):
    if X>2*Y or Y>2*X or (X+Y)%3!=0:
        print(0)
        return 
    
    N = (X+Y)//3 ##N階層め

    # N階層めの一番端のX
    left_x = 2*N
    r = left_x-X
    bunsi = factorial(N)
    bunbo = factorial(N-r)*factorial(r)
    bunbop = pow(bunbo,MOD-2,MOD)
    print(bunsi*bunbop%MOD)
    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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(5,2,mod)


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

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

if a.is_integer() == True and b.is_integer() == True:

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

else:
    print(0)

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
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

def main():
    X, Y = map(int, input().split())
    if (X + Y) % 3 != 0:
        print(0)
        return
    Xp = (X + Y) // 3
    Yp = Y - Xp
    if Yp < 0 or Yp > Xp:
        print(0)
        return
    print(cmb(Xp, Yp, mod))

main()

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

ans = 0
if (X+Y)%3 != 0:
    pass
else:
    N = (X+Y)//3
    t = 2*N - X
    if t >= 0:
         if (N+t) == Y and t <= N:
             t = max(t,N-t)
             ans = cmb(N,t)
             ans = ans%MOD
print(ans)

Submission status: Accepted

Solution code:
import math
words = lambda t : list(map(t, input().split()))
x,y = words(int)

MOD = 10**9+7

def modpow(a,b,mod):
    if b == 0: return 1
    if b % 2 == 0:
        h = modpow(a, b//2, mod)
        return (h * h) % mod
    else:
        return (a * modpow(a, b-1, mod)) % mod

def mod_comb(a,b,mod):
    #print(a,b)
    if a-b < b: return mod_comb(a,a-b,mod)
    ans_mul = 1
    ans_div = 1
    for i in range(b):
        ans_mul *= a-i
        ans_div *= i+1
        ans_mul %= mod
        ans_div %= mod
    return (ans_mul * modpow(ans_div, mod-2, mod)) % mod


if (x+y) % 3 != 0:
    print(0)
elif x < (x+y)//3 or y < (x+y)//3:
    print(0)
else:
    k = (x + y) // 3
    #print(k, k, y-k)
    ans = mod_comb(k,y-k,MOD)
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

M = 1000000007


def inv(x, m):
  y, u, v = m, 1, 0

  while y != 0:
    t = x // y
    x -= t * y
    u -= t * v
    x, y = y, x
    u, v = v, u

  return u % m


def main():
  x, y = map(int, input().split())
  r = 2 * x - y
  l = 2 * y - x

  if r < 0 or l < 0 or r % 3 != 0 or l % 3 != 0:
    print(0)
    return

  r //= 3
  l //= 3
  value = 1

  for i in range(l):
    value = (value * (r + l - i)) % M
    value = (value * inv(i + 1, M)) % M

  print(value)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
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
X , Y = map(int,input().split())
N = max(X,Y)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
mod = 10 ** 9 + 7
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 % 2 == 0 :
    p = X // 2
    q = 0
    while True :
        if Y == p + 2 * q :
            ans = cmb(p+q,min(p,q),mod)
            break
        elif p < 0 :
            ans = 0
            break
        else:
            p -= 1
            q += 2
    print(ans)
else:
    p = X // 2
    q = 1
    while True:
        if Y == p + 2 * q:
            ans = cmb(p + q, min(p, q),mod)
            break
        elif p < 0 :
            ans = 0
            break
        else:
            p -= 1
            q += 2
    print(ans)

Submission status: Accepted

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

prime = 10 ** 9 + 7

if (x + y) % 3 > 0 or x > y * 2 or x * 2 < y:
  print(0)
else:
  num = (x + y) // 3
  _x = x - num
  _y = y - num
  
  fac = [0 for i in range(num + 1)]
  inv = [0 for i in range(num + 1)]
  finv = [0 for i in range(num + 1)]
  
  fac[0] = fac[1] = 1
  finv[0] = finv[1] = 1
  inv[1] = 1

  for i in range(2, num + 1):
    fac[i] = fac[i - 1] * i % prime
    inv[i] = prime - inv[prime % i] * (prime // i) % prime
    finv[i] = finv[i - 1] * inv[i] % prime
  
  print(fac[num] * (finv[_x] * finv[num - _x] % prime) % prime)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
MOD = 10 ** 9 + 7
X, Y = map(int, input().split())
if (X + Y) % 3 != 0:
    print(0)
    exit()
if 2 * Y < X or Y > 2 * X:
    print(0)
    exit()

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

N = (X + Y) // 3 + 1
K = 2 * (N-1) - X + 1
print(combination(N-1, K-1, MOD))

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce

def cmb(n, r, mod,g1,g2):

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


def solve():
    X,Y=[int(x) for x in input().split()]
    if (2*Y-X)%3 or (2*X-Y)%3:
        return 0
    
    a=(2*X-Y)//3
    b=(2*Y-X)//3
    

    n=a+b
    r=a

    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル
    mod = 10**9+7
    N = 10**6
    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 cmb(n,r,mod,g1,g2)

    
print(solve())

Submission status: Accepted

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


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


def fact(a, p):
    f = 1
    for i in range(1, a + 1):
        f *= i
        f %= p
    return f


if (X + Y) % 3 == 0:
    N = (X + Y) // 3
    if X - N >= 0 and Y - N >= 0:
        ans = fact(N, MOD) * pow(fact(X - N, MOD), MOD - 2, MOD) * \
            pow(fact(Y - N, MOD), MOD - 2, MOD)
        ans %= MOD
    else:
        ans = 0
else:
    ans = 0

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 = map(int,input().split())
mod = 10**9 + 7
if (x + y) % 3 > 0:
    print(0)
else:
    n = (x + y) //3
    r = x - n 
    print(cmb(n,r,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())

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

#print(n)
#print(a)

if not n.is_integer() or not a.is_integer():
  print(0)
else:
  n = int(n)
  a = int(a)
  ans = cmb(n,a,mod)
  print(ans)

Submission status: Accepted

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

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

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

x = X - (X + Y) // 3
y = Y - (X + Y) // 3

if x < 0 or y < 0:
    print (0)
    exit()

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

# tmp = math.factorial(y)
tmp = 1
for i in range(1, y + 1):
    tmp *= i
    tmp %= MOD

ans = 1
for i in range(x + 1, x + y + 1):
    ans *= i
    ans %= MOD

def modinv(a, m): #mod. m でのaの逆元 a^{-1}を計算する
    b = m
    u = 1
    v = 0
    while b:
        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

tmp = modinv(tmp, MOD)

ans *= tmp

ans %= MOD

print (ans)

# print (x, y)

Submission status: Accepted

Solution code:
mod = 10**9+7

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

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

    if choice >= 0 and choice %3 == 0:
        A = choice//3
        B = A+abs(X-Y)
        ans = 1
        for i in range(B+1,A+B+1):
            ans *= i
            ans %= mod
        for i in range(1,A+1):
            ans *= pow(i,mod-2,mod)
            ans %= mod
        return ans
    else:
        return 0

    

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

Submission status: Accepted

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

if (2 * X - Y) % 3 == 0:
    a = int((2 * X - Y) / 3)
else:
    a = 'No'
if (2 * Y - X) % 3 == 0:
    b = int((2 * Y - X) / 3)
else:
    b = 'No'

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 a == 'No' or a < 0 or b == 'No' or b < 0:
    print(0)
else:
    ans = cmb(a + b, a)
    print(ans % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
X,Y=map(int,input().split())
MOD=10**9+7
def comb1(n,k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    ans=1
    inv=[1]*(k+1)
    if k>=1:
        ans*=(n-k+1)%MOD
    for i in range(2,k+1):
        inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
        ans=ans*(n-k+i)*inv[i]%MOD
    return ans
if (X+Y)%3==0 and X*2>=Y and X<=Y*2:
    p,q=(2*Y-X)//3,(2*X-Y)//3
    print(comb1(p+q,p))
else:
    print(0)

Submission status: Accepted

Solution code:
def find_power(n):
    # 0!からn!までのびっくりを出してくれる関数
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(10**9+7)
    return powlist
def find_inv_power(n):
    #0!からn!までの逆元を10**9+7で割ったあまりリストを作る関数
    powlist=find_power(n)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist
def combi(a,b,n,r,mod):
    if n<r:
        return 0
    elif n>=r:
        return (a[n]*b[r]*b[n-r])%(mod)
x,y=map(int,input().split())
power=find_power(1000000)
invpower=find_inv_power(1000000)
if (2*x-y)%3==0 and (2*y-x)%3==0:
    if (2*x-y)>=0 and (2*y-x)>=0:
        a=(2*y-x)//3
        b=(2*x-y)//3
        print(combi(power,invpower,a+b,b,10**9+7))
    else:
        print(0)
else:
    print(0)