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:
def combination(n, k, mod=10**9+7):
    numer = denom = 1
    for i in range(k):
        numer = (numer * (n-i)) % mod
        denom = (denom * (i+1)) % mod
    return (numer * pow(denom, mod-2, mod)) % mod


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

if (X + Y) % 3 == 0:
    a = (2*Y-X) // 3
    b = (2*X-Y) // 3

    if a >= 0 and b >= 0:
        print(combination(a+b, a))
        exit()
print(0)

Submission status: Accepted

Solution code:
import math
import os
import sys
# from fractions import gcd
input = sys.stdin.readline

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

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


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


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

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

    n = int((2 * Y - X) / 3)
    m = int(Y - 2 * n)
    # print(n, m)
    # print(cmb(n+m, min(n, m)))

    for i in range(2, m + 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(m+n, min(n, m), MOD))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

if a<0 or b<0:
  print(0)
  sys.exit()
  
f=[1]
for i in range(1,a+b+1):
    f.append(f[-1]*i%mod)

if a+2*b==x and 2*a+b==y:
    print(f[a+b]*pow(f[a]*f[b],mod-2,mod)%mod)
else:
    print(0)

Submission status: Accepted

Solution code:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

x,y = map(int,input().split())
t = x-y
a = 0
if t > 0:
  a = t
  x -= a*2
  y -= a
elif t < 0:
  a = t*-1
  x -= a
  y -= a*2
if x<0 or x%3 != 0:
  ans = 0
else:
  b = x//3
  a += b
  ans = cmb(a+b,b)
print(ans%1000000007)

Submission status: Accepted

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

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

ans=0
mod=10**9+7
if (X+Y)%3!=0:
  print(ans)
else:
  n=Y-(X+Y)//3
  m=X-(X+Y)//3
  if n<0 or m<0:
    print(ans)
  else:
    print(comb(n+m,n,mod))

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

i = (2*X-Y)//3
j = (2*Y-X)//3

if(  i < 0 or j < 0 or (2*X-Y)%3!=0 or (2*Y-X)%3!=0 ):
    print(0)
else:
    print(cmb(i+j, i) % 1000000007)

Submission status: Accepted

Solution code:
import math
X,Y = map(int,input().split())
a,b = (2*Y-X)/3,(2*X-Y)/3
n = 10**9+7
def cmb(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod
def count():
  if not (a//1 == a and b//1==b):
    return 0
  else:
    ahat = int(a%n)
    bhat = int(b%n)
    return cmb(ahat+bhat,ahat)


print(int(count())%(10**9+7))

Submission status: Accepted

Solution code:
X, Y = map(int, input().split())
cnt = 0
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)
    exit()

x = (2*Y - X) // 3
y = (2*X - Y) // 3
if x < 0 or y < 0 :
  print(0)
  exit()
print(cmb(x+y, x) % (10**9 + 7))

Submission status: Accepted

Solution code:
import math


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

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

    return (numerator * pow(denominator, mod-2, mod)) % mod


X, Y = map(int, input().split())
mod = 10**9 + 7
if (X + Y) % 3 != 0:
    print(0)
    exit()
else:
    n = int((2 * Y - X) / 3)
    m = int(Y - 2 * n)
    if n < 0 or m < 0:
        print(0)
        exit()
    else:
        print(cmb(m+n, n, mod))

Submission status: Accepted

Solution code:
def combination(n, r, mod=10 ** 9 + 7):
	n1, r = n + 1, min(r, n - r)
	numer = denom = 1
	for i in range(1, r + 1):
		numer = numer * (n1 - i) % mod
		denom = denom * i % mod
	return numer * pow(denom, mod - 2, mod) % mod


X, Y = map(int, input().split())
# 例外処理
if (X + Y) % 3 != 0 or not (X <= 2 * Y and Y <= 2 * X):
	print(0)
	exit()

n = (X + Y) // 3

r = Y - n # 差
print(combination(n, r))

Submission status: Accepted

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

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.is_integer() and a>=0 and b>=0:
    print(cmb(int(a+b),int(a))%((10**9)+7))
else:
    print(0)

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

if X == Y // 2 or Y == X//2:
    print(1)
    exit(0)

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

diff = X - Y
x = X - 2*diff

if x % 3 != 0:
    print(0)
    exit(0)
else:
    k = x // 3
    for i in range(2, N + 1):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

    ans = cmb(2*k+diff, k, mod)
    print(ans)

Submission status: Accepted

Solution code:
import sys


def alg_combination_mod(n, r, mod):
    r = min(n - r, r)
    if r == 0:
        return 1
    else:
        denominator = 1
        for i in range(n, n - r, -1):
            denominator = (denominator * i) % mod
        molecule = 1
        for i in range(1, r + 1):
            molecule = (molecule * i) % mod
        return denominator * pow(molecule, mod - 2, mod) % mod


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    x, y = list(map(int, readline().split()))
    if (x + y) % 3 == 0:
        t = (x + y) // 3
        for i in range(0, t + 1):
            tx = i * 2 + (t - i)
            ty = i + (t - i) * 2
            if tx == x and ty == y:
                print(alg_combination_mod(t, i, mod))
                exit()
        print(0)
    else:
        print(0)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush,heapify
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

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

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

n = (2*y - x)//3
m = (2*x -y)//3
if n<0 or m<0:
    print(0)
    exit()
print(comb(n+m,min(n,m),MOD))

Submission status: Accepted

Solution code:
M = 10 ** 9 + 7

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

r = 0
if (x + y) % 3 == 0:
  a, b = (2 * y - x) // 3, (2 * x - y ) // 3
  if a >= 0 <= b:
    f = [1]
    for i in range(1, a + b + 1):
      f.append(f[-1] * i % M)
    r = f[a + b] * pow(f[a] * f[b], M - 2, M) % M
print(r)

Submission status: Accepted

Solution code:
import sys
import math
sys.setrecursionlimit(200000)
MOD = 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)を求める。(aとmは互いに素であることが前提)


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


def main():
    X, Y = map(int, input().split())
    if (X + Y) % 3 != 0:
        print(0)
        exit()
    else:
        m = (2 * X - Y) // 3
        n = (2 * Y - X) // 3
        if m < 0 or n < 0:
            print(0)
            exit()
        else:
            res = 1
            for i in range(1, n + m + 1):
                res = res * i % MOD
            for i in range(1, n + 1):
                res = res * mod_inv(i, MOD) % MOD
            for i in range(1,m + 1):
                res = res * mod_inv(i, MOD) % MOD
            print(res)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

x,y = map(int,input().split())
n = 0
mod = 10**9 + 7
mx = 700000
fac = [0]*mx
fin = [0]*mx
inv = [0]*mx

if ((x+y) % 3 != 0):
    print("0")
    exit()
n = (2*y-x)//3
m = (2*x-y)//3

if (n<0)|(m<0):
    print("0")
    exit()

# nCr mod p を求めるのに必要な前処理
fac[0] = fac[1] = 1
fin[0] = fin[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
    fin[i] = fin[i-1] * inv[i] % mod

print(fac[n+m]*((fin[n]* fin[m])%mod) % mod)

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)

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
    P = 10**9 + 7
    N = max(q,r)+2
    inv_t = [0]+[1]
    for i in range(2,N):
        inv_t += [inv_t[P % i] * (P - int(P / i)) % P]
    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 combination(n, k, p):
    numerator = 1
    for i in range(k):
        numerator = (numerator * (n-i)) % p
 
    denominator = 1
    for i in range(1, k+1):
        denominator = (denominator * i) % p
 
    return (numerator * pow(denominator, p-2, p)) % p
 
 
X, Y = map(int, input().split())
 
a = (2*Y-X) / 3
b = (2*X-Y) / 3
 
if a >= 0 and b >= 0 and a == int(a) and b == int(b):
    a = int(a)
    b = int(b)
 
    print(combination(a+b, a, 10**9+7))
else:
    print(0)

Submission status: Accepted

Solution code:
M = 10 ** 9 + 7

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

r = 0
if (x + y) % 3 == 0:
  a, b = (2 * y - x) // 3, (2 * x - y ) // 3
  if a >= 0 <= b:
    n = a + b + 1
    f = [1] * n
    for i in range(1, n):
      f[i] = f[i - 1] * i % M
    r = f[a + b] * pow(f[a] * f[b], M - 2, M) % M
print(r)

Submission status: Accepted

Solution code:
def cmb(n, r, prime):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n % prime

    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] = numerator[k - offset] // pivot
                denominator[k] = denominator[k] // pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= numerator[k]
    
    result = result % prime
    return result


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

ans = 0

if (x + y) % 3 == 0 and 2*x - y >= 0 and 2*y - x >= 0:
    a = (x + y) // 3
    b = (2*x - y) // 3
    ans = cmb(a,b, pow(10,9) + 7)
    #ans = mod_combination(a,b,pow(10,9) + 7)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class FactInvMOD:
    """ 階乗たくさん使う時用のテーブル準備 """

    def __init__(self, MAX, MOD):
        """ MAX：階乗に使う数値の最大以上まで作る """
        
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD
        # 階乗テーブル
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        # 階乗の逆元テーブル
        inverse = [1] * MAX
        # powに第三引数入れると冪乗のmod付計算を高速にやってくれる
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, 0, -1):
            # 最後から戻っていくこのループならMAX回powするより処理が速い
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse
    
    def nCr(self, n, r):
        """ 組み合わせの数 (必要な階乗と逆元のテーブルを事前に作っておく) """

        if n < r: return 0
        # 10C7 = 10C3
        r = min(r, n-r)
        # 分子の計算
        numerator = self.fact[n]
        # 分母の計算
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

    def nPr(self, n, r):
        """ 順列 """

        if n < r: return 0
        return self.fact[n] * self.inv[n-r] % self.MOD

    def nHr(self, n, r):
        """ 重複組み合わせ """

        # r個選ぶところにN-1個の仕切りを入れる
        return self.nCr(r+n-1, r)

x, y = MAP()

x, y = min(x, y), max(x, y)
sm = x + y
if sm % 3 != 0:
    print(0)
    exit()
if y - x > sm // 3:
    print(0)
    exit()

# 連立方程式から式変形
a = (2*y-x) // 3
b = (2*x-y) // 3

fim = FactInvMOD(a+b, MOD)
print(fim.nCr(a+b, a))

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x)
        else:
            return ModInt(self.x + other)

    __radd__ = __add__
        
    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x)
        else:
            return ModInt(self.x - other)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x)
        else:
            return ModInt(other - self.x)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x)
        else:
            return ModInt(self.x * other)

    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, mod-2,mod))
        else:
            return ModInt(self.x * pow(other, mod - 2, mod))
            
    def __rtruediv(self, other):
        if isinstance(other, self):
            return ModInt(other * pow(self.x, mod - 2, mod))
        else:
            return ModInt(other.x * pow(self.x, mod - 2, mod))
            

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, mod))
        else:
            return ModInt(pow(self.x, other, mod))
            

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))
class BigCombination(object):

    def __init__(self, mod: int=10**9+7, max_n: int=5*(10**6)):
        fac, inv=[1], []
        fac_append, inv_append=fac.append, inv.append

        for i in range(1, max_n+1):
            fac_append(fac[-1] * i % mod)

        inv_append(pow(fac[-1], mod-2, mod))

        for i in range(max_n, 0, -1):
            inv_append(inv[-1] * i % mod)

        self.mod, self.factorial, self.inverse=mod, fac, inv[::-1]

    def get_combination(self, n, r):
        if n < r:
            return 0
        return self.factorial[n] * self.inverse[r] * self.inverse[n-r] % self.mod

    def get_permutation(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0

        if n==r:
            return 1
        return self.factorial[n] * self.inverse[n-r] % self.mod
        

def main():
    
    X,Y = MI()
    if (X+Y)%3 != 0:
        print(0)
        return 
    S = X+Y
    X-=S//3
    Y-=S//3
    if X<0 or Y<0:
        print(0)
        return 
    B = BigCombination()
    ans = B.get_combination(X+Y,X)
    print(ans)

if __name__ == '__main__':
    main()

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

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

    for i in range(1,r+1):
        ans*=inv_t[i]
        ans%=10**9+7
            
            
    print(ans)

Submission status: Accepted

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

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

    return (numerator * pow(denominator, p-2, p)) % p


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

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

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

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

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce

mod = 10**9+7

def combination(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod


x, y = map(int, input().split())
if (2*y - x) % 3 != 0:
	print(0)
	exit()

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

a = (2*y - x) // 3
b = y - 2 * a
print(combination(a+b, a))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC145 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

x,y = LI()
fact = [1]*(10**6+1)
for i in range(1,10**6+1):
    fact[i] = i*fact[i-1]
    fact[i] %= mod

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

n,m = (2*x - y)/3,(2*y - x)/3
if n < 0 or m < 0:
    print(0)
    quit()
if n % 1 == 0 and m % 1 == 0:
    n = int(n)
    m = int(m)
    ans = fact[n+m]*pow(fact[n],mod-2,mod)*pow(fact[m],mod-2,mod)
    ans %= mod
    print(ans)
else:
    print(0)

Submission status: Accepted

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

# sys.setrecursionlimit(int(2000000))
def main():
    X, Y = [int(n) for n in input().split()]
    if (2 * Y - X) % 3 != 0 or (2 * X - Y) % 3 != 0:
        print(0)
        return
    i = (2 * Y - X)//3
    j = (2 * X - Y)//3
    print(combinations_count(i+j, min(i,j),int(1e9+7)))

def combinations_count(n, k, M):
    if k == 0:
        return 1
    fn = 0
    fk = 0
    fnk = 0
    cur = 1
    M = int(1e9+7)
    for i in range(1, n+1):
        cur = (cur * i) % M
        if i == n:
            fn = cur
        if i == n-k:
            fnk = cur
        if i == k:
            fk = cur

    return (fn * (modpow(fk , (M-2), M)) * modpow(fnk , (M-2), M))%M
def modpow(a,b,M):
    if b == 1:
        return a % M
    if b % 2 == 1:
        return (modpow(a,(b-1)//2,M)**2 * a)%M
    return (modpow(a,b//2,M) ** 2) % M 
main()

Submission status: Accepted

Solution code:
import numpy as np
import math
input1 = list(map(int,input().split()))

X = input1[0]
Y = input1[1]

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

if Y<X/2:
  print(0)
  exit()

if Y>X*2:
  print(0)
  exit()

s = int((2*X-Y)/3)
t = int((-X+2*Y)/3)

n = s+t
r = min(s,t)

def comb(n,k,p):
  if n==0 or k==0: return 1

  a=1
  for i in range(1,n+1):
    a*=i
    if a >= p:
      a = a%p

  b=1
  for i in range(1,k+1):
    b*=i
    if b >= p:
      b = b%p

  c=1
  for i in range(1,n-k+1):
    c*=i
    if c >= p:
      c = c%p

  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p


ans = comb(n,r,10**9+7)
print(ans)

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
mod=10**9+7
n_max=10**6+1
F=[0]*(n_max+1)
F[0]=1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
def comb(x,y):
  return (F[x]*pow(F[x-y],mod-2,mod)*pow(F[y],mod-2,mod))%mod
a,b=2*y-x,2*x-y
if a<0 or b<0:
  print(0)
elif a%3!=0 or b%3!=0:
  print(0)
else:
  a//=3
  b//=3
  print(comb(a+b,a))

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce
def ncr(n, r):
    r = min(r, n - r)
    if r == 0: return 1;
    if r == 1: return n;
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i in range(r)]
    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] //= pivot
                denominator[k] //= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1: 
            result *= numerator[k]
    return result%(10**9+7)

x, y = map(int, input().split())
if (y+x)%3 != 0 or y > 2*x or x > 2*y:
  print("0")
else:
  n = (y+x)//3
  r = (n-abs(x-y))//2
  a = ncr(n,r)
  print(a)

Submission status: Accepted

Solution code:
def combination(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod
    
x,y = map(int,input().split())


if (x+y)%3 != 0 or not(x <= 2*y and y <= 2*x):
    print(0)
    exit()
else:
    s = (x+y)//3
 
t = min((x-s),(y-s))

print(combination(s,t))

Submission status: Accepted

Solution code:
a = list(map(int, input().split()))
import sys
sys.setrecursionlimit(100000)

if (2*a[0]- a[1])%3 != 0:
    print(0)
else:
    if (2*a[1] - a[0])%3 != 0:
        print(0)
    else:
        if 2*a[0]-a[1]<0 or 2*a[1]-a[0]< 0:
            print(0)
        else:
            x = (2*a[1] - a[0])//3
            y = (2*a[0]- a[1])//3
            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
        
            print((cmb(x+y,x))%(10**9 + 7))

Submission status: Accepted

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

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

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

Submission status: Accepted

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

X, Y = map(int, input().split())
if (X+Y) % 3 != 0 or not (X <= 2*Y and Y <= 2*X):
    print(0)
    exit()

n = (X+Y) // 3
r = Y - n
#print(n, r)
print(combination(n, r))