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:
inpl = lambda: list(map(int,input().split()))
def inv_mod(a, p):
    p = abs(p)
    a %= p
    stack = []
    p0 = p
    while a > 1:
        d, a, p = p//a, p%a, a
        stack.append(d)
    x, y = 1, 0
    while stack:
        d = stack.pop()
        x, y = y-d*x, x
    return x % p0

def comb_mod(n,k,p):
    ans = 1
    k = min(k,n-k)
    if k < 0:
        return 0
    for i in range(k):
        ans = ans * (n-i) * inv_mod(k-i,p) % p
    return ans

MOD = 10**9+7
X, Y = inpl()
if (X+Y) % 3:
    print(0)
    exit()
N = (X+Y)//3
X -= N
Y -= N
Z = X + Y
print(comb_mod(Z,X,MOD))

Submission status: Accepted

Solution code:
class Combination:
    '''MOD上の
    計算量：階乗・逆元テーブルの作成O(N)
    nCkを求めるO(1)'''

    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [pow(self.fact[i], MOD - 2, MOD) for i in range(n + 1)]
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD



x, y = map(int, input().split())
MOD = 10**9 + 7
comb = Combination(10**6, MOD)

if (x+y) % 3 != 0:
    print(0)
    exit()
    
tmp = (x + y) // 3
diff = abs(x - y)

if tmp < diff:
    print(0)
else:
    k = (tmp - diff) // 2
    print(comb.combination(tmp, k))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
x,y=map(int,input().split())
INF=10**9+7
def modcomb(n,k,m):
    fac=[0]*(n+1)
    finv=[0]*(n+1)
    inv=[0]*(n+1)
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,n+1):
        fac[i]=fac[i-1]*i%m
        inv[i]=m-inv[m%i]*(m//i)%m
        finv[i]=finv[i-1]*inv[i]%m
    return fac[n]*(finv[k]*finv[n-k]%m)%m
if (-x+2*y)%3==0 and (2*x-y)%3==0 and -x+2*y>=0 and 2*x-y>=0:
    a=(-x+2*y)//3
    b=(2*x-y)//3
    ans=modcomb(a+b,a,INF)
    print(ans)
else:
    print(0)

Submission status: Accepted

Solution code:

import sys
x,y=map(int,input().split())
n=(x+y)//3
a,b=-1,-1
if (n*3)!=(x+y):
	print(0)
	sys.exit()
for i in range(n+1):
	#print(i*2+(n-i),i+(n-i)*2)
	if i*2+(n-i)==x and i+(n-i)*2==y:
		a,b=i,n-i
#a:x+1 y+2
#b:x+2 y+1
if a<0 or b<0:
	print(0)
	sys.exit()

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

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

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

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

    return result
print(cmb(a+b,a)%(10**9+7))

Submission status: Accepted

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

if (X+Y) % 3 != 0:
    print(0)
    exit()
n = (X+Y)//3
r = Y-n


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


N = 10**6+100
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(n, r, mod))

Submission status: Accepted

Solution code:
X,Y = map(int,input().split())
p = 2*Y - X
q = 2*X - Y
x = -1
y = -1
e = 10**9 + 7
if p >= 0:
    if p%3 == 0:
        x = p//3
if q >= 0:
    if q%3 == 0:
        y = q//3

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**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

if x == -1 or y == -1:
    ans = 0
else:
    z = x + y
    ans = cmb(z,x,e)
print(ans)

Submission status: Accepted

Solution code:
import math
import sys

sys.setrecursionlimit(10 ** 7)


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

fac = [1]
caf = [1]


def pow(n, p):
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod


n = (x + y) // 3 + 10

for i in range(1, n):
    fac.append((fac[i - 1] * i) % mod)
    caf.append(pow(fac[i], mod - 2))


def ncr(n, r):
    if n < r or r < 0:
        return 0
    return (fac[n] * caf[r] * caf[n - r]) % mod


if (x + y) % 3 != 0:
    print(0)
else:
    n = (x + y) // 3
    r = (2 * x - y) // 3
    print(ncr(n, r))

Submission status: Accepted

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

def chs(s,t,mod):
    nume =  1
    for i in range(s-t+1,s+1):
        nume *= i
        nume %= mod 
    deno = 1
    for i in range(1,t+1):
        deno *= i
        deno %= mod
    deno = pow(deno,mod-2,mod)
    
    return (nume*deno%mod)
if (x+y)%3!=0:
    print(0)
    sys.exit()
a = (x+y)//3
x-=a
y-=a
if x<0 or y<0:###
    print(0)
    sys.exit()
print(chs(x+y,y,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


if (2*Y-X)%3 == 0 and (2*X-Y)%3 == 0:
    a = (2*Y-X)//3
    b = (2*X-Y)//3
    
    mod = 10**9+7 #出力の制限
    N = a+b
    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル

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

else:
    ans = 0
    
print(ans)

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)


flag = True
a = 0
b = 0

if (2*y-x)%3 != 0 or (2*y-x) < 0:
  flag = False
else:
  a = (2*y-x)//3

if (2*x-y) %3 != 0 or (2*x-y) < 0:
  flag = False
else:
  b = (2*x-y)//3

if not flag:
  print(0)
else:
  print(cmb(a+b,a,10**9+7))

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a=inp()
        a-=1
        g[i].append(a)
        g[a].append(i)
    return n,g
def graphm():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(m):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((b,w))
        g[b].append((a,w))
    return n,m,g

def dijkstra(s,n,g): # sからの最短距離 頂点数n
    s -= 1
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while len(que)>0:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d

def combi(x,y):
    a=1
    while x>0:
        a=(a*x)%mod
        x-=1
    z=x-y
    while y>0:
        a=(a*pow(y,mod-2,mod))%mod
        y-=1
    while z>0:
        a=(a*pow(z,mod-2,mod))%mod
        z-=1
    return int(a)
    
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=inpm()
    if x<y:
        x,y=y,x
    if x>2*y:
        print(0)
        return
    d=x-y
    n=(x-2*d)*(1/3)
    if n%1!=0:
        print(0)
        return
    n=int(n)
    a=n+d
    b=n    
    
    res = 1
    for i in range(1,a+b+1):
        res = res*i%mod
    for i in range(1,a+1):
        res = res*mod_inv(i,mod)%mod
    for i in range(1,b+1):
        res = res*mod_inv(i,mod)%mod
    print(res)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

mod = 10**9 + 7

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

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

fac = [1, 1]
inv = [1, 1]
finv = [1, 1]
for i in range(2, a+b+10):
    fac.append(fac[i-1] * i % mod)
    inv.append(mod - inv[mod%i] * (mod//i) % mod)
    finv.append(finv[i-1] * inv[i] % mod)

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



print(nck(a+b, a))

Submission status: Accepted

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

MOD = pow(10, 9) + 7


def my_pow(n, p, m):
    """
    calculate n^p (mod m) effectively
    """
    if p == 0:
        return 1
    elif p%2 == 0:
        return ((my_pow(n, p//2, m)) ** 2) % m
    else:
        return (my_pow(n, p-1, m) * n) % m


def combination(n, r):
    """
    calculate nCr using the factorial table
    return: nCr % MOD
    """
    # prepare the factorial table (0! to n!)
    factorial = [1] * (n+1)
    for i in range(1, n+1):
        factorial[i] = (i * factorial [i-1]) % MOD
    
    numerator = factorial[n]
    denominator = (factorial[n-r] * factorial[r]) % MOD
    # a^p-1 ≡ 1 (mod p) (p: prime)
    # a^p-2 ≡ a^-1
    fermat = my_pow(denominator, MOD-2, MOD)

    return (numerator * fermat) % MOD

    
if not (x+y)%3 == 0:
    print(0)
else:
    minimum = (x+y) // 3
    maximum = x + y - minimum
    if not (minimum <= x <= maximum and minimum <= y <= maximum):
        print(0)
    else:
        n = minimum
        r = y - minimum
        print(combination(n, r))

Submission status: Accepted

Solution code:
from sys import stdin


def input():
    return stdin.readline()[:-1]


def intput():
    return int(input())


def sinput():
    return input().split()


def intsput():
    return map(int, sinput())


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

x , y = intsput()

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

if a >= 0 and b >= 0 and a + 2 * b == x and 2 * a + b == y:
    print(ncr(a + b, b))
else:
    print(0)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


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


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


class Combination:
    def __init__(self, n, mod):

        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)
        self.MOD = mod
        self.N = n
        self.g1 = g1
        self.g2 = g2
        self.inverse = inverse

    def __call__(self, n, r):
        if (r < 0 or r > n):
            return 0
        r = min(r, n-r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.MOD

@mt
def slv(X, Y):
    C = Combination(10**6, 10**9+7)
    M = Mod(10**9+7)
    ans = 0
    for i in range(X+1):
        if (X - i) % 2 != 0:
            continue
        j = (X - i) // 2
        if 2*i + j != Y:
            continue
        ans = M.add(ans, C(i+j, i))

    return ans


def main():
    X, Y = read_int_n()
    print(slv(X, Y))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class combination():
    #素数のmod取るときのみ　速い
    def __init__(self, n, mod):
        self.n = n
        self.fac = [1] * (n + 1)
        self.inv = [1] * (n + 1)
        for j in range(1, n + 1):
            self.fac[j] = self.fac[j - 1] * j % mod

        self.inv[n] = pow(self.fac[n], mod - 2, mod)
        for j in range(n - 1, -1, -1):
            self.inv[j] = self.inv[j + 1] * (j + 1) % mod

    def comb(self, n, r, mod):
        if r > n or n < 0 or r < 0:
            return 0
        return self.fac[n] * self.inv[n - r] * self.inv[r] % mod

def examD(mod):
    X, Y = LI()
    if (X+Y)%3!=0:
        ans = 0
    else:
        N = (X+Y)//3
        if N>Y:
            ans = 0
        else:
            k = (N-(X-Y))//2
            C = combination(N,mod)
            ans = C.comb(N,k,mod)
    print(ans)


import sys,copy,bisect,itertools
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD(mod)

Submission status: Accepted

Solution code:
def main():  
    def cmb(n, r, mod):
            if ( r<0 or r>n ):
                return 0
            r = min(r, n-r)
            return g1[n] * g2[r] * g2[n-r] % mod
    x,y = map(int,input().split())
    d = x + y
    if d%3 == 0:
        a = (2*x-y)//3
        b = (2*y-x)//3
        
        mod = 10**9+7
        N = 10**6
        g1 = [1, 1]
        g2 = [1, 1]
        inverse = [0, 1]        
        for i in range( 2, N + 1 ):
            g1.append( ( g1[-1] * i ) % mod )
            inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
            g2.append( (g2[-1] * inverse[-1]) % mod )
        
        ans = cmb(a+b,a,mod)
        print(ans)
    else:
        print(0)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 10**9+7
fact = [1]*(10**6+1)
for i in range(10**6):
    fact[i+1] = ((i+1)*fact[i])%mod

def comb(n,k):
    return (fact[n]*pow(fact[k],mod-2,mod)*pow(fact[n-k],mod-2,mod))%mod

X,Y = map(int,input().split())
a = 2*Y-X
b = 2*X-Y
ans = 0
if a%3==0 and b%3==0 and a>=0 and b>=0:
    ans = comb((a+b)//3,a//3)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
import functools
import itertools
import math
INF = float('inf')
MOD = 10**9+7

# nCk % mod
def modCom(n, k, mod):
    p, q = 1, 1
    for i in range(n-k+1, n+1):
        p = (p * i) % mod
    for i in range(2, k+1):
        q = (q * i) % mod
    return p * pow(q, mod-2, mod) % mod

X, Y = map(int, input().split())
l, r = -1, X//2
while l+1 < r:
    m = (l+r)//2
    n = X-2*m
    if 2*n+m > Y:
        l = m
    else:
        r = m
m = r
n = X-2*r
if 2*m+n == X and m+2*n == Y:
    print(modCom(n+m, n, MOD))
else:
    print(0)

Submission status: Accepted

Solution code:
#%%
x, y = map(int, input().split())
flag = True
a, b = 0, 0
if x > y:
    tmp = x - y
    a += x - y
    x -= tmp * 2
    y -= tmp
elif y > x:
    tmp = y - x
    a += y - x
    y -= tmp * 2
    x -= tmp
else:
    pass
#print(x, y)

if x % 3 != 0:
    flag = False
if x < 0 :
    flag = False
#print(a, b)
a += (x) //3
b += (x) //3

inf = 10 ** 9 + 7

c = 1
d = 1
for i in range(1, a+b+1):
    c *= i
    c %= inf
for i in range(1, a+1):
    d *= i
    d %= inf
for i in range(1, b+1):
    d *= i
    d %= inf

#print(a, b)
#print(c, d)
ans = c * pow(d, inf-2, inf)
ans %= inf

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

Submission status: Accepted

Solution code:
MOD = 1000000007
fac = finv = inv = None

def init(n):
    global fac, finv, inv
    fac = [0] * n
    finv = [0] * n
    inv = [0] * n
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in xrange(2, n):
        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 com(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

def main():
    x, y = map(int, raw_input().split())
    a = 2 * x - y
    b = 2 * y - x
    if a < 0 or b < 0 or a % 3 or b % 3:
        print 0
        return
    a //= 3
    b //= 3
    init(a + b + 1)
    print com(a + b, a)


main()

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
def main():
    Q = 10**9+7
    X, Y = map( int, input().split())
    if (X+Y)%3 != 0:
        print(0)
        return
    H = (X+Y)//3
    if (X < H) or (Y < H):
        print(0)
        return
    N = X+Y - (X+Y)//3*2
    K = X -N
    L = Y-N
    ans = 1
    s = 1
    t = 1
    for i in range(1, N+1):
        ans *= i
        ans %= Q
    for i in range(1, K+1):
        s *= i
        s %= Q
    for i in range(1, L+1):
        t *= i
        t %= Q
    ans *= pow(s, Q-2, Q)
    ans %= Q
    ans *= pow(t, Q-2, Q)
    ans %= Q
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def mod_cmb(n, r, mod=10 ** 9 + 7):
	assert n >= r >= 0

	def ex_euclid(x, y):
		a, b = 1, 0
		while y != 0:
			a, b = b, (a - x // y * b)
			x, y = y, x % y
		return a

	p = q = 1
	for i in range(n - r + 1, n + 1):
		p *= i
		p %= mod
	for i in range(2, r + 1):
		q *= i
		q %= mod
	p *= ex_euclid(q, mod)
	p %= mod
	return p

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

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
if (x + y) % 3 != 0:
    print(0)
    exit()
if min(x,y) * 2 < max(x,y):
    print(0)
    exit()
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

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

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

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
            result %= (10 ** 9 + 7)

    return result

num = (x + y) // 3
print(cmb(num,min(x,y)-num)%(10 ** 9 + 7))

Submission status: Accepted

Solution code:
class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD


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

MOD = 10 ** 9 + 7

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

if X < Y:
  X, Y = Y, X

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

N = (X + Y) // 3
M = N * 2 - X

com = comb(N + 1, MOD)

print(com.com(N, M))

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

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


# MOD = 998244353

def div_mod(a, b, mod):
    """
    (a // b) % mod
    mod は 3 以上の素数を指定
    フェルマーの小定理より mod p の世界で b^(p-1) は必ず 1 になるので
    b の逆元 (b と掛けると 1 になる数) は b^(p-2)
    :param int a:
    :param int b:
    :param int mod:
    :return:
    """
    return a * pow(b, mod - 2, mod) % mod


def mod_inv(a, mod):
    """
    a の逆元
    :param int a:
    :param int mod:
    :return:
    """
    return pow(a, mod - 2, mod)


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


def mod_invs(max, mod):
    """
    逆元のリスト 0 から max まで
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorial_invs(max, mod):
    """
    階乗 0!, 1!, 2!, ..., max! の逆元
    :param int max:
    :param int mod:
    """
    ret = []
    r = 1
    for inv in mod_invs(max, mod):
        r = r * inv % mod
        ret.append(r)
    return ret


class Combination:
    def __init__(self, max, mod):
        """
        :param int max:
        :param int mod: 3 以上の素数であること
        """
        self._factorials = get_factorials(max, mod)
        self._finvs = factorial_invs(max, mod)
        self._mod = mod

    def ncr(self, n, r):
        """
        :param int n:
        :param int r:
        :rtype: int
        """
        if n < r:
            return 0
        return self._factorials[n] * self._finvs[r] % self._mod * self._finvs[n - r] % self._mod


X, Y = list(map(int, sys.stdin.readline().split()))

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

X, Y = min(X, Y), max(X, Y)
if X * 2 < Y:
    print(0)
    exit()

comb = Combination(max=(X + Y) // 3, mod=MOD)
print(comb.ncr((X + Y) // 3, X - (X + Y) // 3))

# dp = np.zeros((X + 1, Y + 1), dtype=int)
# dp[0][0] = 1
# for x, y in itertools.product(range(X), range(Y)):
#     if x + 1 <= X and y + 2 <= Y:
#         dp[x + 1, y + 2] += dp[x, y]
#     if x + 2 <= X and y + 1 <= Y:
#         dp[x + 2, y + 1] += dp[x, y]
# print(dp)

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
mod=10**9+7
if (x+y)%3:
    print(0)
    exit()
x,y=min(x,y),max(x,y)
sa=y-x
if sa>x:
    print(0)
    exit()
p=(x+y)//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(p,(p-sa)//2)%mod)

Submission status: Accepted

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


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

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


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

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

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

else:
    N = (X+Y) // 3
    x = X - N
    y = Y - N

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

Submission status: Accepted

Solution code:
X, Y = map(int, input().split())
if (X+Y)%3 != 0:
  print(0)
  exit()
N = (X+Y)//3
# C_N_X-N
MAX = 700000
MOD = 1000000007
fac = [0]*MAX
finv = [0]*MAX
inv = [0]*MAX
fac[0] = 1
fac[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
for i in range(2, MAX):
  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 COM(n, k):
  if n < 0 or k < 0 or n < k:
    return 0
  return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD
r = COM(N, X-N)
print(r)

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
if (x+y) % 3 != 0:
  print(0)
elif x < 0 or y < 0:
  print(0)
elif x/y > 2 or y/x > 2:
  print(0)
else:
  n = (x+y) // 3
  m = x - n
  mod = 10**9 + 7
  def inv(x):
    y = 1
    while x != 1:
      y *= mod//x + 1
      y %= mod
      x -= mod%x
    return y
  #print(inv(5))
  ans = 1
  for i in range(m):
    ans *= (n-i)
    ans %= mod
    ans *= inv(m-i)
    ans %= mod
  #print(n,m)
  print(ans)

Submission status: Accepted

Solution code:
mod = 10**9+7

# コンビネーション
def cmb(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NN = 10**6 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

X, Y = map(int, input().split())
if (X+Y)%3 != 0:
    print(0)
else:
    a = (X+Y)//3
    ans = cmb(a, X-a)
    print(ans)

Submission status: Accepted

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

m = 3*10**6 +1 
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

def comb(n,k):
    return (fac[n]*finv[k]%mod)*finv[n-k]%mod

if (X+Y)%3!=0:
    ans = 0
else:
    N = (X+Y)//3
    a = X-N
    b = Y-N
    if a<0 or b<0:
        ans = 0
    else:
        ans = comb(a+b,a)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

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

MOD = 10 ** 9 + 7

if x > y:
    x, y = y, x

z = y - x

if x - z < 0 or (x - z) % 3 != 0:
    print(0)
    exit()

a = (x - z) // 3
b = a + z

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 )

print(cmb(a+b, a))

Submission status: Accepted

Solution code:
[X,Y] = list(map(int,input().split()))
output = 0

Z = X+Y

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

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

if (Z%3==0)and(Z/3<=X)and(Z/3<=Y):
    T = int(Z/3)
    S = abs(int(Z/3)-min(X,Y))
    output = combination(T,S, mod=10**9+7)

print(output)

Submission status: Accepted

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

def mod_inverse(a, p):
    mod = 1
    p_bin = bin(p-2)
    for i in range(len(p_bin) - 1, 1, -1):
        if i == len(p_bin) - 1:
            mul = a
            mul %= p
            mod *= (mul ** int(p_bin[i]))
            mod %= p
        else:
            mul = mul ** 2
            mul %= p
            mod *= (mul ** int(p_bin[i]))
            mod %= p
    return mod

def combination(n, k, p):
    a = 1
    for i in range(n, n - k, -1):
        a *= i
        a %= p
    b = 1
    for i in range(k):
        b *= (i + 1)
        b %= p
    return (a * mod_inverse(b, p)) % p

if (x + y) % 3 != 0:
    print(0)
elif x > y * 2 or y > x * 2:
    print(0)
else:
    total = (x + y) // 3
    a = x - total
    b = total - a
    c = min(a, b)
    print(combination(total, c, mod))

Submission status: Accepted

Solution code:
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
mod=10**9+7
x,y=map(int,input().split())
if (x+y)%3==0 and y>=0.5*x and y<=2*x:
    k=(x+y)//3
    h=y-k
    ans=1
    for i in range(k-h+1,k+1):
        ans*=i
        ans%=mod
    for i in range(1,h+1):
        ans*=mod_inv(i,mod)
        ans%=mod
    print(ans)
else:
    print(0)