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
from math import factorial


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
x, y = map(int, sys.stdin.readline().split())

if (x + y)%3 != 0:
    print(0)
    sys.exit()
if y < x/2 and y > 2*x:
    print(0)
    sys.exit()

count1 = int((y-2*x)/(-3))
count2 = int((x-2*y)/(-3))

sum = count1 + count2

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

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

a = cmb(sum,count1,mod)

print(a)

Submission status: Accepted

Solution code:
def solve():
    mod = 10 ** 9 + 7

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

    sum_ = x + y

    q, r = divmod(sum_, 3)
    if r != 0:
        return 0

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

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

    if a < 0 or b < 0:
        return 0

    def cmb(n, r):
        return (fact[n] * finv_t[r] * finv_t[n - r]) % mod

    fact = [1, 1]
    inv_t = [0, 1]
    finv_t = [1, 1]
    for i in range(2, q + 1):
        fact.append((fact[-1] * i) % mod)
        inv_t.append((-inv_t[mod % i] * (mod // i)) % mod)
        finv_t.append((finv_t[-1] * inv_t[-1]) % mod)

    return cmb(q, a)


print(solve())

Submission status: Accepted

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

def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

if (2*y-x)%3!=0 or (2*x-y)%3!=0 or y>2*x or x>2*y:
    print('0')
else:
    a=round((2*y-x)/3)
    b=round((2*x-y)/3)
    n=a+1
    r=b
    ans=comb(n+r-1,r,mod)
    print(int(ans%mod))

Submission status: Accepted

Solution code:
import sys
import math
import bisect
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from operator import mul
from functools import reduce


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


# A
def A():
    r = I()
    print(r * r)
    return


# B
def B():
    N = I()
    s = S()
    if N % 2 != 0:
        print("No")
    elif ''.join(s[:N // 2]) == ''.join(s[N // 2:]):
        print("Yes")
    else:
        print("No")
    return


# C
def C():
    n = I()
    a = [LI() for i in range(n)]
    ans = 0
    for i in range(n):
        for j in range(i + 1, n):
            ans += pow(pow(a[i][0] - a[j][0], 2) + pow(a[i][1] - a[j][1], 2), 0.5)
    avg = ans / (n * (n - 1) / 2)
    print(avg * (n - 1))
    return


# D
def D():
    X, Y = LI()

    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 = X + Y
    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)
    elif X < ((X + Y) // 3) or Y < ((X + Y) // 3):
        print(0)
    else:
        print(cmb((X + Y) // 3, min(X, Y) - ((X + Y) // 3), mod))

    return


# E
def E():
    return


# F
def F():
    return


# Unittest
def resolve():
    D()
    return


# Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
if (x+y)%3!=0:
  print(0)
else:
  z=(x+y)//3
  if x<z or y<z:
    print(0)
  else:
    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
      if n==r:
        return 1
      for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
      return res 
    print(comb(z,x-z)%(10**9+7))

Submission status: Accepted

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

count = 0
if 2 * X - Y >= 0 and 2 * Y - X >= 0:
    if (2*X-Y)%3 == 0 and (2*Y-X)%3 == 0:
        t = (2*X-Y)/3
        s = (2*Y-X)/3
        n = int(t+s)
        r = 0
        if t >= s:
            r = int(s)
        else:
            r = int(t)

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

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

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

        a = cmb(n,r,mod)
        count = a

    else:
        count = 0
else:
    count = 0

print(count)

Submission status: Accepted

Solution code:
MOD = 1000000007

def modinv(a, m):
    b, u, v = m, 1, 0
    while b != 0:
        t = a // b
        a -= t * b
        a, b = b, a

        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u

a, b = 12345678900000, 100000
a %= MOD
#print(a * modinv(b, MOD) % MOD)

def solve(x, y):
    if (x + y) % 3 != 0:
        return 0
    m = (x + y) // 3
    #print(m, (x, y))
    if x < m:
        return 0
    n = m 
    k = x - m
    return C2(n, k)

def C2(n, k):
    d = 1
    for i in range(n-k+1, n+1):
        d *= i 
        d %= MOD
    r = 1
    for i in range(1, k+1):
        r *= i 
        r %= MOD
    return (d * modinv(r, MOD)) % MOD



def test(x, y):
    print((x,y), solve(x,y))
    assert solve(x,y) == solve(y,x)

x, y = map(int, input().split())
if x > y:
    x, y = y, x
answer = solve(x, y) % MOD
print(answer)

Submission status: Accepted

Solution code:
import sys
from math import factorial
sys.setrecursionlimit(100000)

input = sys.stdin.readline

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

mod = 10**9 + 7

def mm(a, b):
    return ((a % mod) * (b % mod)) % mod

def pp(x, y):
    if   y == 0     :
    	return 1
    elif y == 1     : 
    	return x % mod
    elif y % 2 == 0 : 
    	return (pp(x, y/2)**2) % mod
    else            : 
    	return (pp(x, y//2)**2 * x) % mod

def dd(a, b):
    return mm(a, pp(b, mod-2))

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

if (X+Y)%3!=0:
	ans = 0
else:
	nmsum = (X+Y)//3
	nmdif = Y-X
	if (nmsum+nmdif)%2!=0:
		ans = 0
	else:
		n = (nmsum+nmdif)//2
		m = (nmsum-nmdif)//2
		if n<0 or m<0:
			ans = 0
		elif n==0 or m==0:
			ans = 1
		else:
			t = 1
			for i in range(1,n+m+1):
				t = (t*i)%mod
				if i==n: bb = t
				if i==m: cc = t
				if i==n+m: aa = t
			# aa = factorial(n+m)%mod
			# bb = factorial(n)%mod
			# cc = factorial(m)%mod
			ans = aa * modinv(bb,mod) %mod
			ans = ans * modinv(cc,mod) %mod

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def make_nCr_mod(max_n=2 * 10**5, mod=10**9 + 7):
    fact, inv_fact = [0] * (max_n + 1), [0] * (max_n + 1)
    fact[0] = 1
    for i in range(max_n):
        fact[i + 1] = fact[i] * (i + 1) % mod

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

    def nCr_mod(n, r):
        res = 1
        while n or r:
            a, b = n % mod, r % mod
            if a < b:
                return 0
            res = res * fact[a] % mod * inv_fact[b] % mod * inv_fact[a - b] % mod
            n //= mod
            r //= mod
        return res

    return nCr_mod


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

    t1 = 2 * x - y
    t2 = 2 * y - x

    if (t1 % 3) or (t2 % 3) or (t1 < 0) or (t2 < 0):
        print(0)
        return

    c1 = t1 // 3
    c2 = t2 // 3

    nCr = make_nCr_mod(c1 + c2)
    print(nCr(c1 + c2, c1))


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

def main():

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


    if (2*Y-X) % 3 != 0 or (2*X-Y)% 3 != 0:
        return 0
    if (2*Y-X) < 0 or (2*X-Y) < 0: return 0

    n = (2*Y-X) // 3
    m = (2*X-Y) // 3
    # print(n , m)

    if n == 0: return 1
    if m == 0: return 1

    mod = pow(10, 9) + 7

    p1 = 1
    for i in range(1, n+m+1):
        p1 *= i
        p1 %= mod

    p2 = 1
    for i in range(1, n+1):
        p2 *= i
        p2 %= mod

    p3 = 1
    for i in range(1, m+1):
        p3 *= i
        p3 %= mod

    p2 = powfast(p2, mod-2, mod)
    p3 = powfast(p3, mod-2, mod)
    return ((p1 * p2) % mod) * p3 % mod


def powfast(x, y, mod):
    if y == 0: return 1
    if x == 0: return 0
    if y % 2 == 0:
        return pow(powfast(x, y//2, mod), 2) % mod
    else:
        return (x * pow(powfast(x, y//2, mod), 2)) % mod


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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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]]
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m
    
X,Y=map(int,input().split())

if (X+Y)%3==0 and Y<=2*X and Y>=X/2:
    temp=(X+Y)//3
    temp2=X-Y
    x=(temp+temp2)//2
    y=(temp-temp2)//2
    
    m=10**9+7
    ans=1
    for i in range(x+y):
        ans=ans*(i+1)%m
    for i in range(x):
        ans=ans*mod_inv(i+1,m)%m
    for i in range(y):
        ans=ans*mod_inv(i+1,m)%m
    print(ans%m)
    
else:
    print(0)

Submission status: Accepted

Solution code:
import math


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

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

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

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

    return result



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

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

grad = y / x
if grad < 0.5 or grad > 2:
    print(0)
    exit()

turns = int((x + y) / 3)

total = 0
t = (x + y) // 2
u = t - min(x, y)
o = t // 3 - u

total = cmb(turns, o)
total %= num
print(total)

Submission status: Accepted

Solution code:
X, Y = map(int, input().split())
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod
  
mod = 10 ** 9 + 7
  
if (X + Y) % 3 == 0:
  n = (X + Y) // 3 
  if min(X, Y) >= n:
    s = min(X, Y) - n
    ans = comb(n, s, mod)
  else:
    ans = 0
else:
  ans = 0

print(ans)

Submission status: Accepted

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

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

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

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

    return result

x, y = map(int, input().split())
if x < y:
    tmp = y
    y = x
    x = tmp
plus = x + y
if plus % 3 != 0 or x / y > 2:
    print(0)
    exit()

n = int(plus / 3)

center = int(plus / 2)
dist = center - y
pos = int(n / 2) - dist

div = 10**9 + 7


print(int(cmb(n,pos) % div))

Submission status: Accepted

Solution code:
from math import factorial
x, y = map(int, input().split())

if (x + y) % 3 or min(x, y) < (x + y) // 3:
    print(0)
    exit()

n = (x + y) // 3
m = x - n

tn = 10**6
mod = 10 ** 9 + 7
fact = [1, 1] + [0] * tn
finv = [1, 1] + [0] * tn
inv = [0, 1] + [0] * tn

for i in range(2, tn):
    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 com(n, m):
    if n < m: return 0
    if n < 0 or m < 0: return 0
    return fact[n] * (finv[m] * finv[n - m] % mod) % mod

print(com(n, m))

Submission status: Accepted

Solution code:
mod = 10**9 + 7

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

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

t = (x + y) // 3

x -= t
y -= t


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

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

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

a = cmb(x+y,min(x, y),mod)
print(a)

Submission status: Accepted

Solution code:
mod = 1000000007
import sys
sys.setrecursionlimit(1000000)
x, y = map(int, input().split())
a = ((2*x-y)//3)
b = ((2*y-x)//3)
if (x+y) % 3 != 0 or a < 0 or b < 0:
    print(0)
else:
    n = (a + b)%mod
    kaijo = [1, 1]
    for i in range(2, n+1):
        kaijo.append(i*kaijo[i-1]%mod)
    def mul(a, b):
        return ((a % mod) * (b % mod)) % mod
    def power(x, y):
        if y == 0:
            return 1
        elif y == 1:
            return x % mod
        elif y % 2 == 0:
            return power(x, y // 2) ** 2 % mod
        else:
            return power(x, y // 2) ** 2 * x % mod
    def div(a, b):
        return mul(a, power(b, mod - 2))
    n_a = div(kaijo[n], kaijo[a])
    ans = div(n_a, kaijo[n-a])
    print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
from math import sqrt
input = sys.stdin.readline
mod = 10 ** 9 + 7

X, Y = map(int, input().split())
a_3 = -X + 2 * Y
b_3 = 2 * X - Y
if a_3 % 3 != 0 or b_3 % 3 != 0:
    print(0)
    exit()

a = a_3 // 3
b = b_3 // 3

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

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

comb = Combination(1000000)
print(comb(a+b, b))

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(' '))
a = -1
b = -1
 
if (2*Y-X)%3 == 0 and (2*X-Y)%3 == 0:
    a = (2*X-Y)//3
    b = (2*Y-X)//3
 
 
 
if a < 0 or b < 0:
    ans = 0
else:
    ans = cmb(a+b, b)
print(ans % 1000000007)

Submission status: Accepted

Solution code:

n, m = 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

N = 10**6
mod = 10**9+7
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 (n+m) % 3 != 0:
    print(0)
elif m/n > 2 or n/m > 2:
    print(0)
else:
    t = int((n+m)/3)+1
    k = int(min(n-t+1,m-t+1))+1
    print(cmb(t-1,k-1,10**9+7))

Submission status: Accepted

Solution code:

from math import factorial

def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

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

if y < x:
    tmp=y
    y=x
    x=tmp

if (y-x) > x or (x-(y-x))%3 !=0:
    print(0)
    exit()

mo12=0
mo21=0

if y != x:
    tmp=y-x
    y-=2*tmp
    x-=tmp
    mo12=tmp

mo12+=y/3
mo21+=y/3

print(comb(int(mo12+mo21), int(mo21), 1000000007))

Submission status: Accepted

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

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

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

  print(cmb(n, x - n, mod))

Submission status: Accepted

Solution code:
x, y = map(int, input().split())
n, m = 0, 0
for i in range(x+1):
    j = (x - i)/2
    if 2*i + j== y:
        n, m = int(i+j), int(i)
        
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 n == 0 and m == 0:
    a = 0
else:
    a = cmb(n,m)%(10**9+7)
    
print(a)

Submission status: Accepted

Solution code:
mo = 10**9 + 7
def fac(x):
    ans = 1
    for i in range(1,x+1):
        ans *= i
        ans %= mo
    return ans

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)

def modinv(a, m):
    g, x, y = egcd(a, m)
    return x % m

def f():
    x,y = [int(s) for s in input().split()]
    if x > (y*2):
        return 0
    if y > (x*2):
        return 0
    if (2*x-y)%3:
        return 0
    if (2*y-x)%3:
        return 0
    a = (2*x-y)//3
    b = (2*y-x)//3
    if a==0 or b==0:
        return 1
    ar = modinv(fac(a),mo)
    br = modinv(fac(b),mo)
    ans = (((fac(a+b) * ar)%mo)*br)%mo
    return ans


print(f())

Submission status: Accepted

Solution code:
import math
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]]
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m
X,Y = map(int,input().split())
div = 1000000007
if (X+Y)%3 != 0:
    print(0)
else:
    count = (X+Y)//3
    if count > X or count > Y :
        print(0)
    else:
        leftX = X-count
        p = 1
        for i in range(1,count+1):
            p = p*i%div
        for i in range(1,leftX+1):
            p = p*mod_inv(i,div)%div
        for i in range(1,count-leftX+1):
            p = p*mod_inv(i,div)%div
        print(p)

Submission status: Accepted

Solution code:
X,Y = map(int,input().split())
mod = 1000000000+7
if (X+Y)%3 != 0:
    print(0)
    exit()
if X > 2*Y or Y > 2*X:
    print(0)
    exit()
MOD = 10**9 + 7
N = 10**6
fact = [1]*(N+1)
rfact = [1]*(N+1)
r = 1
for i in range(1, N+1):
  fact[i] = r = r * i % MOD
rfact[N] = r = pow(fact[N], MOD-2, MOD)
for i in range(N, 0, -1):
  rfact[i-1] = r = r * i % MOD
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD
Z1 = (X+Y)//3
Z2 = X-Z1
Z3 = Z1 - Z2
print(comb(Z1,Z2))

Submission status: Accepted

Solution code:
MOD = 1000000007

def xGCD(a, b, x, y):
    if (b == 0):
        x[0] = 1
        y[0] = 0
        return a
    x1 = [0]
    y1 = [0]
    gcd = xGCD(b, a%b, x1, y1)
    x[0] = y1[0]
    y[0] = x1[0] - (a//b)*y1[0]
    return gcd

def modfact(n):
    result = 1
    while (n > 1):
        result = (result*n)%MOD
        n -= 1
    return result

def modmult(a, b):
    return (a*b)%MOD

def inverse(a):
    x = [0]
    y = [0]
    xGCD(a, MOD, x, y)
    return x[0]

def bc(n, k):
    return modmult(modmult(modfact(n), inverse(modfact(k))), inverse(modfact(n - k)))

x, y = map(int, input().split())
if (x+y)%3 != 0:
    print(0)
else:
    row = (x+y)//3
    k = x-row
    if (0 <= k and k <= row):
        print(bc(row, k))
    else:
        print(0)

Submission status: Accepted

Solution code:
x, y = map(int, input().split())
a = (2 * y - x) / 3
b = (2 * x - y) / 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 ** 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 a.is_integer() and b.is_integer():
    a = int(a)
    c = int(a + b)
    print(cmb(c, a, mod))
else:
    print(0)

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
if (x+y)%3:
  print(0)
  exit()

n=(x+y)//3

if x<n or 2*n<x:
  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])

    return result

ans = cmb(n, x-n)%((10**9)+7)

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
sys.setrecursionlimit(10**9)

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:
    n_plus_m = (X + Y) // 3
    if X > Y:
        diff = X - Y
    else:
        diff = Y - X
    n = (n_plus_m + diff) // 2 
    print(cmb(n_plus_m, n, mod))
else:
    print(0)

Submission status: Accepted

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

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

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

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

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

#     return result

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



def main(X, Y):
    _X = 2*X - Y
    _Y = -X + 2*Y
    if _X%3!=0 or _Y%3!=0:
        return 0

    X = _X//3
    Y = _Y//3

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

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

    return cmb(X+Y, X, MAX, g1, g2)

print(main(X, Y)%MAX)

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

n = int(((x + y) / 3))
r = min(x, y) - n

if (min(x, y)<n)or((x + y)%3!=0):   
    print(0)
else:
    a = cmb(n, r)%(10**9 + 7)
    print(int(a))

Submission status: Accepted

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


X, Y = map(int, input().split())
l = [(0, 0), (1, 2), (2, 1)]
if X * 2 < Y or Y * 2 < X:
    print(0)
else:
    x = X % 3
    y = Y % 3
    if not (x, y) in l:
        print(0)
    else:  # nCr
        n = (X + Y) // 3
        x = min(X, Y)
        y = max(X, Y)
        r = (n - (y - x)) // 2
        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(n, r, mod))

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

a, b = (2 * X - Y) // 3, (2 * Y - X) // 3
maxf = a + b + 10

if (not ((2 * X - Y) % 3 == 0 and (2 * Y - X) % 3 == 0)) or (a < 0 or b < 0):
    print(0)
    exit()

f, invf = [1] * maxf, [1] * maxf

for i in range(1, maxf):
    f[i] = (f[i - 1] * i) % MOD
invf[maxf - 1] = pow(f[maxf - 1], MOD - 2, MOD)
for i in range(maxf - 1, 0, -1):
    invf[i - 1] = (invf[i] * i) % MOD

comb = lambda a, b: f[a + b] * invf[a] * invf[b] % MOD

print(comb(a, b) % MOD)