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: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7


def pow_mod(a, n):
    if n == 0:
        return 1
    p = pow_mod(a, n // 2)
    if n % 2 == 0:
        return (p * p) % MOD
    else:
        return (a * p * p) % MOD
        

def main():
    x, y = map(int, input().split())
    if (x + y) % 3 != 0:
        return 0
    
    n = (x + y) // 3
    x -= n
    y -= n
    if x < 0 or y < 0:
        return 0
    else:
        ans = 1
        for i in range(x + 1, x + y + 1):
            ans = (ans * i) % MOD
        for i in range(1, y + 1):
            ans = (ans * pow_mod(i, MOD - 2)) % MOD
        return ans


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

Submission status: Time Limit Exceeded

Solution code:
x, y = [int(i) for i in input().split()]
if (2*x - y)%3 != 0:
    print(0)
else:
    LIM = 2*(10**6 + 5)
    fct = [1]*LIM
    inv = [1]*LIM
    MOD = 10**9 + 7
    for i in range(1, LIM):
        fct[i] = ((i%MOD)*(fct[i-1]%MOD))%MOD
        fct[i] %= MOD

    for i in range(1, LIM):
        inv[i] = (((inv[i-1])%MOD)*(pow(i, MOD-2, MOD)%MOD)%MOD)
        inv[i] %= MOD
    
    B = (2*x - y)//3
    A = x - (2*B)
    num = fct[A+B]%MOD
    den = ((inv[A]%MOD)*(inv[B])%MOD)%MOD
    print(((num)%MOD*(den)%MOD))

Submission status: Time Limit Exceeded

Solution code:
LARGE = 10 ** 9 + 7


def solve(x, y):
    if (x + y) % 3 != 0:
        return 0
    z = (x + y) // 3
    if x < z or y < z:
        return 0
    # zC(x-z)
    r = min(x - z, y - z)
    res = 1
    for i in range(r):
        res *= z - i
        res *= pow(i + 1, LARGE - 2, LARGE)
        res %= LARGE
    return res


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


def test():
    assert solve(3, 3) == 2
    assert solve(2, 2) == 0
    assert solve(999999, 999999) == 151840682


if __name__ == "__main__":
    test()
    main()

Submission status: Time Limit Exceeded

Solution code:
x,y=map(int,input().split())
mod=10**9+7
n_max=10**6+1
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
  FI[i+1]=pow(F[i+1],mod-2,mod)
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%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: Time Limit Exceeded

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 = 3000000
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: Time Limit Exceeded

Solution code:
X,Y = map(int, input().strip().split(' '))
MOD = int(1e9+7)

dp = [[0 for __ in range(X+2)] for _ in range(Y+2)]
dp[0][0] = 1
for y in range(Y):
  for x in range(X):
    dp[y+1][x+2] = (dp[y+1][x+2]+dp[y][x])%MOD
    dp[y+2][x+1] = (dp[y+2][x+1]+dp[y][x])%MOD

print(dp[Y][X])

Submission status: Accepted

Solution code:
x, y = map(int, input().split())
mod = 10**9 + 7
if (2*x-y)%3 == 0 and (2*y-x)%3 == 0 and 2*x-y >= 0 and 2*y-x >= 0:
    u = (2*x-y)//3
    v = (2*y-x)//3
    n = u + v
    x = 1
    y = 1
    for i in range(u):
        x = x*(n-i)%mod
        y = y*(i+1)%mod
    print((x * pow(y, mod-2, mod))%mod)
else:
    print(0)

Submission status: Accepted

Solution code:
import sys
X,Y = map(int,input().split())
if (X+Y)%3 != 0:
    print(0)
    sys.exit()
A = Y - (X+Y)//3
B = X - (X+Y)//3
if A<0 or B<0:
    print(0)
    sys.exit()
N = A+B
def cmb(n, r, mod):
    inv = [0,1]
    for i in range(2, N + 1):
        inv.append((-inv[mod % i] * (mod // i)) % mod)
    cmd = 1
    for i in range(1,min(r,n-r)+1):
        cmd = (cmd*(N-i+1)*inv[i])%mod
    return cmd
    
a = cmb(N,A,10**9+7)
print(a)

Submission status: Accepted

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

mod = 10**9 + 7

if (x+y)%3 != 0:
    print(0)
    
else:
    
    n=(x+y)//3
    
    r = min(x-n,y-n)
    
    if r<0:
        print(0)
        
    else:
    
        p=1
        q=1
        for i in range(r):
           
            p *= n-i
            p %= mod
            
    
            q *= i+1
            q %= mod
                
        ans = p * pow(q,mod-2,mod)
        ans %= mod
            
        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 )


if (-x+2*y)%3!=0:
  ans=0
else:
  a=(-x+2*y)//3
  b=(2*x-y)//3
  ans=cmb(a+b,a,mod)
  
print(ans)

Submission status: Accepted

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

fact=[1 for i in range(N+1)]
for i in range(1,N):
    fact[i+1]=(fact[i]*(i+1))%mod

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

ans=0
if (2*Y-X)%3==0 and (2*X-Y)%3==0 and (2*Y-X)>=0 and (2*X-Y)>=0:
    cntx=(2*Y-X)//3
    cnty=(2*X-Y)//3
    
    ans=nCk(cntx+cnty,cntx)%mod

print(ans)

Submission status: Accepted

Solution code:
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
    
n,m = map(int, input().split(" "))

if (n+m)%3 != 0 or max(n,m) // min(n,m) > 2:
  print(0)
else:
  sa = max(n,m)-min(n,m)
  times = [((n+m)//3), ((n+m)//3-sa)//2]
  #print(times)
  print(cmb(times[0], times[1], p))

Submission status: Accepted

Solution code:
class Factorials:
    def __init__(self, n=10**6, mod=10**9 + 7):
        self.mod = mod

        # self.fac[i] ≡ i! (factorial:階乗)
        self.fac = [1] * (n+1)
        for i in range(2, n+1):
            self.fac[i] = self.fac[i-1] * i % mod

        # self.rec[i] ≡ 1 / i! (reciprocal:逆数)
        self.rec = [1] * (n+1)
        self.rec[n] = pow(self.fac[n], mod-2, mod)
        for i in range(n-1, 1, -1):
            self.rec[i] = self.rec[i+1] * (i+1) % mod

    # comb(n, r) ≡ nCr
    def comb(self, n, r):
        return self.fac[n] * self.rec[r] * self.rec[n - r] % self.mod

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

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

n = (x + y) // 3
r = x - n
c = Factorials(n)
print(c.comb(n, r))

Submission status: Accepted

Solution code:

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

mod=pow(10, 9)+7

def comint(n, mod):
    fac = [0 for _ in range(n)]
    finv = [0 for _ in range(n)]
    inv = [0 for _ in range(n)]
    fac[0]=1
    fac[1]=1
    finv[0]=1
    finv[1]=1
    inv[1]=1

    for i in range(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
    return fac, finv

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

if (x+y)%3!=0:
    print(0)
else:
    n=(x+y)//3
    a=x-n
    b=y-n
    fac, finv = comint(a+b+1, mod)
    print(com(a+b,a,fac,finv,mod))

Submission status: Accepted

Solution code:
M = 10**9 + 7

def combination(n, k):
  if k > n-k:
    k = n-k
  p = [-1 for i in range(k+1)]
  kp = {i:[] for i in range(n-k+1, n+1)}
  for i in range(2, k+1):
    if p[i] != -1:
      continue
    for j in range(i, k+1, i):
      if p[j] == -1:
        p[j] = i
    for j in range(((n-k)//i + 1)*i, n+1, i):
      kp[j].append(i)
  count = [0 for i in range(k+1)]
  for x in range(2, k+1):
    buf = x
    while p[buf]!=-1:
      m = p[buf]
      while buf > 1 and buf % m == 0:
        count[m] += 1
        buf = buf//m
  ans = 1
  for x in range(n-k+1, n+1):
    buf = x
    for i in kp[x]:
      while count[i]>0 and buf%i==0:
        buf = buf//i
        count[i] -= 1
    ans *= buf
    ans %= M
  return ans

X, Y = map(int, input().split())
a = X + Y
b = a//3
a = a%3
#print(a,b)
if a==0 and b <= X <= b*2:
  print(combination(b, X-b))
else:
  print(0)

Submission status: Accepted

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

x, y = map(int,input().split())
if (x+y)%3!=0 or 2*y<x or 2*x<y:
    print(0)
else:
    MOD = 1_000_000_007
    n = (2*y-x)//3
    m = (2*x-y)//3
    fac = [0]*(n+m+1)
    finv = [0]*(n+m+1)
    inv = [0]*(n+m+1)
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2,n+m+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
    print(calccombi(n+m,n))

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    x,y = i_map()
    if (x+y)%3 != 0:
        print(0)
        exit()

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

    if n < 0 or m < 0:
        print(0)
        exit()

    def fur(n,r):
        p,q = 1, 1
        for i in range(r):
            p = p*(n-i)%MOD
            q = q*(i+1)%MOD
        return (p * pow(q,MOD-2,MOD)) % MOD

    print(fur(n+m,n))



if __name__=="__main__":
    main()

Submission status: Accepted

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


def permute(n, m):
    ret = 1
    while n >= m:
        ret *= n
        # ret %= mod
        n -= 1

    return ret


def count_combinations(n, m):
    fact = [1] * (n + 1)
    inv = [i for i in range(n+1)]
    fact_inv = [1] * (n + 1)

    for i in range(2, n+1):
        fact[i] = fact[i-1] * i % mod
        inv[i] = (-inv[mod%i]*(mod//i))%mod
        # inv[i] = mod - inv[mod % i] * (mod // i) % mod
        fact_inv[i] = fact_inv[i-1] * inv[i] % mod

    ret = (fact[n] * fact_inv[m] * fact_inv[n-m]) % mod

    return ret


def count_comb2(n, m):
    fact = [1, 1]  # fact[n] = (n! mod p)
    factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
    inv = [0, 1]  # factinv 計算用

    for i in range(2, n + 1):
        fact.append((fact[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv.append((factinv[-1] * inv[-1]) % mod)

    if (m < 0) or (n < m):
        return 0
    m = min(m, n - m)
    return fact[n] * factinv[m] * factinv[n-m] % mod

ret = 0
if (X+Y)%3 == 0:
    m = (2*X - Y) // 3
    n = (2*Y - X) // 3

    if m >= 0 and n >= 0:
        ret = count_combinations(n+m, m)
        # ret = count_comb2(n+m, m)

print(ret)

Submission status: Accepted

Solution code:
p = 1000000007

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

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

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

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

n = a + b
fac = [0] * (n + 1)
fac[0] = 1
for i in range(n):
    fac[i + 1] = fac[i] * (i + 1) % p


def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], p - 2, p) * pow(fac[k], p - 2, p) % p


print(mcomb(n, a))
#他者の解答を参考にした

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 145 D - Knight
import sys
from math import factorial

mod = 10 ** 9 + 7

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

# 合計の移動回数は Total = X + Y / 3 
# 移動方法は A: (i + 1, j + 2)  B: (i + 2, j + 1) の2通り
# 移動回数は A: 2 * Total - X  B: X - Total 

# 到達不可能であるか判断する
if (X + Y) % 3 != 0:
    print(0)
    sys.exit()

if Y > 2 * X or Y < X * 0.5:
    print(0)
    sys.exit()


Total = (X + Y) // 3
A = Total * 2 - X
B = X - Total

# combination の計算
ans = 1
for i in range(1, Total + 1):
    ans *= i
    ans %= mod

ans = ans * pow(factorial(A), mod - 2, mod)
ans = ans * pow(factorial(B), mod - 2, mod)

print(ans % mod)

Submission status: Accepted

Solution code:
from functools import reduce

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

if (2 * y - x) % 3 != 0 or (2 * x - y) % 3 != 0:
  print("0")
  exit()
  
a,b = (2 * y - x) // 3, (2 * x - y) // 3 

r = max(a,b)

if min(a,b) < 0:
  print("0")
else:
  numerator = reduce(lambda x, y: x * y % mod, range(a + b - r + 1, a + b + 1))
  denominator = reduce(lambda x, y: x * y % mod, range(1 , r + 1))
  print(numerator * pow(denominator, mod - 2, mod) % mod)

Submission status: Accepted

Solution code:
from functools import reduce

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

if (2 * y - x) % 3 != 0 or (2 * x - y) % 3 != 0:
  print("0")
  exit()
  
a,b = (2 * y - x) // 3, (2 * x - y) // 3 

r = min(a,b)

if r == 0:
  print("1")
elif r < 0:
  print("0")
else:
  numerator = reduce(lambda x, y: x * y % mod, range(a + b - r + 1, a + b + 1))
  denominator = reduce(lambda x, y: x * y % mod, range(1,r + 1))
  print(numerator * pow(denominator, mod - 2, mod) % mod)

Submission status: Accepted

Solution code:
from collections import defaultdict

# nCkを高速に求める
# https://drken1215.hatenablog.com/entry/2018/06/08/210000


class COM:
    def __init__(self, n, MOD):
        self.n = n
        self.MOD = MOD
        self.fac = [0] * (n+1)
        self.finv = [0] * (n+1)
        self.inv = [0] * (n+1)
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        for i in range(2, n+1):
            self.fac[i] = self.fac[i-1] * i % MOD
            self.inv[i] = MOD - self.inv[MOD % i] * (MOD // i) % MOD
            self.finv[i] = self.finv[i-1] * self.inv[i] % MOD

    
    def calc(self, k):
        if k < 0:
            return 0
        return self.fac[self.n] * (self.finv[k] * self.finv[self.n-k] % self.MOD) % self.MOD


def main():
    MOD = 10**9+7
    X, Y = map(int,input().split())
    if (X+Y) % 3 == 0:
        z = (X+Y) // 3
        a_x = X-z
        a_y = Y-z
        if a_x >= 0 and a_y >= 0:
            com = COM(a_x+a_y, MOD)
            print(com.calc(a_x))
        else:
            print(0)
    else:
        print(0)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def comb(n, r, mod):
    if n < 0 or r < 0 or r > n: return 0
    nu = 1
    de = 1
    for i in range(r):
        nu = nu * (n-i) % mod
        de = de * (i+1) % mod
    return nu * inv(de, mod) % mod
 
def inv(a, mod):
    b = mod
    p, q = 1, 0
    while b > 0:
        c = a//b
        d = a; a = b; b = d % b
        d = p; p = q; q = d-c*q
    return p+mod if p < 0 else p

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

m = (2 * x -y) // 3
n = (2 * y -x) // 3
mod = 10**9+7
if n >= 0 and m >= 0 and (x + y) % 3 == 0:
  ans = comb(n+m, m, mod)
  print(ans)
else:
  print(0)

Submission status: Accepted

Solution code:
# import itertools
# import math
import sys
# sys.setrecursionlimit(500*500)
# import numpy as np
# import heapq
# from collections import deque

# N = int(input())
# S = input()
# n, *a = map(int, open(0))
X, Y = map(int, input().split())
# A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

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

if (X + Y) % 3 != 0:
    print(0)
    sys.exit()
if (2 * Y - X) < 0 or (2 * X - Y) < 0:
    print(0)
    sys.exit()

cnt = (X + Y) // 3

diff = abs(X - Y)



def comb(n, m, mod = 10 ** 9 + 7):
    numerator = 1
    denominator = 1
    for i in range(1, m + 1):
        numerator = numerator * (n - i + 1) % mod
        denominator = denominator * i % mod
    d_inv = pow(denominator, mod - 2, mod)
    return numerator * d_inv % mod

print(comb(cnt, (2 * Y - X) // 3) % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
# import itertools
# import math
import sys
# sys.setrecursionlimit(500*500)
# import numpy as np
# import heapq
# from collections import deque

# N = int(input())
# S = input()
# n, *a = map(int, open(0))
X, Y = map(int, input().split())
# A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

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

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

cnt = (X + Y) // 3

diff = abs(X - Y)



def comb(n, m, mod = 10 ** 9 + 7):
    if m < 0:
        return 0
    numerator = 1
    denominator = 1
    for i in range(1, m + 1):
        numerator = numerator * (n - i + 1) % mod
        denominator = denominator * i % mod
    d_inv = pow(denominator, mod - 2, mod)
    return numerator * d_inv % mod

print(comb(cnt, (2 * Y - X) // 3) % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
x,y=sorted(map(int,input().split()));z=x+y
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

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

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

print((z%3<1)*cmb(z//3,(2*x-y)//3,10**9+7))

Submission status: Accepted

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20

class Counting():
    def __init__(self,maxim,mod):
        maxim += 1

        self.mod = mod
        self.fact = [0]*maxim
        self.fact[0] = 1
        for i in range(1,maxim):
            self.fact[i] = self.fact[i-1] * i % mod

        self.invfact = [0]*maxim
        self.invfact[maxim-1] = pow(self.fact[maxim-1],mod-2,mod)
        for i in reversed(range(maxim-1)):
            self.invfact[i] = self.invfact[i+1] * (i+1) % mod
        


    def nCk(self,n,r):
        if n < 0 or n < r: return 0
        return self.fact[n] * self.invfact[r] * self.invfact[n-r] % self.mod

    def nPk(self,n,r):
        if n < 0 or n < r: return 0
        return self.fact[n] * self.invfact[n-r] % self.mod

        
def main():
    X,Y=mi()
    MOD = 10**9+7
    C = Counting(10**6+10,MOD)
    ans = 0
    for a in range(X+1):
        if (X-a) %2 == 1: continue
        b = (X-a)//2

        if 2*a+b == Y:
            ans += C.nCk(a+b,a)
    
    print(ans)






if __name__ == "__main__":
    main()

Submission status: Accepted

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

def mod_pow(n, m):
  res = 1
  while m > 0:
    if m & 1:
      res = (res*n)%MOD
    n = (n*n)%MOD
    m >>= 1
  return res
  
if (2*Y-X)%3 != 0 or (2*X-Y)%3 != 0 or 2*Y < X or 2*X < Y:
  print(0)
else:
  A = (2*X-Y)//3
  B = (2*Y-X)//3
  m = 1
  n = 1
  for i in range(A):
    m = (m*(A+B-i))%MOD
    n = (n*(A-i))%MOD
  inverse_n = mod_pow(n, MOD-2)
  print((m*inverse_n)%MOD)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
x, y = [int(i) for i in input().split()]
if (2*x - y) % 3 != 0 or (2*y - x) % 3 != 0:
  print(0)
  exit()
a = (2*x - y) // 3
b = (2*y - x) // 3
if a < 0 or b < 0:
  print(0)
  exit()
def mygcd(a_b, b, mod):
    b = min(a_b, b)
    cnt = 1
    for i in range(b):
        cnt = cnt * (a_b - i) * pow(i+1, mod-2, mod) % mod
    return cnt
print(mygcd(a+b, b, mod))

Submission status: Accepted

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

if (x + y)%3:
  print(0)
  sys.exit()

n = y - (x+y)//3
m = x - (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 = m+n
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(m+n,n,mod))

Submission status: Accepted

Solution code:
def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = 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 < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k]*finv[n-k]%mod)%mod

mod = 10**9+7

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

a = X%2 #1の数
b = X//2 #2の数
for i in range(b+1):
    if a*2 + b*1 == Y:
        break
    a += 2
    b -= 1

if a*2 + b*1 != Y:
    print(0)
else:
    max = a+b+1
    fac = [0] * max
    finv = [0] * max
    inv = [0] * max
    COMinit()
    print(COM(a+b,a))

Submission status: Accepted

Solution code:
# ABC145 D

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

a,b=-1,-1
if not (2*X-Y)%3:
    b=(2*X-Y)//3
if not (2*Y-X)%3:
    a=(2*Y-X)//3
    



N=10**6
p=10**9+7
f,finv,inv=[0]*N,[0]*N,[0]*N

def nCr_init(L,p):
    for i in range(L+1):
        if i<=1:
            f[i],finv[i],inv[i]=1,1,1
        else:
            f[i]=(f[i-1]*i)%p
            inv[i]=(p-inv[p%i]*(p//i))%p
            finv[i]=(finv[i-1]*inv[i])%p

def nCr(n,r,p):
    if 0<=r<=n and 0<=n:
        return (f[n]*finv[n-r]*finv[r])%p
    else:
        return 0
    
nCr_init(a+b+1,p)
if a>=0 and b>=0:
    print(nCr(a+b,b,p))
else:
    print(0)

Submission status: Accepted

Solution code:
class Combination:
    def __init__(self, mod, max_n):
        self.MOD = mod
        self.MAX_N = max_n

        self.f = self.factorial(self.MAX_N)
        self.f_inv = [self.inv(x) for x in self.f]

    def inv(self,x):
        return pow(x, self.MOD-2, self.MOD)
    
    def factorial(self, n):
        res = [1]
        for i in range(1,n+1):
            res.append(res[-1] * i % self.MOD)
        return res
    
    def comb(self, n, r):
        return (self.f[n] * self.f_inv[r] % self.MOD) * self.f_inv[n-r] % self.MOD


X, Y = map(int,input().split())
k, l = (2*Y-X)//3, (2*X-Y)//3

if (X + Y) % 3 != 0 or k < 0 or l < 0:
    print(0)
    exit()

CB = Combination(10**9+7, k+l)
print(CB.comb(k+l,k))

Submission status: Accepted

Solution code:
import math

def main():
	X, Y = [int(n) for n in input().split(" ")]
	if (X + Y) % 3 != 0 or Y > 2 * X or X > 2 * Y:
		print(0)
		return 0
	p = 1000000007
	n_move = int((X + Y) / 3)
	i_move = int((2 * X - Y) / 3)
	j_move = int((2 * Y - X) / 3)
	f = [1, 1]
	finv = [1, 1] + [0] * n_move
	for i in range(n_move):
		f.append((f[-1] * (i + 2)) % p)
	lf = len(f)
	finv[lf - 1] = modpower(f[-1], p - 2, p)
	for i in range(lf - 1):
		finv[lf - i - 2] = ((finv[lf - i - 1]) * (lf - i - 1)) % p
	print((f[n_move] * (finv[i_move] * finv[j_move]) % p) % p)

def modpower(a, p, d):
	pp = [a]
	for i in range(int(math.log2(p)) + 1):
		pp.append((pp[-1] ** 2) % d)
	b_p = format(p, 'b')
	m = 1
	for i in range(len(b_p)):
		if b_p[-i-1] == "1":
			m = (m * pp[i]) % d
	return m

main()

Submission status: Accepted

Solution code:
def nCr(n, r):
    num, den = 1, 1
    for i in range(n, n-r, -1):
        num = num * i % M       ##;print(num)
    for i in range(1, r+1):
        den = den * i % M       ##;print(den)
    den_inv = pow(den, -1, M)   #;print(num, den, den_inv) 
    return num * den_inv % M

def is_comb():
    a = 1/3 * (2*X - Y)
    b = 1/3 * (-X + 2*Y)
    if a>=0 and b >= 0 and a.is_integer() and b.is_integer():
        return int(a), int(b)
    return 0, 0

M = 10**9 + 7
X, Y  = map(int, input().split())
#X, Y =  103078,  214577
a, b = is_comb()   #; print(a, b)
if a==b==0:
    print(0)
else:
    n, r  = a+b, a
    print(nCr(n, r))

Submission status: Accepted

Solution code:
X,Y = map(int,input().split())
M = 10**9+7
if X%3 == Y%3 == 1 or X%3 == Y%3 == 2:
    Answer = 0
else:
    dif = abs(X-Y)
    W =  (min(X,Y) - dif)//3
    X1 = W + dif
    Y1 = W
    Answer = 1
    N = X1+Y1
    for i in range(1,X1+1):
        Answer = (Answer*(N)*pow(i,-1,M))%M
        N -= 1
    for j in range(1,Y1+1):
        Answer = (Answer*(N)*pow(j,-1,M))%M
        N -= 1
print(Answer)

Submission status: Accepted

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

def ncr(n, r, p):
    num = 1
    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

if (x+y)%3 == 0:
    n = (x+y)//3

    if not (n <= x <= 2*n):
        print(0)
    else:
        print(ncr(n, x-n, 1000000007))
else:
    print(0)

Submission status: Accepted

Solution code:
X,Y = map(int,input().split())
mod = 10**9+7
N = (X+Y)//3
M = (N+X-Y)//2

if (X+Y)%3!=0 or M<0 or N<M:
  print(0)
else:
  ans = 1
  for m in range(1,M+1):
    ans*=(N-M+m)*pow(m,mod-2,mod)
    ans%=mod
  print(ans)

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    return C

X,Y=mint()
if (X+Y)%3!=0:
    print(0)
    exit()
k=abs(X-Y)
N=min(X,Y)-k
if N<0:
    print(0)
    exit()
n=2*(N//3)+k
C=comb(n,MOD)
print(C.get(N//3))

Submission status: Accepted

Solution code:
X,Y=map(int,input().split())
if 2*Y<X or 2*X<Y:
  print(0)
  exit()
if not((X%3==0 and Y%3==0) or (X%3==1 and Y%3==2) or (X%3==2 and Y%3==1)):
  print(0)
  exit()
P=10**9+7
A=(2*Y-X)//3
B=(2*X-Y)//3
num = 1
for i in range(A+1, A+B+1):
  num=num*i%P
den = 1
for j in range(1, B+1):
  den = den*j%P
den = pow(den,P-2,P)
print((num*den)%P)

Submission status: Accepted

Solution code:
import math

X,Y= list(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):
    print(0)
    exit()

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


#print(s,t)

ans = cmb(s+t, s, 10**9+7)

print(ans)

Submission status: Accepted

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

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



if a!=(2*x-y)/3 or b!=(2*y-x)/3:
    print(0)
elif a<0 or b<0:
    print(0)
else:
    max=a+b+10
    fac=[0]*max
    finv=[0]*max
    inv=[0]*max

    fac[0]=fac[1]=1
    finv[0]=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

    ans=fac[a+b]*(finv[a]*finv[b]%mod)%mod
    print(ans)