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:
# coding: utf-8
import re
import math
import itertools
from copy import deepcopy
import random
from heapq import heappop,heappush
import time
import os
import queue
import sys
import datetime
from functools import lru_cache
readline=sys.stdin.readline
sys.setrecursionlimit(2000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
week=["Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"]
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_power(a,b):#aはbの累乗数か
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def facs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod_,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod_-2,mod_)*pow(fac[r],mod_-2,mod_))%mod_
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def floor_(n,x=1):
    return x*(n//x)
def ceil_(n,x=1):
    return x*((n+x-1)//x)
#################################### ########
# coding: utf-8
import re
import math
import itertools
from copy import deepcopy
import random
from heapq import heappop,heappush
import time
import os
import queue
import sys
import datetime
from functools import lru_cache
readline=sys.stdin.readline
sys.setrecursionlimit(2000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_power(a,b):#aはbの累乗数か
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def get_facs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def floor_(n,x=1):
    return x*(n//x)
def ceil_(n,x=1):
    return x*((n+x-1)//x)
###################################################
def main():
    X,Y=map(int,input().split())
    if (X+Y)%3==0:
        n=(X+Y)//3
        X-=n
        Y-=n
        facs=get_facs(10**6+1,mod)
        if X<0 or Y<0:
            print(0)
            return
        ans=(facs[X+Y])*pow(facs[X]*facs[Y],mod-2,mod)%mod
        print(ans)
    else:
        print(0)


main()

Submission status: Accepted

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

a, b = divmod(2*X-Y, 3)
c, d = divmod(2*Y-X, 3) 
if (not b == d == 0) or (2*X < Y) or (2*Y < X):
  print(0)
else:
  m, n = 1, 1
  mod = 10**9+7
  for i in range(1, min(a, c)+1):
    m = (m * (a+c-i+1)) % mod
    n = (n * i) % mod
  ans = (m * pow(n, mod-2, mod)) % mod
  print(ans)

Submission status: Accepted

Solution code:
MOD = 1000000007

def mod(n):         
  return n % MOD

def add(a, b):      #mod(a+b)を求める
  return mod(mod(a)+mod(b))

def subtract(a, b): #mod(a-b)を求める
  return mod(mod(a)-mod(b))

def multiply(a, b): #mod(a*b)を求める
  return mod(mod(a)*mod(b))

def divide(a, b):   #mod(a / b)を求める
  ans = mod(a) * inverse(b)
  return mod(ans)

def modpow(a, n):   #mod(a**n)を高速で求める
    res = 1  
    digit = len(str(bin(n))) - 2
    for i in range(digit):
      if (n >> i) & 1:
        res *= mod(a)
        res = mod(res)
      a = mod(a**2)
    return mod(res)

def inverse(a):     #aの逆元を求める
  return modpow(a, MOD-2)

MAX = 1000000           #適当な数を入力
fac, finv, inv = [[0]*MAX for i in range(3)]
def combinit():     #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

def modcomb(n, k):      #mod(nCk)を計算、ただしn<MAX
  if (n < k):
    return 0
  if (n < 0 or k < 0):
    return 0
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
combinit()          #下準備の実行 O(MAX)

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

if (x+y) % 3 != 0:
  print(0)
  sys.exit()
  
if x < y:
  x, y = y, x
  
k = (2*y - x)//3
print(modcomb(y-k, k))

Submission status: Accepted

Solution code:
from math import factorial
mod=10**9+7

def mod_cmb(n,k,mod):
    def ext_gcd(a,b):
        if b==0:
            return a, 1, 0
        else:
            d,x,y=ext_gcd(b,a%b)
            x-=(a//b)*y 
        return d,y,x
    p,q=1,1
    for i in range(n-k+1,n+1):
        p=(p*i)%mod
    for i in range(2,k+1):
        q=(q*i)%mod
    return int(p*(ext_gcd(q,mod)[1]%mod)%mod)

a,b=map(int,input().split())

x=abs(a-b)
c=max(a,b)-x*2
d=min(a,b)-x


if c%3==0 and d%3==0 and c==d and c>=0:
    print(mod_cmb(x+c//3*2,c//3,mod))
else:
    print(0)

Submission status: Accepted

Solution code:
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
fracmod=[0]*(2*(10**6))
fracmod[0]=1
fracmod[1]=1
p=10**9+7
X,Y=map(int,input().split())
for i in range(2,2*(10**6)):
    fracmod[i]=(fracmod[i-1]*i)%p
if (X+Y)%3==0:
    a=(X+Y)//3
    b=X-a
    #print(a,b)
    if (b<0)or(b>a):
        print("0")
    else:
        print((fracmod[a]*modinv(fracmod[a-b],p)*modinv(fracmod[b],p))%p)
else:
    print("0")

Submission status: Accepted

Solution code:
nmax = 2*10**6
mod = 10**9+7
fac = [1]*nmax
finv = [1]*nmax
inv = [1]*nmax
def ncr_pre():
    for i in range(2,nmax):
        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 ncr(n,r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fac[n]* (finv[r] * finv[n-r] %mod) %mod
ncr_pre()

x,y = map(int,input().split())
a = (2*x-y)/3
b = (2*y-x)/3
if a.is_integer() and b.is_integer():
    a = int(a)
    b = int(b)
    print(ncr(a+b,b))
else:
    print(0)

Submission status: Accepted

Solution code:
from functools import reduce
X,Y = map(int,input().split())
x = (-X+2*Y) /3
y = (2*X-Y) /3
MOD = 10**9+7

def mod_comb(n,m,mod):
  def mod_mult(a,b,mod1=mod):
    return (a*b) % mod1
  n1 = reduce(mod_mult ,range(n,n-m,-1),1)
  n2 = reduce(mod_mult ,range(m,1,-1),1)
  n2inv = pow(n2,mod-2,mod) 
  return ((n1*n2inv) % mod)


if int(x) == x and int(y) == y and x>=0 and y>=0 :
  sum1 = int(x+y)
  bunbo = min([int(x),int(y)])
  print(mod_comb(sum1,bunbo,MOD))
else:
  print(0)

Submission status: Accepted

Solution code:
# 二項係数の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 = 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())

v=abs(x-y)
if min(x,y)-v>=0 and (min(x,y)-v)%3==0:
    r=(min(x,y)-v)//3+v
    l=(min(x,y)-v)//3
    ans=cmb(r+l,l,mod)
    print(ans)
else:
    print(0)

Submission status: Accepted

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

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
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
if (X + Y) % 3 != 0:
    print(0)
else:
    x = (2*Y-X) // 3
    y = (2 * X - Y) // 3
    total = x + y
    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)
    print(cmb(total, x, p))

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

x,y = mi()
#a,b
# x = a + 2b
# y  = 2a + b

if (-x + 2*y) % 3 == 0 and (2*x - y) % 3 ==0:
    a = (-x+2*y) //3
    b = (2*x-y)//3
    if a < 0 or b < 0:
        print(0)
        exit()
else:
    print(0)
    exit()

#a+b C a
#a^-1 (mod P)
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

#  これは計算量rでncr mod p を求められる。
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

ans = combination(a+b,a)
print(ans)

Submission status: Accepted

Solution code:
#%%
x, y = map(int,input().split())
x,y =max(x,y),min(x,y)
y_1 = y
y_2 = 0
x_1 = 0
x_2 = y
while x_1 + x_2*2 > x:
    y_1 -=2
    y_2 +=1
    x_1 +=1
    x_2 -=2
if x_1 + x_2*2 !=x or y_1 + 2*y_2 !=y:
    print(0)
    exit()
p = 10 ** 9 + 7
N = y + 1  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

fact = [ 0 for i in range(N+1)]
factinv = fact.copy()
inv = fact.copy()

fact[0], fact[1] = 1, 1
factinv[0], factinv[1] = 1, 1
inv[0], inv[1] = 0, 1


for i in range(2, N + 1):
    fact[i] = (fact[i-1] * i) % p##階乗のリスト
    inv[i] = (-inv[p % i] * (p // i)) % p
    factinv[i] =(factinv[i-1] * inv[i]) % p##階乗の逆数のリスト

#知りたいのが数通りのcmbだけの場合
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

print(fact[y_1+y_2]*factinv[y_1]*factinv[y_2] %p)

Submission status: Accepted

Solution code:
def main():
    
    M = 10**9 + 7
    
    def ncr(n, r, mod=M):
        upp, low = 1, 1
        for i in range(r):
            upp = upp * (n-i) % mod
            low = low * (r-i) % mod
        return upp * pow(low, mod-2, mod) % mod
    
    x, y = map(int, input().split())
    if (x + y) % 3:
        print(0)
        return
    
    n = (x + y) // 3
    
    if x - n < 0 or y - n < 0:
        print(0)
        return
    
    print(ncr(n, x-n))

if __name__ == "__main__":
    main()

Submission status: Accepted

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



def p(m,n):
  a = 1
  for i in range(n):
    a = (a*(m-i)) % mod
  return a

def c(m,n):
  return p(m,n)*pow(p(n,n),mod-2,mod) % mod

if (X+Y) % 3 == 0 and Y//2 <= X <= Y*2:
  print(c((X+Y)//3,(2*X-Y)//3))
else:
  print(0)

Submission status: Accepted

Solution code:
def main():
    x, y = [int(x) for x in input().split()]
    if (x + y) % 3 != 0:
        return 0
    moves = (x + y) // 3
    a, b = x - moves, y - moves
    if a < 0 or b < 0:
        return 0
    return combinations_mod(a + b, a)


def combinations_mod(n, r, mod=1000000007):
    """Returns nCr in mod."""
    r2 = n - r
    r = min(r, r2)
    combs = 1
    for i, j in zip(range(n - r + 1, n + 1), range(1, r + 1)):
        combs = combs % mod * i % mod * pow(j, mod - 2, mod) % mod
    return combs


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

Submission status: Accepted

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

cnt = 0
for p in range(X//2+1):
  if Y == 2*X-3*p:
    A = 1
    for a in range(p):
      A *= (X-p)-a
      A %= mod
    B = 1
    for b in range(1,p+1):
      B *= b 
      B %= mod
    cnt +=( A*pow(B,mod-2,mod) )% mod
print(cnt)

Submission status: Accepted

Solution code:
import sys

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

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

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,r = 5000,5

n = (X + Y)//3
r = min(X, Y) - n
print(cmb(n, r, p))

Submission status: Accepted

Solution code:
from functools import reduce


def modcombination(n, k, mod):
    # nCk % mod
    num = reduce(lambda x, y: x * y % mod, range(n, n - k, -1))
    den = reduce(lambda x, y: x * y % mod, range(1, k + 1))
    return num * pow(den, mod - 2, mod) % mod


if __name__ == '__main__':
    MOD = 10 ** 9 + 7
    x, y = map(int, input().split())
    if (x + y) % 3 != 0:
        print(0)
        exit(0)

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

Submission status: Accepted

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

import sys
if (-X+2*Y)%3 != 0 or (2*X-Y)%3 != 0:#桂馬跳びでは到達できない
    print(0)
    sys.exit()
x, y = (-X+2*Y) // 3, (2*X-Y) // 3
if x < 0 or y < 0:#盤面外
    print(0)
    sys.exit()
    
P = 1000000007

def mul(a, b):
    return ((a % P) * (b % P)) % P
 
def div(x, y):
    return mul(x, pow(y, P-2, P))
 
def comb(n, r):
    x = 1
    for i in range(n, n - r, -1):
        x = (x * i) % P
        
    y = 1
    for i in range(1, r+1):
        y = (y * i) % P
    return div(x, y)

print(comb(x + y, min(x, y)))

Submission status: Accepted

Solution code:
MOD=10**9+7

def nCr(n,r):
    """組み合わせ"""
    res=1
    fac=1
    for i in range(r):
        res *= n-i
        res %= MOD
        fac *= i+1
        fac %= MOD
    return res*pow(fac, MOD-2, MOD)%MOD

def main():
    X,Y=map(int,input().split())
    flag=0
    if (X+Y)%3!=0:
        flag=1
    n=(2*Y-X)//3
    m=(2*X-Y)//3
    if n<0 or m<0:
        flag=1
    if flag:
        print(0)
        exit()
    print(nCr(n+m,min(n,m)))

main()

Submission status: Accepted

Solution code:
from functools import reduce
X,Y = map(int,input().split())
x = (-X+2*Y) /3
y = (2*X-Y) /3
#ans=0のときをどっかで書く。indentめんどいからどうする？
MOD = 10**9+7
if int(x) == x and int(y) == y and x>=0 and y>=0 :
  sum1 = int(x+y)
  bunbo = min([int(x),int(y)])
  n1 = reduce(lambda a,b : (a*b) % MOD  ,range(sum1,sum1-bunbo,-1),1)
  n2 = reduce(lambda a,b : (a*b) % MOD ,range(bunbo,1,-1),1)
  n2inv = pow(n2,MOD-2,MOD) 
  print((n1*n2inv) % MOD)
else:
  print(0)

Submission status: Accepted

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

from operator import mul
from functools import reduce
def combination_count(n, r):
  r = min(n-r, r)
  num = reduce(modmul, range(n, n-r, -1), 1)
  denom = reduce(modmul, range(r, 1, -1), 1)
  return num*mod_inv(denom,10**9+7)

def modmul(a, b):
  return mul(a,b)%(10**9+7)

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

if (x+y)%3 != 0:
  print('0')
else:
  m = (2*x - y)//3
  n = x - 2*m
  if m < 0 or n < 0:
    print('0')
  else:
    c = combination_count(m+n, m)
    print(c%(10**9+7))

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
from functools import reduce
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm_base(a, b):
    return (a * b) // gcd(a, b)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def nCr(n,r):
  bunshi = 1
  bunbo = 1
  for i in range(r):
    bunshi = (bunshi * (n-i)) % MOD
    bunbo = (bunbo * (i+1)) % MOD
  return bunshi * pow(bunbo, MOD - 2, MOD) % MOD


def main():
  X, Y = map(int, readline().split())
  if (X + Y) % 3 != 0 or (2 * X - Y) % 3 != 0 or (2 * Y - X) % 3 != 0:
    print(0)
    sys.exit()
  else:
    n = (2*Y - X)//3
    m = (2*X - Y)//3
    if n<0 or m<0:
      print(0)
      sys.exit()
    ans = nCr(n+m, n)
  print(ans%MOD)
  
  
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
def pow_mod(n, m, mod):
    if m == 0:
        return 1
    if m == 1:
        return n

    res = 1
    if m % 2 == 1:
        res = n

    return ((pow_mod(n * n % mod, m // 2, mod) % mod) * res) % mod


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


def cmb_mod(n, r, mod):

    mul1 = frac_mod(n, mod) % mod
    mul2 = pow_mod(frac_mod(r, mod), mod - 2, mod) % mod
    mul3 = pow_mod(frac_mod(n - r, mod), mod - 2, mod) % mod

    return (((mul1 * mul2) % mod) * mul3) % mod


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

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


mod = 10 ** 9 + 7
a = (2 * y - x) // 3
b = (2 * x - y) // 3

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

print(cmb_mod(a + b, a, mod))

Submission status: Accepted

Solution code:
def cmb(n, r, p):
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
n = 7*10**5  # N は必要分だけ用意する
N = 2*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)
    if i <= n:
        inv.append((-inv[p % i] * (p // i)) % p)
        factinv.append((factinv[-1] * inv[-1]) % p)
X, Y = map(int, input().split())
if (X+Y)%3 != 0:
    result = 0
else:
    n = Y-(X+Y)//3
    m = X-(X+Y)//3
    if n<0 or m<0:
        result = 0
    else:
        result = cmb(n+m, n, p)
print(result)

Submission status: Accepted

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

def fac(n,k,p):
    ans=1
    for i in range(n-k+1,n+1):
        ans=(ans*i)%p
    return ans

def makeinv(length,p):
    L=[0,1]
    for i in range(2,length+1):
        x=p-((L[p%i]*(p//i))%p)
        L.append(x)
    return L

def comb(n,k,p):
    ans=fac(n,k,p)
    inv=makeinv(k,p)
    for i in range(1,k+1):
        ans=(ans*inv[i])%p
    return ans

if (X+Y)%3!=0:
    print(0)
else:
    N=(X+Y)//3
    K=(2*Y-X)//3
    if N>=0 and K>=0:
        print(comb(N,K,P))
    else:
        print(0)

Submission status: Accepted

Solution code:
mod = 10**9 + 7
x,y = map(int,input().split())
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

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

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

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

    return result
if (x + y)%3 != 0 :
    print(0)
else :
    n = int((x + y)/3) 
    if x - n < 0 or y - n < 0:
        print(0)
    else:
        ans = cmb(n,x-n)
        print(ans%mod)

Submission status: Accepted

Solution code:
def fact(n,mod):
    ret=1
    for i in range(2,n+1):
        ret=(ret*i)%mod
    return ret

def pCq(p,q,mod):
  pCq=1
  for i in range(q):
    pCq*=p-i
    pCq=pCq%mod
  den=fact(q,mod)
  inv=pow(den,mod-2,mod)
  pCq=(pCq*inv)%mod
  return pCq

X,Y=map(int,input().split())
MOD=10**9+7
ans=0
n,m=2*X-Y,2*Y-X
if n%3==0 and m%3==0:
  n//=3
  m//=3
  ans=pCq(m+n,max(m,n),MOD)
print(ans)

Submission status: Accepted

Solution code:
def power(x, y, mod):
    """
    https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
    二分累乗法でx ** yを求める
    
    2 ** n = 4 ** (n//2) = 16 ** (n//4)
    みたいなことをする
    """

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


def mul(a, b, mod):
    """
    https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
    modを加味したかけ算を行う
    """
    return ((a % mod) * (b % mod)) % mod

def div(a, b, mod):
    """
    https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
    modを加味した割り算を行う    
    """
    if a == b:
        return 1
    return mul(a, power(b, mod-2, mod), mod)


def factorial_part(start, last, mod):
    """
    startからlastまでのかけ算を行う
    
    factorial_part(2, 4, mod) = 2 * 3 * 4 = 24    
    """
    assert(start <= last)
    x = 1
    for k in range(start, last+1):
        x *= k
        x %= mod
    return x

def combination(n, a, mod):
    if a == 0:
        return 1
    nCa = div(factorial_part(n - a + 1, n, mod), factorial_part(1, a, mod), mod)
    return nCa

mod = int(1e9) + 7



x, y  = map(int, input().split())
s = x + y
if s % 3 != 0:
    print(0)
else:
    s = s // 3
    x -= s
    y -= s
    if x < 0:
        print(0)
    elif y < 0:
        print(0)
    else:
        print(combination(x + y, x, mod))

Submission status: Accepted

Solution code:
#ABC145D

MOD = 10 ** 9 + 7
import math
x,y = map(int,input().split())
a,b = -1,-1

for i in range(x+1):
    m = 0
    if (x-i) % 2 == 0:
        m = (x-i) // 2
        if 2*i + m == y:
            if i >= 0 and m >= 0:
                a = i
                b = m
                break
    else:
        continue
        
def kai(x):
    an = 1
    for i in range(1,x+1):
        an = an * i % MOD
        
    return an

def pow_k(x, n):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K = K * x % MOD
        x = x ** 2 % MOD
        n //= 2

    return K * x % MOD

al = kai(a)
be = kai(b)

if a == -1 and b == -1:
    print(0)
else:
    print(( kai(a+b) * pow_k(al,MOD-2)) % MOD * pow_k(be,MOD-2) % MOD )

Submission status: Accepted

Solution code:
def comb(n, k, mod):
    if k == 0:
        return 1
    else:
        x, y = 1, 1
        for i in range(k):
            x = x * (n - i) % mod
            y = y * (k - i) % mod
        c = x * pow(y, mod - 2, mod) % mod
        return c


x, y = map(int, input().split())
mod = 10 ** 9 + 7
n = (x + y) // 3
if not((x + y) % 3 == 0 and n <= x <= 2 * n):
    ans = 0
else:
    k = min(x - n, 2 * n - x)
    ans = comb(n, k, mod)
print(ans)

Submission status: Accepted

Solution code:
#ABC145D

MOD = 10 ** 9 + 7
import math
x,y = map(int,input().split())
a,b = -1,-1

for i in range(x+1):
    m = 0
    if (x-i) % 2 == 0:
        m = (x-i) // 2
        if 2*i + m == y:
            if i >= 0 and m >= 0:
                a = i
                b = m
                break
    else:
        continue
        
MAX_N = 10**6

fact = [1]
fact_inv = [0]*(MAX_N+4)
for i in range(MAX_N+3):
    fact.append(fact[-1]*(i+1)%MOD)

fact_inv[-1] = pow(fact[-1],MOD-2,MOD)
for i in range(MAX_N+2,-1,-1):
    fact_inv[i] = fact_inv[i+1]*(i+1)%MOD

def com(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod  
        
        
if a == -1 and b == -1:
    print(0)
else:
    print(com(a+b,a,MOD))

Submission status: Accepted

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

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

#m: (i+2, j+1), n (i+1, j+2)

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

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

ans = 1
i = 1

if n > m:
    n, m = m, n

while i <= n:
    ans *= (m+i) * pow(i, MOD-2, MOD)
    ans %= MOD
    i += 1

print(ans)

Submission status: Accepted

Solution code:
class MathUtil:
    # calculate {m+n}C{n}
    def egcd(self, a: int, b: int):
        if a == 0:
            return b, 0, 1
        else:
            g, y, x = self.egcd(b % a, a)
            return g, x - (b // a) * y, y

    def modinv(self, a: int, m: int):
        g, x, y = self.egcd(a, m)
        if g != 1:
            raise Exception('modular inverse does not exist')
        else:
            return x % m

    def combination(self, n: int, r: int, mod: int = 10**9+7) -> int:
        r = min(r, n-r)
        res = 1
        for i in range(r):
            res = res * (n-i) * self.modinv(i+1, mod) % mod
        return res


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


m = - x + 2*y
n = 2*x - y

if m % 3 != 0 or n % 3 != 0 or m < 0 or n < 0:
    print(0)
else:
    m //= 3
    n //= 3

    print(MathUtil().combination(m+n, n))

Submission status: Accepted

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


def combination(n, r, mod=10**9+7):
    """
    nCr mod m
    """
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


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

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

if a < 0 or a > n:
    print(0)
else:
    print(combination(n, a))

Submission status: Accepted

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

if(abs(y-x) > min(x,y)):
    print(0)
    exit()

sum_ = (x+y)//3
right = y - sum_
up = x - sum_

mod = 10**9 + 7

## nCkのmodを求める関数
# テーブルを作る(前処理)
max = 10**6 + 10
fac, finv, inv = [0]*max, [0]*max, [0]*max

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

comInit(max)

# 二項係数の計算
def com(n,k):
    if(n < k):
        return 0
    if( (n<0) | (k < 0)):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

ans = com((right+up), right)
print(ans)

Submission status: Accepted

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

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

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

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

mi = min(n,m)
num = n+m
mod = 10**9+7
a = 1
b = 1

for i in range(mi):
    a = a*(num-i)%mod
    b = b*(mi-i)%mod

print((a*pow(b,mod-2,mod))%mod)

Submission status: Accepted

Solution code:
M=10**9+7;x,y=map(int,input().split());d,m=divmod(x+y,3)
if m or y>2*x or x>2*y:print(0);exit()
x-=d;y-=d;s=t=1
for i in range(min(x,y)):s=s*(x+y-i)%M;t=t*(i+1)%M
print(s*pow(t,M-2,M)%M)

Submission status: Accepted

Solution code:
M=10**9+7
x,y=map(int,input().split())
d,m=divmod(x+y,3)
if m or y>2*x or x>2*y: print(0); exit()
x-=d
y-=d
s=t=1
for i in range(min(x,y)):
  s=s*(x+y-i)%M
  t=t*(i+1)%M
print(s*pow(t,M-2,M)%M)