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:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
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 )

x, y = map(int, input().split())
if (x + y) % 3 != 0:
    print(0)
else:
    n = (x + y) // 3
    print(cmb(n, x - n, mod))

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 = X + Y
C21 = 0
C12 = 0

if N % 3 != 0 or X > 2*Y or Y > 2*X:
  print(0)
else:
  while N != 0:
    if X >= Y:
      C21 += 1
      X -= 2
      Y -= 1
      N -= 3
    else:
      C12 += 1
      X -= 1
      Y -= 2
      N -= 3
  a = cmb(C21 + C12, C21)
  print(a % (10**9 + 7))

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

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 (x + y) % 3 == 0:
    n = (x + y) // 3
    k = x - n
    print(cmb(n, k, mod) % (10**9 + 7))
else:
    print(0)

Submission status: Accepted

Solution code:
import operator as op
from functools import reduce



def fact(n):
    x = n
    t = 1
    while(x>0):
        t *= x
        t %= (10**9+7)
        x -= 1
    return t



valid = True
n = sorted([int(i) for i in input().split()])
a = n[0]
b = n[1]
x = 0
y = 0

x += b-a
t = a
a -= b-a
b -= 2*(b-t)

if(a>=0 and b>=0 and a%3==0):
    x += a//3
    y += a//3
else:
    valid = False

if(valid):
    print ((fact(x+y)*pow(fact(x)*fact(y), 10**9+5, 10**9+7)) % (10**9+7))
else:
    print(0)

Submission status: Accepted

Solution code:
from numpy.linalg import solve
mod = 10**9+7
x,y=map(int,input().split(' '))
left = [[1,2],
        [2,1]]
right = [x,y]

A=solve(left,right)
ax,ay=float(A[0]),float(A[1])
if not 0.5 <= y/x <= 2:
    print(0)
    exit()
if not float.is_integer(ax) or not float.is_integer(ay):
    print(0)
    exit()
ax,ay=int(ax),int(ay)
fac=[0 for i in range(ax+ay+1)]
inv=[0 for i in range(ax+ay+1)]
finv=[0 for i in range(ax+ay+1)]
fac[0] = 1
fac[1] = 1
finv[0]=1
finv[1]=1
inv[1] = 1
for i in range(2,ax+ay+1):
    fac[i] = fac[i-1]*i%mod
    inv[i] = mod-inv[mod%i]*(mod//i)%mod
    finv[i]= finv[i-1] * inv[i]%mod
ans = fac[ax+ay]*(finv[ax]*finv[ay])
ans %= mod
print(int(ans))

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 = 666666
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 (X + Y) % 3 != 0:
    print(0)
else:    
    bg = max(X, Y)
    sm = min(X, Y)

    z = (bg + sm) // 3
    a = z - (z * 2 - bg)
    b = z - a
    
    print(cmb(a+b,a,mod))

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

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 )

def is_integer(n):
    try:
        float(n)
    except ValueError:
        return False
    else:
        return float(n).is_integer()

X,Y = map(int,input().split())
a = (2*Y-X)/3
b = (2*X-Y)/3
if (X == 0 or Y == 0):
    print(0)
    exit()
if is_integer(a):
    a = (2*Y-X)//3
else:
    print(0)
    exit()
if is_integer(b):
    b = (2*X-Y)//3
else:
    print(0)
    exit()
n = a+b
mod = 10**9+7 
ans = cmb(n,a,mod)
print(ans)

Submission status: Accepted

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

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

if max(x,y) / min(x,y) > 2:
    print(0)
    exit()

n = (x + y) // 3
xn = (2*x - y) // 3
yn = n - xn

fac = [1] * (n+1)
finv = [1] * (n+1)
inv = [1] * (n+1)
def com_init(n):
    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
com_init(n)
def solve(n, k):
    return fac[n] * (finv[k] * finv[n - k] % M) % M

ans = solve(n, yn)
print(ans)

Submission status: Accepted

Solution code:
import math
MOD = 1000000000+7
X, Y = map(int, input().split())

if ((2*Y-X)%3 != 0) or ((2*X-Y)%3 != 0) or (2*Y-X) < 0 or (2*X-Y) < 0:
    print(0)
else:
    x = (2*Y-X) // 3
    y = (2*X-Y) // 3
    fac_list = [None for _ in range(x+y+2)]
    inv_fac_list = [None for _ in range(x+y+2)]

    fac_list[0] = 1
    for i in range(1, x+y+2):
        fac_list[i] = i * fac_list[i-1] % MOD

    inv_fac_list[x+y+1] = pow(fac_list[x+y+1],(MOD - 2), MOD)
    for i in range(x+y, -1, -1):
        inv_fac_list[i] = inv_fac_list[i+1] * (i+1) % MOD

    print((fac_list[x+y] * inv_fac_list[x] * inv_fac_list[y]) % MOD)

Submission status: Accepted

Solution code:
import math

N = 10 ** 9 + 7
X, Y = map(int, input().split())
B3 = 2 * X - Y
if B3 % 3:
    print(0)
    exit()
B = B3 // 3
A = X - 2 * B
if A < 0 or B < 0:
    print(0)
    exit()

# count = 1
# for i in range(A + 1, A + B + 1):
#     count *= i
# for i in range(1, A + 1):
#     count //= i
# print(count % N)

# def combinations_count(n, r):
#     return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
#
# print(combinations_count(A + B, A) % N)

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

Submission status: Accepted

Solution code:
# 2019/11/16

import math
mod=10**9+7
X,Y=map(int,input().split())

x=(2*X-Y)/3
y=X-2*x
if x!=int(x) or y!=int(y):
    print(0)
    exit()
else:
    x=int(x)
    y=int(y)

def cmb(n,r,mod=10**9+7):
    fac=[1,1]
    for i in range(2,n+1):
        fac.append(fac[i-1]*i%mod)
    ret=fac[n]*pow(fac[r]*fac[n-r]%mod,mod-2,mod)%mod
    return ret

if x<0 or y<0:
    print(0)
    exit()

n=x+y
r=min(x,y)

ans=cmb(n,r)
if x==0:
    if Y==2*y and X==Y//2:
        print(ans)
    else:print(0)
elif y==0:
    if X==2*x and Y==X//2:
        print(ans)
    else:print(0)
else:
    print(ans)

Submission status: Accepted

Solution code:
#cmb
mod=10**9+7
MAX=10**6

g1=[1,1]
g2=[1,1]
for i in range(2,MAX+1):
    num_1=g1[-1]*i%mod
    g1.append(num_1)
    g2.append(pow(num_1,mod-2,mod))
    
def cmb(n,r,MOD):
    return g1[n]*g2[r]*g2[n-r]%MOD

x,y=map(int,input().split())
ans=0
for k in range(y//2+1):
    l=y-2*k
    if l>=0 and k+2*l==x:
        ans=(ans+cmb(k+l,k,mod))%mod
print(ans)

Submission status: Accepted

Solution code:
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

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

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

x,xm = divmod(X*2-Y, 3)
y,ym = divmod(-X+Y*2, 3)
if (xm == 0) & (ym==0)& (x>=0) & (y>=0):
    print(combination(x+y, x, mod))
else:
    print(0)

Submission status: Accepted

Solution code:
class Combination:
    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


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

mod = 10**9+7
ans_list = []

x_list = []

for i in range(0, x//2+1):
    x_list.append([i, x-2*i])

for g,l in x_list:
    if (g+2*l)==y:
    	ans_list.append([g,l])

ans=0
A = Combination(10**6, mod)
for g,l in ans_list:
    ans += A(g+l,l)

print(ans)

Submission status: Accepted

Solution code:
import os

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

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

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range(2, MAX + 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())
m = x + y
if m % 3 != 0:
    print(0)
    os.sys.exit()

n = int(m / 3)
k = x - n + 1

print(cmb(n, k-1))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)

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

mod = int(10**9 + 7)

res = 0

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

N = 0
M = 0
if X <= Y:
    N += X
    M += Y
else:
    N += Y
    M += X

f = [1]
for i in range(N):
    f.append(f[i]*(i+1)%mod)

def comb(A,B,mod):
    if A >= B:
        temp = f[A] * pow(f[B],mod-2,mod) * pow(f[A-B],mod-2,mod) % mod
    else:
        temp = f[B] * pow(f[A],mod-2,mod) * pow(f[B-A],mod-2,mod) % mod
    return temp

def perm(A,B,mod):
    return f[A+B] * pow(f[A],mod-2,mod) * pow(f[B],mod-2,mod) % mod

for i in range(N):
    role1 = i + 1
    role2 = int((N - role1) / 2)
    roles = role1 + role2
    temp1 = role1 + role2 * 2
    temp2 = role1 * 2 + role2
    if (temp1 == N) & (temp2 == M):
        res += perm(role1,role2,mod)

    res %= mod




print(res)

Submission status: Accepted

Solution code:
import math
MOD = 1000000000+7
X, Y = map(int, input().split())

if ((2*Y-X)%3 != 0) or ((2*X-Y)%3 != 0) or (2*Y-X) < 0 or (2*X-Y) < 0:
    print(0)
elif 2 *Y == X or 2 * X == Y:
    print(1)
else:
    x = (2*Y-X) // 3
    y = (2*X-Y) // 3
    fac_list = [None for _ in range(x+y+2)]
    inv_fac_list = [None for _ in range(x+y+2)]

    fac_list[0] = 1
    for i in range(1, x+y+2):
        fac_list[i] = i * fac_list[i-1] % MOD

    inv_fac_list[x+y+1] = pow(fac_list[x+y+1],(MOD - 2), MOD)
    for i in range(x+y, 0, -1):
        inv_fac_list[i] = inv_fac_list[i+1] * (i+1) % MOD

    print((fac_list[x+y] * inv_fac_list[x] * inv_fac_list[y]) % MOD)

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 = 2*10**6//3 + 1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
x, y = map(int,input().split())

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 = 0
if (x + y)% 3 == 0:
    movtot = (x+y)//3
    movx = x - movtot

    ans = cmb(movtot,movx,mod)
    
print(ans)

Submission status: Accepted

Solution code:

x, y = map(int, input().split())
PRIME = 10 ** 9 + 7
if (x + y) % 3 == 0:
    n = (x + y) // 3
    if x >= n and y >= n:
        up = 2 * n - x
        factorial = 1
        for i in range(1, n + 1):
            factorial *= i
            factorial %= PRIME
        inv = pow(factorial, PRIME - 2, PRIME)
        invs = [1 for _ in range(n + 1)]
        invs[n] = inv
        for i in range(n, min(n - up, up), -1):
            inv *= i
            inv %= PRIME
            invs[i - 1] = inv
        print((factorial * invs[n - up] * invs[up]) % PRIME)
    else:
        print(0)
else:
    print(0)

Submission status: Accepted

Solution code:
import sys
mod = 10**9+7
X, Y = map(int, input().split())
if (X+Y) % 3 != 0:
	print(0)
	sys.exit()

tot = (X+Y) // 3

x = X - tot
y = tot - x

if x < 0:
	print(0)
	sys.exit()

if x == 0 or y == 0:
	print(1)
	sys.exit()

ans = 1
for i in range(y+1, tot+1):
	ans *= i
	ans %= mod

for i in range(1,x+1):
	ans *= pow(i, mod-2, mod)
	ans %= mod

print(ans%mod)

Submission status: Accepted

Solution code:
p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x%p
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
A = [1 for _ in range(10**6+1)]
for i in range(1,10**6+1):
    A[i] = (A[i-1]*i)%p
B = [1 for _ in range(10**6+1)]
B[10**6] = pow(A[10**6],p-2)
for i in range(10**6-1,1,-1):
    B[i] = (B[i+1]*(i+1))%p

X,Y = map(int,input().split())
if (X+Y)%3!=0:
    cnt = 0
else:
    k = (X+Y)//3
    if X>Y:
        X,Y = Y,X
    n = X-k
    if X<k:
        cnt = 0
    else:
        cnt = (((A[k]*B[n])%p)*B[k-n])%p
print(cnt)

Submission status: Accepted

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

# https://qiita.com/derodero24/items/91b6468e66923a87f39f#既存ツールを用いた手法３評価-
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)


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

dP = dict()
vQ = []

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

N = (X+Y)//3
K = X - N
nCk = cmb(N,K,MOD)

print(nCk)

Submission status: Accepted

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

ans = 0 
mod = 10**9 + 7 

lst = list(map(int,input().split()))
x = lst[0]
y = lst[1]

a = (2*y-x)/3
b = (2*x-y)/3
N = 10**6
g1 = [1, 1]  
g2 = [1, 1]  
inverse = [0, 1]  

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

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

#a = cmb(6,3,mod)
#print(a)

if a.is_integer() and b.is_integer():
    a = int(a)
    b = int(b)
    ans = cmb(a+b,b,mod)
    print(ans)
else:
    print(0)

Submission status: Accepted

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


MOD = 10**9 + 7

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

pascal_depth = int((X + Y) / 3)  # パスカルの三角形に当たるn
x, y = int((X + Y) * 2 / 3), (X + Y) / 3
pascal_k = x - X  # 端からいくつずれているか

if pascal_k > pascal_depth / 2:
    pascal_k = pascal_depth - pascal_k

# ans = 1
# # for k in range(int(pascal_k), 0, -1):
# #     ans *= pascal_depth
# #     # print(ans)
# #     pascal_depth -= 1
# #     if ans > MOD:
# #         ans %= MOD

# # for k in range(int(pascal_k), 0, -1):
# # フェルマーの少定理jを使ってみる
# for i in range(1, int(pascal_depth) + 1):
#     ans *= i
#     if ans > MOD:
#         ans %= MOD

# from math import factorial
# # k_fact = factorial(pascal_k)
# k_fact = 1
# # k_fact
# for i in range(1, pascal_k + 1):
#     k_fact *= i
#     if k_fact > MOD:
#         k_fact %= MOD
# ans *= k_fact**(MOD - 2) % MOD
# # nk_fact = factorial(pascal_depth - pascal_k)
# nk_fact = 1
# for i in range(1, int(pascal_depth - pascal_k) + 1):
#     nk_fact *= i
#     if nk_fact > MOD:
#         nk_fact %= MOD

# ans *= nk_fact**(MOD - 2) % MOD


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 = pascal_depth
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(pascal_depth, pascal_k, mod)
print(a)

Submission status: Accepted

Solution code:
import sys


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 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル


x, y = [int(_) for _ in input().split()]
n = 1500000
p = 10**9+7
l = []
for i in range(0, n*3//2+1, 3):
    l.append(i)

if x/2 <= y <= 2*x:
    for i in l:
        if y == i - x:
            t = i//3
            N = t
            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(t,x-t,10**9+7))
            sys.exit()
print(0)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
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 #出力の制限
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 )
def print_ans(X, Y):
    """Test Case
    >>> print_ans(3, 3)
    2
    >>> print_ans(2, 2)
    0
    >>> print_ans(999999, 999999)
    151840682
    """
    A = np.array([[1, 2],[2, 1]])
    B = np.array([X, Y])
    X = np.linalg.solve(A, B)
    if X[0].is_integer() and X[1].is_integer() :
        # ans1 = factorial(X[0] + X[1])
        # ans2 = factorial(X[0])
        # ans3 = factorial(X[1])
        # mod =  (10**9+7)
        # print((ans1 // ans2 * ans3 ) % mod)
        print(cmb(int(X[0] + X[1]),int(X[0]),mod))
        # print(math.factorial(X[0] + X[1]) // (math.factorial(X[0]) * math.factorial(X[1])))
    else:
        print("0")


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

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

max_diff = min(X,Y)
if (X+Y) % 3 == 0:
  n = (X + Y) // 3
  k = max_diff - n
  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(n,k,mod)
else:
  ans = 0

print(ans)

Submission status: Accepted

Solution code:
import math

def comb(n, k, MOD, N):
    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
    return fact[n] * rfact[k] * rfact[n-k] % MOD

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

diff = abs(x-y)
if (min(x, y) - diff) % 3 != 0 or (min(x, y) - diff) < 0:
    print(0)
else:
    count = (min(x, y) - diff) // 3
    print(comb(2*count+diff, count, mod, 10**6))

Submission status: Accepted

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


c1 = (2*Y-X)
if c1%3!=0:
  print(0)

else:
  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
  
  c1 = c1//3
  c2 = Y-2*c1
  c3 = c1+c2
  mod = 10**9+7
  g1 = [1, 1]
  g2 = [1, 1]
  inverse = [0, 1]
  for i in range( 2,c3+1):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

  a = cmb(c3,c1,mod)

  print(a)

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 (x + y) % 3 != 0:
    print(0)
else:
    n = (x + y) // 3
    a = 2 * (x + y) // 3
    b = (x + y) // 3
    # print(a, b, n)
    if x > a or y > a:
        print(0)
    else:
        t = a-x
        # print(t)
        p = 10 ** 9 + 7
        # k = factorial(n) // factorial(t) // factorial(n - t)
        k = comb(n, n-t, p)
        # print(int(k % p))
        print(k)

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())
if(X>Y): x,y = Y,X
else: x,y = X,Y
  
#1 : →↑↑ , 2 :→↑→
#1をi回使う ∧ 2をN-i回使う
ans = -1
for i in range(y+1):
  #i回 1を使い、N-i回 2を使う
  tmp_x,tmp_y = 2*i,1*i 
  res_x,res_y = x-tmp_x,y-tmp_y
  if(res_x > 0):
    if((res_y%res_x == 0)and(res_y//res_x == 2)):
     n1 = i
     n2 = res_x
     break
  elif(res_x == 0):
     if(res_y == 0):
       n1 = i
       n2 = i
     else: ans = 0
     break
  elif(res_x < 0):
    ans = 0
    break
    
if(ans != 0):
 mod = 10**9+7 #出力の制限
 N = n1+n2
 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 )
 r = min(n1,n2)
 ans = cmb(N, r, mod)

  
if((x+y)%3 != 0): ans = 0
ans = ans%(10**9 + 7)
print(ans)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

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

    f = 1
    factorials = [1]
    for m in range(1, a + b + 1):
        f *= m
        f %= MOD
        factorials.append(f)

    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (a + b + 1)
    invs[a + b] = inv
    for m in range(a + b, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv


    print (factorials[-1] * invs[a] * invs[b] % MOD)

    # print (math.factorial(a + b) // math.factorial(a) // math.factorial(b) %  MOD)


else:
    print (0)

Submission status: Accepted

Solution code:
from math import factorial
from functools import reduce 

MOD = 10**9 + 7

def power_func(a,b,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

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

factorial = [1]
for n in range(1, X+Y):
    factorial.append(factorial[n-1]*n%MOD)

ans = 0
prv_m, prv_n = None, None
done = set([])
for m in range(X):
  if (X-m)%2 == 1:continue
  n = (X-m)//2
  if 2*m+n != Y: continue
 
  ans += factorial[m+n]*power_func(factorial[m],MOD-2,MOD)*power_func(factorial[n],MOD-2,MOD)
  ans %= MOD
  done.add((m,n))

for m in range(Y):
  if (Y-m)%2 == 1:continue
  n = (Y-m)//2
  if 2*m+n != X or (n,m) in done: continue
  ans += factorial[m+n]*power_func(factorial[m],MOD-2,MOD)*power_func(factorial[n],MOD-2,MOD)
  ans %= MOD

print(ans%MOD)

Submission status: Accepted

Solution code:

# Python3 function to  
# calculate nCr % p 
def ncr(n, r, p): 
    # initialize numerator 
    # and denominator 
    num = den = 1 
    for i in range(r): 
        num = (num * (n - i)) % p 
        den = (den * (i + 1)) % p 
    return (num * pow(den,  
            p - 2, p)) % p 


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

if not((x + y) % 3 == 0):
    print(0)
elif (x > 2*y) or (y > 2 * x):
    print(0)
else:
    k = (x + y) // 3
    i = x - k
    print(ncr(k, i, 10 ** 9 + 7))

Submission status: Accepted

Solution code:
from functools import reduce

prime = 1000000007


def modpow(a: int, n: int, mod: int = prime) -> int:
    res = 1
    while n > 0:
        if n & 1 != 0:
            res = res * a % mod
        a = a * a % mod
        n = n // 2
    return res


def modinv(a: int, mod: int = prime) -> int:
    return modpow(a, mod-2, mod)


def modfactrial(n: int, mod: int = prime) -> int:
    return reduce(lambda x, y: (x*y) % mod, range(1, n+1), 1)


def modcombination(n: int, r: int, mod: int = prime) -> int:
    # nCr = n!/(r!(n-r)!)
    n_fact = modfactrial(n, mod)
    r_fact = modfactrial(r, mod)
    nr_fact = modfactrial(n-r, mod)
    r_fact_inv = modinv(r_fact, mod)
    nr_fact_inv = modinv(nr_fact, mod)
    return n_fact * r_fact_inv * nr_fact_inv % mod


def abort():
    import sys
    print(0)
    sys.exit(0)


x, y = [int(x) for x in input().split()]
if (2*x-y) % 3 != 0:
    abort()
if (2*y-x) % 3 != 0:
    abort()
n = (2*y-x)//3
m = (2*x-y)//3

if n < 0 or m < 0:
    abort()
print(modcombination(n+m, n))

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 (x+y)%3 !=0 :
  print(0)
else:  
  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 )

  move = (x+y)//3
  lx = x-move
  n = cmb(move,lx,mod)  
        
  print(n%(10**9+7))

Submission status: Accepted

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

N=min(X,Y)
factl=[1]
for i in range(1,N+1):
    factl.append(factl[-1]*i%mod)
invl=[pow(factl[-1],mod-2,mod)]
for i in range(N,0,-1):
    invl.append(invl[-1]*i%mod)
invl.reverse()
def Comb(a,b):
    return factl[a]*invl[a-b]*invl[b]%mod

d=X-Y
if (Y-d)%3!=0 or Y-d<0:
    print(0)
    exit()
x,y=d+(Y-d)//3,(Y-d)//3

print(Comb(x+y,y))