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:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

def main():
    x,y = map(int,ipt().split())

    #nCrをmodで割った余りを求める。Nに最大値を入れて使用。
    N = 7*10**5
    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル
    def cmb(n,r,mod=(10**9+7)):
        if r<0 or r>n :
            return 0
        r = min(r,n-r)
        return g1[n]*g2[r]*g2[n-r]%mod
    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 (2*x-y)%3 == 0 and 2*x-y >= 0 and (2*y-x)%3 == 0 and 2*y-x >= 0:
        print(cmb((x+y)//3,(2*x-y)//3))
    else:
        print(0)



    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
from collections import OrderedDict
import itertools
from sys import stdin
input = stdin.readline


class PrimeComb:
  def __init__(self, MAX=666670, MOD=1000000007):
    # preprocessing: O(MAX)
    self.MAX  = MAX
    self.MOD  = MOD
    self.fac  = [0]*MAX
    self.inv  = [0]*MAX
    self.finv = [0]*MAX
    self.fac[0]  = self.fac[1] = 1
    self.finv[0] = self.finv[1] = 1
    self.inv[1]  = 1
    for i in range(2, MAX):
      self.fac[i]  = self.fac[i-1] * i % MOD
      self.inv[i]  = MOD - self.inv[MOD % i] * int(MOD / i) % MOD
      self.finv[i] = self.finv[i-1] * self.inv[i] % MOD

  def com(self, n, k):
    # compute -> nCk % self.P : O(1)
    if (n < k): return 0
    if (n < 0 or k < 0): return 0
    return self.fac[n] * (self.finv[k] * self.finv[n-k] % self.MOD) % self.MOD


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

  num_trans1 = 0
  num_trans2 = 0

  # min_ = min(X, Y) // 3
  # X -= 3*min_
  # Y -= 3*min_
  # num_trans1 += min_
  # num_trans2 += min_
  ans = 0
  for i in range(min(X, Y)//3 + 1):
    tempX = X - 3*i
    tempY = Y - 3*i
    num_trans1 = i
    num_trans2 = i

    if tempX==tempY==0:
      ans += PC.com(num_trans1+num_trans2, num_trans1)

    elif tempX > tempY:
      if tempX % 2:
        # print(0)
        continue
      if tempX//2 != tempY:
        # print(0)
        continue
      num_trans2 += tempY
      ans += PC.com(num_trans1+num_trans2, num_trans1)
    elif tempX < tempY:
      if tempY % 2:
        # print(0)
        continue
      if tempY//2 != tempX:
        # print(0)
        continue
      num_trans1 += tempX
      ans += PC.com(num_trans1+num_trans2, num_trans1)

  # print(num_trans1, num_trans2)
  print(ans % 1_000_000_007)


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

Submission status: Accepted

Solution code:

def check_use_count(X, Y):
    a = (2 * X - Y) // 3
    b = X - 2 * a

    return a, b


def factorial(x, mod):
    if x == 0:
        return 1

    x %= mod

    for i in range(x-1, 0, -1):
        x *= i
        x %= mod

    return x


def main():
    mod = 10**9 + 7
    X, Y = [int(x) for x in input().split()]

    # 必ず3で割り切れる
    if (X + Y) % 3 != 0:
        print(0)
        exit()

    a, b = check_use_count(X, Y)

    # 0だったら行けない
    if a < 0 or b < 0:
        print(0)
        exit()

    # 移動パターンの計算
    # !(a + b) / !a * !b
    up = factorial(a + b, mod)
    fact_a = factorial(a, mod)
    fact_b = factorial(b, mod)

    down = fact_a * fact_b % mod

    result = up * pow(down, mod - 2, mod) % mod
    print(result)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
x, y = map(int, input().split())
MOD = 10**9+7
 
def combination(n, r, mod):
	r = min(r, n-r)
	num = 1
	d = 1
	for i in range(1, r+1):
		num = num * (n+1-i) % mod
		d = d * i % mod
	return num * pow(d, mod-2, mod) % mod
if (x+y)%3 != 0:
	print (0)
	exit()
n = (x+y)/3
yy = (2*x-y)/3
xx = (2*y-x)/3
if yy < 0:
  print (0)
  exit()
if xx < 0:
  print (0)
  exit()
if xx.is_integer() and yy.is_integer():
	print (combination(int(xx+yy),int(xx),MOD))
else:
	print (0)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from itertools import combinations

X,Y=(int(x) for x in input().rstrip('\n').split())
if (X+Y) % 3 != 0:
  print(0)
else:
  t = (X+Y)//3
  if X<t or Y<t:
    print(0)
  else:
    s = abs(X-Y)
    if s==t:
      print(1)
    else:
      a = (t-s) // 2      
      res = t
      for i in range(1,a):
        res = res*(t-i)
        ad = pow(i+1,1000000005,1000000007)%1000000007
        res = res*ad
        res = res%1000000007
      print(res%1000000007)

Submission status: Accepted

Solution code:
def nCr(n, r, mod):
    x, y = 1, 1
    for r_ in range(1, r+1):
        x = x*(n+1-r_)%mod
        y = y*r_%mod
    return x*pow(y, mod-2, mod)%mod
 
x, y = map(int, input().split())
mod = 10**9+7
if (x+y)%3 or 2*x<y or 2*y<x:
    print(0)
else:
    print(nCr((x+y)//3,(2*x-y)//3, mod))

Submission status: Accepted

Solution code:
from functools import reduce
def nCr(n,r,DIV):
  if r<n-r:
    r=n-r
  if r==0:
    return 1
  f=lambda x,y:x*y%DIV
  X=reduce(f,range(n-r+1,n+1))
  Y=reduce(f,range(1,r+1))
  return X*pow(Y,DIV-2,DIV)%DIV

mod = pow(10, 9) + 7
x, y = map(int, input().split())
left, right = 0, 0
a, b = max(x, y), min(x, y)

if (2*b - a) % 3 == 0:
    d, s = a - b, (2*b - a)//3
    p, q = d + s, s
    print(nCr(p+q, p, mod))
else:
    print(0)

Submission status: Accepted

Solution code:
# 解説を参考に作成

# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque

def inverse(a, p):
    """逆元"""
    a_, p_ = a, p
    x, y = 1, 0
    while p_:
        t = a_ // p_
        a_ -= t * p_
        a_, p_ = p_, a_
        x -= t * y
        x, y = y, x
    x %= p
    return x


def dev_mod(a, b, mod):
    """a(= A % mod) / b を mod で割った余り"""
    return (a * inverse(b, mod)) % mod


# from decorator import stop_watch
#
#
# @stop_watch
def solve(X, Y):
    mod = 10 ** 9 + 7
    if (2 * Y - X) % 3 != 0:
        print(0)
        return
    a = round((2 * Y - X) / 3)
    b = Y - 2 * a
    a, b = max(a, b), min(a, b)
    
    if b < 0:
        print(0)
        return

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

    print(ans)


if __name__ == '__main__':
    X, Y = map(int, input().split())
    solve(X, Y)

Submission status: Accepted

Solution code:
mod = 10**9+7
def comb(n, k):
    c = 1
    for i in range(k):
        c *= n - i
        c %= mod
    d = 1
    for i in range(1, k + 1):
        d *= i
        d %= mod
    return (c * pow(d, mod - 2, mod)) % mod
x,y=map(int,input().split())

ans=0

z=x//2

for q in range(z,x+1):
  w=2*q-x
  if w*2+(q-w)==y:
    t=comb(q,w)
    ans+=t
    
  
  
print(ans)

Submission status: Accepted

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

mod = 10**9+7
def comb(n, k):
    c = 1
    for i in range(k):
        c *= n - i
        c %= mod
    d = 1
    for i in range(1, k + 1):
        d *= i
        d %= mod
    return (c * pow(d, mod - 2, mod)) % mod


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

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

# 公式解説解答
# n = (x + y) // 3
# x -= n
# y -= n
# if x < 0 or y < 0:
#     print(0)
#     exit()
# print(comb(x + y, x))

# x = 2a + b
# y = a + 2b
# 連立方程式を解いてa,bを求める
# あとはa,bの同じものを含む順列(a+b)!/a!b!
a = (2 * x - y) // 3
b = (-x + 2 * y) // 3
if a < 0 or b < 0:
    print(0)
    exit()
print(comb((x + y) // 3, a))

Submission status: Accepted

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

mod = 10**9+7
def comb(n, k):
    c = 1
    for i in range(k):
        c *= n - i
        c %= mod
    d = 1
    for i in range(1, k + 1):
        d *= i
        d %= mod
    return (c * pow(d, mod - 2, mod)) % mod


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

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

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

print(comb(x + y, x))

Submission status: Accepted

Solution code:
mod = 10**9+7
MAX_N = 10 ** 6
fact = [1]
fact_inv = [0] * (MAX_N + 4)
for i in range(MAX_N + 3):
  fact.append(fact[-1] * (i + 1) % mod)
fact_inv[-1] = pow(fact[-1], mod - 2, mod)
for i in range(MAX_N + 2, -1, -1):
  fact_inv[i] = fact_inv[i + 1] * (i + 1) % mod
def mod_comb_k(n, k, mod):
  return fact[n] * fact_inv[k] % mod * fact_inv[n - k] % mod
x,y=map(int,input().split())
if (2*x-y)>=0 and (2*y-x)>=0 and (x+y)%3==0:
  print(mod_comb_k((x+y)//3,(2*y-x)//3,mod))
else:print(0)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)
INF = float("inf")

class Modinv:
    def __init__(self, n, mod):
        self.mod = mod
        self.fact = [1]*n
        self.finv = [1]*n
        self.inv  = [1]*n
        for i in range(2,n):
            self.fact[i] = (self.fact[i-1]*i) % self.mod
            self.inv[i]  = self.mod - self.inv[self.mod%i] * (self.mod//i)%self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

    def nPr(self, n, r):
        if n<r:
            return 0
        else:
            return self.fact[n] * self.finv[n-r] % self.mod

    def nCr(self, n, r):
        if n<r:
            return 0
        else:
            return self.fact[n] * (self.finv[r] * self.finv[n-r] % self.mod) % self.mod

    def nHr(self, n, r):
        return self.nCr(n-1+r, n-1)

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

    if (X+Y)%3 != 0:
        print(0)
    else:
        # 操作回数
        n = (X+Y)//3
        # 移動を簡略化, (1,2) => (0,1), (2,1) => (1,0) に
        X -= n
        Y -= n
        # 負の領域には移動不可能
        if X < 0 or Y < 0:
            print(0)
        else:
            modinv = Modinv(10**6+10, 10**9+7)
            print(modinv.nCr(X+Y,X))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import factorial as F
def comInit(mx=510000, mod=pow(10,9)+7):
    fac = [0]*mx
    finv = [0]*mx
    inv = [0]*mx
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2,mx):
        fac[i] = fac[i-1]*i%mod
        inv[i] = mod - inv[mod%i]*(mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod
    return fac, finv

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

x, y = map(int, input().split())
mod = pow(10,9)+7
if (x+y)%3!=0:
    print(0)
else:
    w = (2*y-x)//3
    h = (2*x-y)//3
    if w<0 or h<0:
        print(0)
    else:
        fac, finv = comInit(w+h+1)
        print(com(fac, finv, w+h,w))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict, deque

(x, y), res, MOD = map(int, input().split()), 0, int(1e9) + 7
if (x + y) % 3 == 0:
    a, b = (y * 2 - x) // 3, (x * 2 - y) // 3
    if all([True if x >= 0 else False for x in (a, b)]):
        l, r = 1, 1
        for i in range(a + 1, a + b + 1): l = (l * i) % MOD
        for i in range(1, b + 1): r = (r * i) % MOD
        res = l * pow(r, MOD - 2, MOD)
print(res % MOD)

Submission status: Accepted

Solution code:
mod = 10**9+7
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]


def init(n):
    for i in range(2, n + 1):
        fac.append(fac[-1] * i % mod)
        inv.append(-inv[mod % i] * (mod // i) % mod)
        finv.append(finv[-1] * inv[-1] % mod)


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


X, Y = map(int, input().split())
b = max([X, Y])
s = min([X, Y])
if s - (b-s) < 0 or not (s-(b-s)) % 3 == 0:
    print(0)
    exit()

s_t = (s-(b-s))//3
b_t = (s-(b-s))//3 + (b-s)
a = s_t + b_t
b = b_t
p = 10**9 + 7
init(a)
print(com(a, b, p))

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
m = 666666 + 500
fac = [0] * m
finv = [0] * m
inv = [0] * m


def COMBinitialize(m):
    fac[0] = 1
    finv[0] = 1
    if m > 1:
        fac[1] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2, m):
            fac[i] = fac[i-1] * i % MOD
            inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
            finv[i] = finv[i - 1] * inv[i] % MOD


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


COMBinitialize(m)


def main():
    X, Y = (int(i) for i in input().split())
    if (X+Y) % 3 != 0:
        return print(0)
    ans = COMB((X+Y)//3, X - (X+Y)//3)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class Com:
    def __init__(self, MAX = 1000000, MOD = 1000000007):
        self.MAX = MAX
        self.MOD = MOD
        self._fac = [0]*MAX
        self._finv = [0]*MAX
        self._inv = [0]*MAX
        self._fac[0], self._fac[1] = 1, 1
        self._finv[0], self._finv[1] = 1, 1
        self._inv[1] = 1
        for i in range(2,self.MAX):
            self._fac[i] = self._fac[i - 1] * i % self.MOD
            self._inv[i] = self.MOD - self._inv[self.MOD%i] * (self.MOD // i) % self.MOD
            self._finv[i] = self._finv[i - 1] * self._inv[i] % self.MOD
    
    def com(self, n, k):
        if (n < k):
            return 0
        if (n < 0 or k < 0):
            return 0
        return self._fac[n] * (self._finv[k] * self._finv[n - k] % self.MOD) % self.MOD
a,b = list(map(int,input().split()))
if 2*a-b >= 0 and (2*a-b)%3 == 0 and a-2*((2*a-b)//3) >= 0:
    x = (2*a-b)//3
    y = a-2*x
    com = Com()
    print(com.com(x+y, x))
    exit()
a,b = b,a
if 2*a-b >= 0 and (2*a-b)%3 == 0 and a-2*((2*a-b)//3) >= 0:
    x = (2*a-b)//3
    y = a-2*x
    com = Com()
    print(com.com(x+y, x))
    exit()
print(0)

Submission status: Accepted

Solution code:
x, y = map(int, input().split())
tmp = 2*y - x
if tmp%3 != 0:
    print(0)
    exit()
up = tmp // 3
total = y - up*2 + up

n = total
k = up
mod = 10**9 + 7

#print(n)
#print(k)

if k == 0:
    print(1)
    exit()
try:
    modinv_table = [-1] * (k+1)
    modinv_table[1] = 1
    for i in range(2, k+1):
        modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod
except:
    k = total - up
    modinv_table = [-1] * (k + 1)
    modinv_table[1] = 1
    for i in range(2, k + 1):
        modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod

def binomial_coefficients(n, k):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i + 1]
        ans %= mod
    return ans

print(binomial_coefficients(n, k))

Submission status: Accepted

Solution code:
def bigcmb(N, R, MOD):  # nCr(mod p) #n>=10**7,r<=10**6 #前処理不要
    if (R < 0) or (N < R):
        return 0
    R = min(R, N - R)
    fact, inv = 1, 1
    for i in range(1, R + 1):
        fact = (fact * (N - i + 1)) % MOD
        inv = (inv * i) % MOD
    return fact * pow(inv, MOD - 2, MOD) % MOD


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

if (x + y) % 3 != 0:
    print(0)
else:
    cnt = (x + y) // 3
    print(bigcmb(cnt, x - cnt, mod))

Submission status: Accepted

Solution code:
def bigcmb(N, R, MOD):  # nCr(mod p) #n>=10**7,r<=10**6 #前処理不要
    if (R < 0) or (N < R):
        return 0
    R = min(R, N - R)
    fact, inv = 1, 1
    for i in range(1, R + 1):
        fact = (fact * (N - i + 1)) % MOD
        inv = (inv * i) % MOD
    return fact * pow(inv, MOD - 2, MOD) % MOD


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

if (x + y) % 3 != 0 or (x > 2 * y) or (2 * x < y):
    print(0)
else:
    cnt = (x + y) // 3
    print(bigcmb(cnt, x - cnt, mod))

Submission status: Accepted

Solution code:
def bigcmb(N, R, MOD):  # nCr(mod p) #n>=10**7,r<=10**6 #前処理不要
    if (R < 0) or (N < R):
        return 0
    R = min(R, N - R)
    fact, inv = 1, 1
    for i in range(1, R + 1):
        fact = (fact * (N - i + 1)) % MOD
        inv = (inv * i) % MOD
    return fact * pow(inv, MOD - 2, MOD) % MOD


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

if (x + y) % 3 != 0 or x > 2 * y or 2 * x < y:
    print(0)
else:
    print(bigcmb((x + y) // 3, x - (x + y) // 3, mod))

Submission status: Accepted

Solution code:
def nCr(n,r):
  dividend = 1
  divisor = 1
  MOD = 10**9+7
  d1 = n
  for i in range(1,r+1):
    dividend *= d1
    divisor *= i
    d1 -= 1
    dividend %= MOD
    divisor %= MOD

  return (dividend * pow(divisor, MOD-2, MOD)) % MOD

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

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

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

if n<0 or m<0:
  print(0)
else:
  print(nCr(n+m, n))

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 組合せnCr
def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]



# ここから書き始める
MAX_N = 10**6

fact = [1]
fact_inv = [0]*(MAX_N+4)
for i in range(MAX_N+3):
    fact.append(fact[-1]*(i+1)%MOD)

fact_inv[-1] = pow(fact[-1],MOD-2,MOD)
for i in range(MAX_N+2,-1,-1):
    fact_inv[i] = fact_inv[i+1]*(i+1)%MOD


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


x, y = map(int, input().split())
ans = 0
for i in range(x + 1):
    cnt1 = i
    if (x - cnt1) % 2 != 0 or y - 2 * cnt1 != (x - cnt1) // 2:
        continue
    cnt2 = (x - cnt1) // 2
    ans += mod_comb_k(cnt1 + cnt2, cnt1, MOD)
print(ans % MOD)

Submission status: Accepted

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


S = -X + 2 * Y
T = 2 * X - Y

if S < 0 or T < 0:
    print(0)
    exit()
if S % 3 != 0 or T % 3 != 0:
    print(0)
    exit()

S //= 3
T //= 3


def cmb(n, r, p):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = 1
    for i in range(n, n - r, -1):
        over = over * i % p
    under = 1
    for i in range(1, r + 1):
        under = under * i % p
    inv = pow(under, p - 2, p)
    return over * inv % p


# print(S, T)
ans = cmb(S + T, S, MOD) % MOD
print(ans % MOD)

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
mod = 10**9+7
if (x+y)%3!=0:
  print(0)
  exit()
if 2*min(x,y)<max(x,y):
  print(0)
  exit()
n = (2*x-y)//3
m = (2*y-x)//3
#n+mCm
if n==0 or m==0:
  print(1)
  exit()
def ka(x):
  a = 1
  while x!=1:
    a *= x
    x -= 1
    a%= mod
  return a

ans = (ka(n+m)*pow(ka(m),mod-2,mod)%mod)*(pow(ka(n),mod-2,mod))%mod
print(ans)

Submission status: Accepted

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

MAX = 2 * 10 ** 6 + 1
MOD = 10 ** 9 + 7

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1
for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    
# Inverse factorial
finv = [0] * (MAX + 1)
finv[MAX] = pow(fac[MAX], MOD - 2, MOD)
for i in reversed(range(1, MAX + 1)):
    finv[i - 1] = finv[i] * i % MOD

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

mod = 10 ** 9 + 7
v1 = 2 * Y - X
v2 = 2 * X - Y
if (v1 >= 0 and v1 % 3 == 0 and v2 >= 0 and v2 % 3 == 0):
    a = v1 // 3
    b = v2 // 3
    print(comb(a + b, a))
else:
    print(0)

Submission status: Accepted

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

def mod_inv(n, m):
    return pow(n, m-2, m)

def nCr_mod_m(n, r, m):
    if r < 0 or n < r:
        return 0
    # n!
    fact = fact_prev = 1 # 0! = 1! = 1
    for i in range(2, n+1):
        fact = fact_prev * i % m
        fact_prev = fact
    # n!^(-1)
    fact_inv = [0]*(max(r, n-r)+1)
    fact_inv[0] = fact_inv[1] = 1  # 1 = 1 mod m
    for i in range(2, max(r, n-r)+1):
        fact_inv[i] = fact_inv[i-1] * mod_inv(i, m) % m
    return (fact * fact_inv[r] % m) * fact_inv[n-r] % m

def main():
    X, Y = map(int, input().split())
    if ((X+Y)%3 != 0) or (min(X,Y)*2 < max(X,Y)):
        print(0)
        sys.exit()

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

    print(nCr_mod_m(x+y, x, MOD))
main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
import itertools


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


def main():
    x,y = map(int,input().split())
    if (x+y)%3 !=0:
        print(0)
        exit()
    if x*2 <y or y *2 <x:
        print(0)
        exit()

    n = int((x+y)/3)
    #conbination y-n from N or  x-n from N


    mod = 10 ** 9 + 7  # 出力の制限
    N = 10 ** 6
    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
    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, x-n, mod)

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

Submission status: Accepted

Solution code:
X, Y = map(int, input().split())
P = 10 ** 9 + 7
N = (X+Y) // 3
R = (2 * X - Y) // 3
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

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


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


if (X+Y) % 3 != 0:
    print(0)
else:
    print(cmb_mod(N, R, P))

Submission status: Accepted

Solution code:
import sys
from math import factorial
input = sys.stdin.readline


def log(*args):
    print(*args, file=sys.stderr)


def main():
    x, y = map(int, input().rstrip().split())
    # 全部 i + 1, j + 2が最初だったとする
    # a + 2b = x, 2a + b = y
    # =>
    # a = x - 2b
    # b = y - 2a
    # =>
    # b = y - 2x + 4b
    # 3b = 2x - y
    # b = (2x - y) / 3
    # a = (2y - x) / 3
    if (2 * x - y) % 3 != 0 or (2 * y - x) % 3 != 0:
        print(0)
        return
    a = (2 * x - y) // 3
    b = (2 * y - x) // 3
    if a < 0 or b < 0:
        print(0)
        return
    # (a + b) C min(a, b)
    # => (a + b)! / (min(a, b) ! * (a + b - min(a, b)) !
    mod = 10**9 + 7
    ans = (factorial_mod(a + b, mod) * pow(factorial_mod(min(a, b), mod), mod - 2, mod)
           * pow(factorial_mod(a + b - min(a, b), mod), mod - 2, mod)) % mod
    print(ans)


def factorial_mod(a, mod):
    ans = 1
    for v in range(1, a + 1):
        ans *= v
        ans %= mod
    return ans


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# from math import factorial

def main():
    x, y = map(int, input().split())
    # m = (i+2, j+1)
    # n = (i+1, j+2)
    # x = 2m + n
    # y = m + 2n
    # 2x - y = 3m
    # 2y - x = 3n

    m = (2*x-y) // 3
    n = (2*y-x) // 3
    def cmb(n, r, mod):
        if (r<0 or r>n):
            return 0
        r = min(r, n-r)
        return fac[n] * finv[r] * finv[n-r] % mod

    mod = 10**9+7 #素数制限
    N = m+n
    fac = [1, 1] # 元テーブル
    finv = [1, 1] # 逆元テーブル
    finv_cal = [0, 1] #逆元計算用

    for i in range(2, N + 1):
        fac.append((fac[-1] * i) % mod)
        finv_cal.append((-finv_cal[mod % i] * (mod//i)) % mod)
        finv.append((finv[-1] * finv_cal[-1]) % mod)
    
    # 行き先のx+yが3の倍数でないとたどり着けない。
    if (x+y) % 3 != 0:
        print(0)
    else:
        # m, n どちらかが負かもしくはどちらも0の時
        if m < 0 or n < 0 or (m+n) == 0:
            print(0)
        else:
            ans = cmb(m+n, n, mod)           
            print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#n回,m回　　X =n + 2*m  Y = 2*n + m
X,Y = map(int,input().split())
import numpy as np
from functools import reduce
import math 
a = [[1, 2], [2, 1]]
#次に逆行列を求めます。
mod = pow(10,9)+7

b = np.linalg.inv(a)


Z = np.array([[X],[Y]])

n,m=np.dot(b,Z)
p,q = *n,*m


def comb(n,k,p):
    if k==0:
        return 1
    A = reduce(lambda x,y:x*y%p ,[n-k+1+i for i in range(k)])
    B = reduce(lambda x,y:x*y%p ,[i+1 for i in range(k)])
    return A*pow(B,p-2,p)%p


if p<0 or q<0:
    print(0)
elif not abs(p-round(p))<pow(10,-3) or not abs(q-round(q))<pow(10,-3):
    print(0)
elif p==0 and q==0:
    print(0)
elif p==0:
    print(1)
elif q==0:
    print(1)
else:
    n = int(round(p))
    m = int(round(q))
    ans = comb(n+m,m,mod)

    print(ans%mod)

Submission status: Accepted

Solution code:
a,b = map(int,input().split())
mod = 10**9+7
x = (2*a-b)//3
y = (2*b-a)//3

if (2*a-b)%3 != 0 or (2*b-a)%3 != 0 or 2*b < a or 2*a < b or (a+b)%3 != 0:
    print(0)
    exit()

def comb(n,r):
    fact = 1
    invfact = 1
    for i in range(r):
        fact *= n-i
        fact %= mod
        invfact *= i+1
        invfact %=mod
    return fact*pow(invfact,mod-2,mod)%mod

print(comb(x+y,y))

Submission status: Accepted

Solution code:
x,y = map(int, input().split())
a = 0
b = 0
if x>y:
  while x>y:
    x-=2
    y-=1
    a+=1
if x<y:
  while x<y:
    x-=1
    y-=2
    b+=1
if x == y and x%3==0:
    a+=x//3
    b+=y//3
else:
  print(0)
  exit(0)
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

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

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

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

Submission status: Accepted

Solution code:

mod = 10**9+7
MAX_N = 10 ** 6

fact = [1]
fact_inv = [0] * (MAX_N + 4)
for i in range(MAX_N + 3):
    fact.append(fact[-1] * (i + 1) % mod)

fact_inv[-1] = pow(fact[-1], mod - 2, mod)
for i in range(MAX_N + 2, -1, -1):
    fact_inv[i] = fact_inv[i + 1] * (i + 1) % mod

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

OK = False
X, Y = map(int, input().split())
for i in range(0, max(X, Y)+1):
    if (Y - (X - i*2)*2) == i and X-2*i >= 0:
        x = i
        y = X - i*2
        print(mod_comb_k(x + y, min(x, y), mod))
        OK = True
        break
if not OK:
    print(0)