Problem:


Score : 400 points

Problem Statement

There is a knight - the chess piece - at the origin (0, 0) of a two-dimensional grid.

When the knight is at the square (i, j), it can be moved to either (i+1,j+2) or (i+2, j+1).

In how many ways can the knight reach the square (X, Y)?

Find the number of ways modulo 10^9 + 7.

Constraints

1 \leq X \leq 10^6

1 \leq Y \leq 10^6

All values in input are integers.

Input

Input is given from Standard Input in the following format:

X Y

Output

Print the number of ways for the knight to reach (X, Y) from (0, 0), modulo 10^9 + 7.

Sample Input 1

3 3

Sample Output 1

2

There are two ways: (0,0) \to (1,2) \to (3,3) and (0,0) \to (2,1) \to (3,3).

Sample Input 2

2 2

Sample Output 2

0

The knight cannot reach (2,2).

Sample Input 3

999999 999999

Sample Output 3

151840682

Print the number of ways modulo 10^9 + 7.



Sample input:
3 3


Sample output:
2

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

#1400

def main():
	x,y=MI()
	mod=10**9+7

	a=2*y-x
	b=2*x-y

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

	a//=3
	b//=3

	f=[1]
	for i in range(1,10**6):
		f.append(f[-1]*i%mod)

	ans=f[a+b]*pow(f[a],mod-2,mod)*pow(f[b],mod-2,mod)
	print(ans%mod)


if __name__ == "__main__":
	main()

Submission status: Accepted

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

import sys
sys.setrecursionlimit(200000000)
p = 10**9+7

def exp(y,x):
  xbin=str(bin(x))[2:]
  ans=1
  yl=[0]*(len(xbin)+1)
  yl[0]=y
  yl[1]=y**2
  for d,i in enumerate(xbin[::-1],start=0):
    if d > 1:
      yl[d]=yl[d-1]**2%p
    if i == "1":
      ans=(ans*yl[d])%p
  return ans%p

def ff(n,ca):
  if ca == 0:
    return 1
  if ca == 1:
    return n
  return n*ff(n-1,ca-1)%p

if (y+x)%3 != 0:
  print(0)
elif y/x > 2:
  print(0)
elif y/x < 0.5:
  print(0)
else:
  n=(2*x-y)//3
  m=(2*y-x)//3
  fact=1
  for i in range(2,n+1):
    fact=fact*i%p
  ans=ff(n+m,n)*exp(fact,p-2)%p
  print(ans)

Submission status: Accepted

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

mod = 10 ** 9 + 7
def cmb(n, r, mod):
    r = min(r, n - r)
    x = 1
    y = 1
    for i in range(r):
        x = x * (n - i) % mod
        y = y * (i + 1) % mod
    y = pow(y, mod-2, mod)
    return x * y % mod

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

n=(x+y)//3

x-=n
y-=n
if x < 0 or y < 0: print(0);exit()

print(cmb(x+y,x,mod))

Submission status: Accepted

Solution code:
def framod(x,p=10**9+7):
  a=1
  for i in range(1,x+1):
    a = (a*i)%p
  return a
#############################################
X,Y=map(int,input().split())
p=10**9+7

if (X+Y)%3!=0:
  print(0)
else:
  a = (2*X-Y)//3
  b = (2*Y-X)//3
  t = a+b
  if a<0 or b<0:
    print(0)
  else:
    S=framod(t)
    T=pow(framod(a),p-2,p)
    U=pow(framod(b),p-2,p)
    print(((S*T)%p)*U%p)

Submission status: Accepted

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

import math

def combination(n, x, mod=10**9+7):
    factorial = [1] * (n+1)
    t = 1
    for i in range(1, n+1):
        t = (t * i) % mod
        factorial[i] = t
    tmp = factorial[n]
    tmp = (tmp * pow(factorial[x], mod-2, mod)) % mod
    tmp = (tmp * pow(factorial[n-x], mod-2, mod)) % mod
    return tmp

if 2*Y-X<0 or 2*X-Y<0:
	print(0)
elif (2*Y-X)%3!=0 or (2*X-Y)%3!=0:
	print(0)
else:
	a=(2*Y-X)//3
	b=(2*X-Y)//3
	print(combination(a+b,a,mod=10**9+7))

Submission status: Accepted

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

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

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

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

mod = 10**9+7


def comb(n, r, mod):
    x=y=1
    for i in range(r):
        x *= n; y *= r
        x %= mod; y %= mod
        n -= 1; r -= 1
    return x * pow(y, mod - 2, mod) % mod

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

Submission status: Accepted

Solution code:
def solve():
    x, y = map(int, input().split())
    n = (2*y-x) / 3
    m = (2*x-y) / 3

    mod = 10**9+7

    if n < 0 or m < 0 or (x+y)% 3 != 0:
        return 0
    cmb = 1
    n = int(n)
    m = int(m)
    
    cnt = 0
    for i in range(n):
        cnt += 1
        cmb *= n+m-i
        cmb *= pow(i+1, mod-2, mod)
        cmb %= mod
    return cmb

print(solve())

Submission status: Accepted

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

def cmb(n, r):
    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)
    exit()

A = (2 * Y - X) // 3
B = (2 * X - Y) // 3

print(cmb(A + B, A))

Submission status: Accepted

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

def cmb(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    """
    階乗テーブル、逆元の階乗テーブルを作成する
    """
    fac = [1, 1] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac


def comb(m,n):
    MOD = 10**9 + 7
    fac, ifac = make_tables(MOD, m)
    ans = cmb(m, n, MOD, fac, ifac)
    return ans

def calculate(x,y):
    m = 0
    n = 0

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

    result = []

    while (2*m <= x) and (m <= y):
        n = x - 2 * m
        if (2*m + n == x) and (2*n + m == y):
            result.append(comb(m+n,n))

        m = m + 1

    if len(result) == 0:
        print(0)
    else:
        print(min(result))

calculate(X,Y)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): return k.join(list(map(str, lst)))
INF = float('inf')

def mcomb(n, k, mod):
    def mfac(l, r, mod):
        ans = l
        for i in reversed(range(r, l)):
            ans *= i
            ans %= mod
        return ans

    A = mfac(n,n-k+1,mod)
    B = mfac(k,1,mod)
    # B = mpow(B,mod-2,mod)
    B = pow(B, mod-2, mod)
    return A * B % mod

def solve():
    x, y = MI()
    if (x + y) % 3 != 0:
        print(0)
        return

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

    mod = 1000000007
    ans = mcomb(x+y, max(x, y), mod)
    print(ans % mod)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
X, Y = map( int, input().split())
MOD = 10 ** 9 + 7
  
def n_H_r( n, r ):
  n1, n2 = 1, 1
  for i in range( 1, r + 1 ):
    n1 = n1 * ( n + i )  % MOD
    n2 = n2 * i % MOD
  return ( n1 * pow( n2, MOD - 2, MOD )) % MOD

cnt = 0
if ( ( X + Y ) % 3 == 0 ) and ( max( X, Y ) <= 2 * min( X, Y )):
  base = ( X + Y ) // 3
  a, b = 0, 0
  for i in range( base + 1 ):
    j = base - i
    if ( 2 * i + j == X ) and ( i + 2 * j == Y ):
      a = i
      b = j
      break
  cnt = n_H_r( a, b )
print( cnt )

Submission status: Accepted

Solution code:
'''
nCk mod pを求める。

nCk= n!/k!(n-k)!を考えるが、単純計算だと途中の桁が膨大になり計算が間に合わない。
そこで計算中にmodをとるが、割り算にmodを適用するためには逆元を求める必要がある。


'''

from collections import defaultdict,deque
import sys, bisect, math, itertools
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


class combination():
    def __init__(self, mod):
        '''
        modを指定して初期化
        '''
        self.mod=mod
        self.fac = [1, 1]  # 階乗テーブル
        self.ifac = [1, 1]  # 階乗の逆元テーブル
        self.inv = [0, 1]  # 逆元計算用

    def calc(self,n,k):
        '''
        nCk%modを計算する
        '''
        if k < 0 or n < k:
            return 0
        self.make_tables(n) #テーブル作成
        k = min(k, n - k)
        return self.fac[n] * (self.ifac[k] * self.ifac[n - k] % self.mod) % self.mod

    def make_tables(self, n):
        '''
        階乗テーブル・階乗の逆元テーブルを作成
        '''
        for i in range(len(self.fac), n + 1):
            self.fac.append((self.fac[-1] * i) % self.mod)
            self.inv.append((-self.inv[self.mod % i] * (self.mod // i)) % self.mod)
            self.ifac.append((self.ifac[-1] * self.inv[-1]) % self.mod)

comb = combination(mod)

x, y = inpl()
if x > y:
    x, y = y, x
dist = x + y
if dist % 3:
    print(0)
    exit()
total = int((x + y) // 3)
n = x - total
if y > 2 * x:
    print(0)
    exit()

print(comb.calc(total, n))

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
MAX = 700000
fact = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX


def CombInit():
    fact[0] = fact[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fact[i] = fact[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD


def Comb(n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return fact[n] * (finv[k] * finv[n - k] % MOD) % MOD


X, Y = map(int, input().split())
if (X + Y) % 3:
    print(0)
else:
    CombInit()
    m = (2 * X - Y) // 3
    n = (2 * Y - X) // 3
    print(int(Comb(m + n, m)))

Submission status: Accepted

Solution code:
import numpy as np
import math

def cmb(n, r, mod):
    n_1 = 1
    n_2 = 1

    r = min(r, n-r)
    for i in range(1, r+1):
        n_1 = n_1 * i % mod
        n_2 = n_2 * (n - i + 1) % mod

    return (n_2 * pow(n_1, mod - 2, mod))%mod

mod = 10**9+7

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

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


if x.is_integer() == False or y.is_integer() == False or x < 0 or y < 0:
    print(0)
else:
    print(cmb(int(x+y), int(x), mod))

Submission status: Accepted

Solution code:
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!=0:
  print(0)
else:
  n=2*Y-X
  m=2*X-Y
  mod=10**9+7
  if n<0 or m<0:
    print(0)
  else:
    n=int(n/3)
    m=int(m/3)
    print(cmb(n+m,m)%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 )
if (X+Y)%3!=0:
  print(0)
else:
  n=2*Y-X
  m=2*X-Y
  if n<0 or m<0:
    print(0)
  else:
    n=int(n/3)
    m=int(m/3)
    print(cmb(n+m,m,mod))

Submission status: Accepted

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

if (x+y)%3 != 0:
  print(0)
  exit()
if 2*x < y:
  print(0)
  exit()
if 2*y < x:
  print(0)
  exit()
  
mod = 10**9+7
n = (2*x-y)//3
m = (2*y-x)//3

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod) 
  
def comb(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

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

Submission status: Accepted

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

if (x+y)%3 != 0:
  print(0)
  exit()
if 2*x < y:
  print(0)
  exit()
if 2*y < x:
  print(0)
  exit()
  
mod = 10**9+7
n = (2*x-y)//3
m = (2*y-x)//3

def make_array_for_comb(N, mod=10**9+7):
    fact = [1,1]
    fact_inv = [1,1]
    inv = [0,1]
    for i in range(2, N+1):
        fact.append((fact[-1]*i) % mod)
        # モジュラ逆数の性質
        inv.append((-inv[mod%i] * (mod//i)) % mod)
        fact_inv.append((fact_inv[-1]*inv[i]) % mod)
    return fact, fact_inv

def comb(n, r, mod=10**9+7):
  if (r < 0) or (n < r):
      return 0
  r = min(r, n - r)
  return fact[n] * fact_inv[r] * fact_inv[n-r] % mod

fact, fact_inv = make_array_for_comb(n+m,mod)

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

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
s = (2 * y -x) / 3
t = (2 * x -y) / 3
if s.is_integer() and t.is_integer() and s >= 0 and t >= 0:
    def comb(n, r, mod=10 ** 9 + 7):
        a = 1
        b = 1
        r = min(r, n - r)
        for i in range(r):
            a = a * (n - i) % mod
            b = b * (i + 1) % mod
        return a * pow(b, mod - 2, mod) % mod
    s = int(s)
    t = int(t)
    print(comb(s + t, t, mod=10 ** 9 + 7))
else:
    print(0)

Submission status: Accepted

Solution code:
def ext_euler(a, b):
    # return (x, y, gcd(a, b)) s.t. ax + by = gcd(a, b)
    assert a > b
    if b == 0:
        return 1, 0, a
    y, x, v = ext_euler(b, a % b)
    y -= (a // b) * x
    return x, y, v


def mod_inv(a, mod):
    if a > mod:
        x, _, _ = ext_euler(a, mod)
    else:
        _, x, _ = ext_euler(mod, a)
    return x % mod


def mod_comb(n, k, mod):
    if k > n // 2:
        return mod_comb(n, n - k, mod)
    c = 1
    for i in range(k):
        c *= (n - i)
        c *= mod_inv(k - i, mod)
        c %= mod
    return c


def main():
    MOD = 10**9 + 7
    X, Y = list(map(int, input().split(' ')))
    if (2 * X - Y) % 3 != 0 or (- X + 2 * Y) % 3 != 0:
        print(0)
        exit(0)
    a = (2 * X - Y) // 3
    b = (- X + 2 * Y) // 3
    if a < 0 or b < 0:
        print(0)
        exit(0)
    print(mod_comb(a + b, b, MOD))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	X,Y = inputMap()

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

	turn = (X+Y) // 3

	X -= turn
	Y -= turn

	if X < 0 or Y < 0:
		print(0)
		sys.exit()

	print(combination(X+Y,X))

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	X,Y = inputMap()

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

	turn = (X+Y) // 3

	X -= turn
	Y -= turn

	if X < 0 or Y < 0:
		print(0)
		sys.exit()

	print(combination(X+Y,Y))

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
#ika　tako
'''
A.ダメなケースを除外できるか、B.組合せの数を問題に応じて求められるか
階乗や逆元はfor文で求める。
ダメなケースを除外した上で、最終X,Y に行くには、二つの選択肢
(i+1,j+2),(i+2,j+1)の組合せの数を求める。
組合せの数を求める時は、階乗と逆元を使う。
逆元は一通り、全て求めておいて、配列invsに格納して、後で使う。
'''
def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f = f * m % MOD
    fn = f#n!を求める

    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)#[1, 1, 1]のイメージ、逆元？格納テーブル
    invs[n] = inv#配列の一番最後のデータ
    for m in range(n, 1, -1):#n*(n-1)*(n-2)*...と上から掛けている
        inv = inv * m % MOD#逆元を一通り、求めて、配列invsに格納する
        invs[m - 1] = inv
        
    return fn, invs

def solve(x, y):#ダメなケースの除外
    d, m = divmod(x + y, 3)#商と余り
    if m != 0 or x < d or y < d:
    #Xとyの合計は3の倍数、x、yがd移動回数以下はあり得ない（1回1個は進む）
        return 0
    #c = d - x　　これだと範囲外参照でエラー
    c = abs(d - x)#nCr=nC(n-r)、Cの後ろのrと(n-r)を入れ替えても同じ
 
    MOD = 10 ** 9 + 7
    f, invs = prepare(d, MOD)
    return f * invs[c] * invs[d - c] % MOD
  #fはn!、invs[c],invs[d - c] はc!,(d-c)!の逆元？
  #nCr=n!/(r!*(n-r)!)
  
x, y = map(int, input().split())
print(solve(x, y))

Submission status: Accepted

Solution code:
def cmb(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    """
    階乗テーブル、逆元の階乗テーブルを作成する
    """
    fac = [1, 1] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac
mod = 10**9+7
x,y = map(int,input().split())
if (x+y) % 3 != 0:
    res = 0
else:
    m = (2 * x - y) // 3
    n = (2 * y - x) // 3
    if m < 0 or n < 0:
        res = 0
    else:
        total = n+m
        k = n
        fac,ifac = make_tables(mod, total)
        res = cmb(total, k, mod, fac, ifac)
print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

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

def combination(n,r,q):
    if r==0:
        return 1

    return ((n*combination(n-1,r-1,q)%q)*modinv(r,q))%q

def _input():
    return list(map(int, input().split()))

def main():
    i=_input()
    x,y=i[0],i[1]
    if 2*y>=x and 2*x>=y and (2*y-x)%3==0 and (2*x-y)%3==0:
        n=(2*y-x)//3
        m=(2*x-y)//3
        print(int(combination(n+m,min(m,n),1000000007)))
    else:
        print(0)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
 
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
 
def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
 
def combination(n,r,q):
    if r==0:
        return 1
 
    return ((n*combination(n-1,r-1,q)%q)*modinv(r,q))%q
 
def _input():
    return list(map(int, input().split()))
 
def main():
    i=_input()
    x,y=i[0],i[1]
    if 2*y>=x and 2*x>=y and (2*y-x)%3==0 and (2*x-y)%3==0:
        n=(2*y-x)//3
        m=(2*x-y)//3
        print(int(combination(n+m,min(m,n),1000000007)))
    else:
        print(0)
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
INF=1000000007
if (x+y)%3!=0:
    print(0)
    exit(0)
if x>2*y or y>x*2:
    print(0)
    exit(0)
times_sum=(x+y)//3
x-=times_sum;y-=times_sum
def factorial_cor(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
        fact %= INF
    return fact
a=factorial_cor(x+y)
b=factorial_cor(y)
c=factorial_cor(x)
def modinv(a):
    b=INF;u=1;v=0
    while b:
        t=a//b
        a-=t*b
        a,b=b,a
        u-=t*v
        u,v=v,u
    u%=INF
    if u<0:
        u+=INF
    return u
b=modinv(b)
c=modinv(c)

print(a*b*c%INF)

Submission status: Accepted

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

def powmod(a,p):
  if p==0:
    return 1
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD
def invmod(a):
  return powmod(a,MOD-2)
def comb_mod(n,r):
  r=min(r,n-r)
  nPr=1
  fact_r=1
  for i in range(r):
    nPr*=n-i
    nPr%=MOD
    fact_r*=r-i
    fact_r%=MOD  
  return (nPr*invmod(fact_r))%MOD

if (X+Y)%3!=0:
  print(0)
else:
  u=(2*X-Y)//3
  v=(-X+2*Y)//3
  if u>=0 and v>=0:    
    #print(u,v)
    print(comb_mod(u+v,v))
  else:
    print(0)

Submission status: Accepted

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

def powmod(a,p):
  if p==0:
    return 1
  elif p==1:
    return a
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD
def invmod(a):
  return powmod(a,MOD-2)
def comb_mod(n,r):
  nPr=1
  fact_r=1
  for i in range(r):
    nPr*=n-i
    nPr%=MOD
    fact_r*=r-i
    fact_r%=MOD  
  return (nPr*invmod(fact_r))%MOD

if (X+Y)%3!=0:
  print(0)
else:
  u=(2*X-Y)//3
  v=(-X+2*Y)//3
  if u>=0 and v>=0:    
    #print(u,v)
    print(comb_mod(u+v,v))
  else:
    print(0)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float('inf')
MOD=10**9+7
input=sys.stdin.readline

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



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

if x==0 and y==0:
    print(0)
    exit()


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


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

if n==0 and m==1:
    print(1)
    exit()
if n==1 and m==0:
    print(1)
    exit()
    

#n+mCm
#(n+m)!/m!


def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)



print(cmb(n+m, m, 10**9+7))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
import collections

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

# 合計 a + b回動かす
a = (2*y-x)//3  # a回
b = (2*x-y)//3  # b回
# (a+b)!/a!b!
ans = 1
for i in range(1, a+b+1):
    ans = (ans * i) % mod
a_func = 1
for i in range(1, a+1):
    a_func = (a_func * i) % mod
inv_a_func = pow(a_func, mod-2, mod)

b_func = 1
for i in range(1, b+1):
    b_func = (b_func * i) % mod
inv_b_func = pow(b_func, mod-2, mod)

ans = (ans * inv_a_func) % mod
ans = (ans * inv_b_func) % mod
print(ans)

Submission status: Accepted

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


def calc_comb(n, k, mod):
    '''
        n が大きい場合に使う
    '''
    a = 1
    b = 1
    for i in range(1,k+1):
        a *= i
        a %= mod
        b *= n
        n -= 1
        b %= mod
    return b * pow(a, mod-2, mod) % mod

if (X+Y) % 3 != 0:
    print(0)
else:
    total_move = (X+Y) // 3
    # 右に2つ動くことを選択しなければいけない回数
    right_move =  min(X,Y) - total_move
    if right_move >= 0:
        print(calc_comb(total_move, right_move, MOD))
    else:
        print(0)

Submission status: Accepted

Solution code:
#階乗
F = 10**6+5
mod = 10**9+7
fact = [1]*F
inv = [1]*F
for i in range(2,F):
    fact[i]=(fact[i-1]*i)%mod
inv[F-1]=pow(fact[F-1],mod-2,mod)
for i in range(F-2,1,-1):
    inv[i] = (inv[i+1]*(i+1))%mod

x,y=map(int,input().split())
t=(x+y)//3
if (x+y)%3!=0 or x<t or y<t:
    print(0)
else:
    print(fact[t]*inv[x-t]*inv[2*t-x]%mod)

Submission status: Accepted

Solution code:
class Combination:
    def __init__(self, n, mod):
        self.mod = mod

        # self.fac[i] ≡ i! (factorial:階乗)
        l = [1]
        num = 1
        for i in range(1, n+1):
            num *= i
            num %= mod
            l.append(num)
        self.fac = l.copy()

        # self.rec[i] ≡ 1 / i! (reciprocal:逆数)
        num = pow(num, mod-2, mod)
        l = [1 for i in range(n+1)]
        l[n] = num
        for i in range(n-1, 0, -1):
            num *= i + 1
            num %= mod
            l[i] = num
        self.rec = l.copy()

    # comb(n, r) ≡ nCr
    def comb(self, n, r):
        return self.fac[n] * self.rec[r] * self.rec[n - r] % self.mod

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

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

n = (x + y) // 3
r = x - n
c = Combination(n, mod)
print(c.comb(n, r))