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:
x,y=map(int,input().split())
mod=pow(10,9)+7
x_=(2*x-y)
y_=(2*y-x)
if x_<0 or y_<0 or x_%3!=0 or y_%3!=0:
  print(0)
  exit()
x_//=3
y_//=3
n=x_+y_
r=min(x_,y_)

a,b=1,1
for i in range(r):
  a*=n-i
  a%=mod
  b*=i+1
  b%=mod
c=(a*pow(b,mod-2,mod))%mod
print(c)

Submission status: Accepted

Solution code:
import sys
import math

# import copy
# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
INF = sys.maxsize
MOD = 10 ** 9 + 7


# ===CODE===


class Combination:
    def __init__(self, mod):
        self.mod = mod
        self.fact = [1] * (2 * 10 ** 6 + 1)
        for i in range(1, 2 * 10 ** 6 + 1):
            self.fact[i] = i * self.fact[i - 1] % self.mod

    def nCr(self, n, k):
        a = self.fact[n] % self.mod
        b = (self.fact[k] * self.fact[n - k]) % self.mod
        c = pow(b, self.mod - 2, self.mod)
        return a * c % self.mod


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

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

yoko = (2 * x - y) // 3
tate = (2 * y - x) // 3

if yoko < 0 or tate < 0:
    print(0)
    exit(0)

comb = Combination(MOD)
print(comb.nCr(yoko + tate, yoko))

Submission status: Accepted

Solution code:
'''
Aは移動関数と同数：xとy方向に合計で3進んでいるから
Bは移動回数の内、(i+1,j+2)を選んだ回数：
1回でx方向には1進み、y方向には2進む
進み方は2通りしかないので、全体の内、1通りを選んだ回数を求めればOK
'''
X,Y=map(int,input().split())
if (X+Y)%3!=0:#まず、条件に合わないケースを除外
  print(0)
  exit()
A=int((X+Y)/3)
B=int((2*Y-X)/3)
if A<0 or B<0:
  print(0)
  exit()
MOD=10**9+7
def comb(n,k):#組合せを求める関数
  tmp=1
  for i in range(n-k+1,n+1):#分子：n*(n-1)*...*(n-k+1)
    tmp*=i
    tmp%=MOD
  for i in range(1,k+1):#分母：k!
    tmp*=pow(i,MOD-2,MOD)#分母なので逆元にする
    tmp%=MOD
  return tmp
ans = comb(A,B)#上記説明の通り。要は組み合わせの問題
print(ans%MOD)

Submission status: Accepted

Solution code:
#ika　tako
def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f = f * m % MOD
        #print(f)
    fn = f#n!を求める
    #print(fn)
 
    #print(f)
    inv = pow(f, MOD - 2, MOD)
    #print(inv)
    invs = [1] * (n + 1)#[1, 1, 1]のイメージ、逆元？格納テーブル
    #print(invs)　　⇒　[1, 1, 1]のイメージ、逆元格納テーブル
    invs[n] = inv
    for m in range(n, 1, -1):#n*(n-1)*(n-2)*...と上から掛けている
        inv = inv * m % MOD#なぜ、下から掛けない？
        invs[m - 1] = inv
 
    return fn, invs
 
def solve(x, y):
    d, m = divmod(x + y, 3)#商と余り
    if m != 0 or x < d or y < d:
    #Xとyの合計は3の倍数、x、yがd移動回数以下はあり得ない（1回1個は進む）
        return 0
    #c = d - x　　これだと範囲外参照でエラー
    c = abs(d - x)
 
    MOD = 10 ** 9 + 7
    f, invs = prepare(d, MOD)
    return f * invs[c] * invs[d - c] % MOD
  #fはn!、invs[c],invs[d - c] はc!,(d-c)!の逆元？
  #nCr=n!/(r!*(n-r)!)
  
x, y = map(int, input().split())
print(solve(x, y))

Submission status: Accepted

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

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

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

W = X - ((X+Y)//3)
H = Y - ((X+Y)//3)

mx = 10**6
fact = [1] * (mx+1) # 階乗を格納するリスト
def inv(n): # MODを法とした逆元
    return pow(n, MOD-2, MOD)
for i in range(mx):
    fact[i+1] = fact[i] * (i+1) % MOD # 階乗を計算
ans = (fact[W+H] * inv(fact[W]) * inv(fact[H])) % MOD # comb(W+H,W) = (W+H)!/(W!H!)
print (ans)

Submission status: Accepted

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

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

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

W = X - ((X+Y)//3)
H = Y - ((X+Y)//3)

mx = 10**6
fact = [1] * (mx+1) # 階乗を格納するリスト
def inv(n): # MODを法とした逆元
    return pow(n, MOD-2, MOD)
for i in range(mx):
    fact[i+1] = fact[i] * (i+1) % MOD # 階乗を計算
ans = (fact[W+H] * inv(fact[W]) * inv(fact[H])) % MOD # comb(W+H,W) = (W+H)!/(W!H!)
print (ans)

Submission status: Accepted

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

if (X+Y) % 3 == 0:
    Z = int((X+Y)/3)
    A = X - Z
    B = Y - Z
    fact = [1] * (Z+1)
    fact_inv = [1] * (Z+1)

    if A >= 0 and A <= Z and A + B == Z:
        for i in range(1,Z+1):
            fact[i] = (fact[i-1] * i)%MOD
        for i in range(1,max(A,B)+1):
            fact_inv[i] = pow(fact[i], MOD-2,MOD)

        ans = (((fact[Z] * fact_inv[Z-A]) % MOD ) * fact_inv[A]) % MOD
        print(ans)
    else:
        print(0)


else:
    print(0)

Submission status: Accepted

Solution code:
import sys, math
from pprint import pprint
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

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

X, Y = rl()

if (X+Y) % 3 != 0:
	print(0)
	exit()
if not (1/2 <= Y/X <= 2):
	print(0)
	exit()
n = (X+Y)//3
k = X-n
print(combmod(n,k))

Submission status: Accepted

Solution code:
import numpy as np

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

fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

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


if __name__ == '__main__':
    x, y = map(int, input().split())
    if (x + y) % 3 != 0:
        res = 0
    else:
        n, m = map(int, np.linalg.solve([[1, 2], [2, 1]], [x, y]))
        if n < 0 and m < 0:
            res = 0
        else:
            COMinit()
            res = COM(n + m, n)
    print(res)

Submission status: Accepted

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

MAX = 10**6+1
MOD = 10**9+7
fac = [1]
for i in range(1, MAX):
    fac.append(fac[i-1] * i % MOD)

if (x % 3 == 0 and y % 3 == 0) or (min(x % 3, y % 3) == 1 and max(x % 3, y % 3) == 2):
    xx, yy = max(x, y), min(x, y)
    a = b = 0
    while not xx == yy:
        xx -= 2
        yy -= 1
        a += 1
        if xx < 0 or yy < 0:
            res = 0
            break
    else:
        a += xx // 3
        b += yy // 3
        res = fac[a+b] * pow(fac[a]*fac[b], MOD-2, MOD) % MOD
    print(res)
else:
    print(0)

Submission status: Accepted

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

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

def comb(n, r, mod = 10**9 + 7):
    return ( framod(n,mod) * pow(framod(n-r,mod),mod-2,mod ) * pow(framod(r,mod),mod-2,mod))
X,Y=map(int,input().split())
if (X + Y) % 3 ==0:
  s,t= ( 2*X - Y ) // 3 , (2*Y - X) // 3
  if s*t<0:
    print(0)
  else:
    print(comb(s+t,s) % mod)
else:
  print(0)

Submission status: Accepted

Solution code:
import math
import sys

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

#互いに素なa,bについて、a*x+b*y=1の一つの解
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)
    sys.exit()

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

x = X - ((X + Y) // 3)
y = Y - ((X + Y) // 3)

mod = 10 ** 9 + 7

numerater = 1
for i in range(1, x+y+1):
    numerater =  (numerater * i) % mod

denominator_x = 1
for i in range(1, x+1):
    denominator_x = (mod_inv(i, mod) * denominator_x) % mod

denominator_y = 1
for i in range(1, y+1):
    denominator_y = (mod_inv(i, mod) * denominator_y) % mod

res = (numerater * denominator_x * denominator_y) % mod

print(res)

Submission status: Accepted

Solution code:
X,Y=map(int, input().split())
if X/Y>2 or Y/X>2 or (X+Y)%3!=0:
    print(0)
    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) 階乗のmod
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)
base=(X+Y)//3
print(cmb(base, (X-base),p))

Submission status: Accepted

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

a = 2*x - y
b = -x + 2*y
if a < 0 or b < 0:
    print(0)
    exit()

a //= 3
b //= 3
MOD = 10**9+7
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 mod_comb_k(n,k,MOD):
    return fact[n] * fact_inv[k] % MOD * fact_inv[n-k] %MOD


print(mod_comb_k(a+b, a, MOD))

Submission status: Accepted

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

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

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

cnt = 0
while(y != 2*x):
    y += 1
    x -= 1
    cnt += 1

def mod_combination(n, k):
    mod = 1000000007
    v = 1
    for i in range(1, k+1):
        v *= n
        v %= mod
        v *= pow(i, mod-2, mod)
        v %= mod
        n -= 1
    return v % mod

print(mod_combination(x, cnt))

Submission status: Accepted

Solution code:
from functools import reduce
X,Y = (int(x) for x in input().split())
def route(x,y):
    d = min(x,y) - ((x+y)//3)
    if d == 0:
        return 1
    else:
        return (route(x-2,y-1) + route(x-1,y-2))%1000000007
def modmul(a,b):
    return a * b % 1000000007
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m
def comb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(modmul, range(n, n - r, -1))
    under = reduce(modmul, range(1,r + 1))
    return over * modinv(under, 1000000007)
if (X+Y) % 3 != 0 or min(X,Y) < (X+Y) // 3:
    print('0')
else:
    d = min(X,Y) - ((X+Y)//3)
    if d == 0:
        print('1')
    else:
        t = (X+Y) // 3
        print((comb(t-1,d)+comb(t-1,d-1))%1000000007)

Submission status: Accepted

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

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

def make_tables(mod,n):
    fac = [1,1]
    ifac = [1,1]
    inverse = [0,1]

    for i in range(2,n+1):
        fac.append((fac[-1]*i)%mod)
        inverse.append((-inverse[mod%i]* (mod//i)) % mod)
        ifac.append((ifac[-1]* inverse[-1])%mod)
    return fac, ifac

if x > y:
    x, y = y, x
d = x+y
if d % 3 != 0:
    print(0)
else:
    s = (x+y)//3
    t = x - s

    if y > 2 * x:
        print(0)
    else:
        mod = 10**9+7

        fac, ifac = make_tables(mod,s)
        ans = comb(s,t,mod,fac,ifac)
        print(ans)

Submission status: Accepted

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

MOD = 10**9 + 7
def prepare(n, MOD):

    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs
if (X+Y)%3!=0:
    print(0)
else:
    #最初に行き方を決めて、使う移動方法の個数を求めて、重複組み合わせ
    #決め打ちしてから n:2x+yの移動　m:x+2yの移動
    n = (2*X-Y)//3
    m = (2*Y-X)//3

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


    fac, invs = prepare((n+m), MOD)


    print(fac[n+m]*invs[n]*invs[m]%MOD)

Submission status: Accepted

Solution code:
mod = 10**9 + 7
x, y = map(int, input().split())
move_count = 0
if (y + x) % 3 == 0:
    move_count = ((y + x) // 3)

move_a = (y - move_count) % mod
move_b = (x - move_count) % mod


def nck(n, k):
    numer, denom = 1, 1
    for i in range(k):
        numer = numer * (n - i) % mod
        denom = denom * (k - i) % mod
    return numer * pow(denom, mod-2, mod) % mod


ans = nck(move_count, min(move_a, move_b))
print(ans % mod)

Submission status: Accepted

Solution code:
def com(n,r,mod):
    k=min(r,n-r)
    C=1
    for i in range(1,k+1):
        C=(C*(n+1-i)*pow(i,mod-2,mod))%mod
    return C

x, y = map(int,input().split())
mod = 10 ** 9 + 7
n = (2 * y - x) // 3 if (2 * y - x) % 3 == 0 else -1
m = (2 * x - y) // 3 if (2 * x - y) % 3 == 0 else -1

if n >= 0 and m >= 0:
    print(com(n + m, n, mod))
else:
    print(0)

Submission status: Accepted

Solution code:
def comb(n, k, p):
    if n<0 or k<0 or n<k:
        return 0
    if n==0 or k==0:
        return 1
    a, b, c = 1, 1, 1
    for i in range(1, n+1):
        a = (a*i)%p
    for i in range(1, k+1):
        b = (b*i)%p
    for i in range(1, n-k+1):
        c = (c*i)%p
    return a*pow(b, p-2, p)*pow(c, p-2, p)%p
X,Y = map(int,input().split())
if (X + Y) % 3 != 0:
    print(0)
else:
    n = int((X+Y)/3)
    p = max(X,Y)
    q = min(X,Y)
    if p > 2 * q:
        print(0)
    else:
        a = 2*n - p
        b = comb(n,a,10**9 + 7)
        print(b)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7


def combination(n: int, r: int, mod=MOD):
    n1 = n+1
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod


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

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

    if a < 0 or b < 0:
        print(0)
    else:
        print(combination(a+b, a))

Submission status: Accepted

Solution code:
x, y = map(int, input().split())
if (x + y) % 3 != 0:
    print(0)
else:
    n = (x+y) // 3
    nx = x - n
    ny = y - n
    if (nx < 0 ) or (ny < 0):
        print(0)
    else:
        mod = 10 **9 +7
        fac = [1] * 1000000
        for i in range(1,n+1):
            fac[i] = fac[i-1] * i % mod
        print(fac[n] * pow(fac[nx], mod-2, mod) * pow(fac[ny], mod-2, mod) % mod)

Submission status: Accepted

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

mod = 10**9+7

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

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

else:
    a = (2*Y-X)//3
    b = (X+Y)//3 - a
    if a < 0 or b < 0:
        print(0)
    else:
        print(com(a+b, a))

Submission status: Accepted

Solution code:
# python3.4.2用
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')


X,Y = imn()

# 一回の移動でx座標とy座標の値は3増える。X+Yが3の倍数でないときは0
if (X+Y)%3 != 0:
    print(0)
    exit()
# M + 2N = X, 2M + N = Yの連立方程式が得られるので、M,Nを求める 
M = (2*Y-X)//3
N = (-2*M)+Y

# nCrをやる前に前準備を行う
MAX = 10**6
fact = [1,1]
factinv = [1,1]
inv = [0,1]
for i in range(2, MAX+1):
    fact.append((fact[-1]*i) % MOD)
    inv.append((-inv[MOD%i]*(MOD//i))%MOD)
    factinv.append((factinv[-1]*inv[-1])%MOD)

# nCrを求める
def cmb(n,r):
    if r < 0 or n < r:
        return 0
    r = min(r, n-r)
    return fact[n] * factinv[r] * factinv[n-r] % MOD 

print(cmb(M+N, M))

Submission status: Accepted

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

def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

x, y = map(int, input().split())
if (x+y)%3 or y>2*x or x>2*y: print(0)
else:
    a, b = (2*x-y)//3, (2*y-x)//3
    m = 10**9+7
    res = 1
    for i in range(1,a+b+1):
        res = res*i%m
    for i in range(1,a+1):
        res = res*mod_inv(i,m)%m
    for i in range(1,b+1):
        res = res*mod_inv(i,m)%m
    print(res%m)

Submission status: Accepted

Solution code:
# python3.4.2用
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')

X,Y = imn()

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

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

MAX = 10**6
fact = [1,1]
factinv = [1,1]
inv = [0,1]
for i in range(2, MAX+1):
    fact.append((fact[-1]*i) % MOD)
    inv.append((-inv[MOD%i]*(MOD//i))%MOD)
    factinv.append((factinv[-1]*inv[-1])%MOD)

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(cmb(M+N, M, MOD))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
MOD = 1000000007  # type: int

def combination(n: int, r:int, mod=MOD):
    n1 = n+1
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

def solve(X: int, Y: int):

    u = (2*Y - X)//3
    r = (X- u)//2

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

    a = combination(u+r, u)
    print(a)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(X, Y)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(4100000)

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

mod = 1000000007
f = 0
df = abs(x-y)     #difference
tm = (x+y)//3   #time

if (x+y)%3 != 0:
    f = 1
elif tm < df:
    f = 1
else:
    pass

def mod_a_to_bth_power(a:int, b:int):
    if b%2 == 0:
        return (mod_a_to_bth_power(a, b//2)**2)%mod
    elif b == 1:
        return a%mod
    else:
        return ((mod_a_to_bth_power(a, b//2)**2)*a)%mod

def mod_inverse(a:int):
    return mod_a_to_bth_power(a, mod-2)

def mod_nCr(n:int, r:int):
    num, den = 1, 1 #numerator denominator
    for i in range(r):
        num = (num*(n-i))%mod
        den = (den*(i+1))%mod
    return (num*mod_inverse(den))%mod

if f == 1:
    print(0)
else:
    if df == 0:
        c = tm//2
    else:
        c = (tm-df)//2+df
    ans = mod_nCr(tm, c)
    print(ans)

Submission status: Accepted

Solution code:
import math

mod = 10**9+7

def comb(n, r):
	x = 1
	y = 1
	if n-r<r:
		r = n-r
	for i in range(r):
		x *= n-i
		y *= (i+1)
		x %= mod
		y %= mod
	return x * pow(y, mod-2, mod) % mod

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

o = -1

if X%2 == 0:
	if (Y-X//2)%3 != 0:
		o = 0
else:
	if (Y-(X-3)//2)%3 != 0:
		o = 0

if o == -1:
	n = (2*Y-X)//3
	m = Y-2*n
	if n >= 0 and m >= 0:
		o = comb(n+m, min(n,m))
	else:
		o = 0
		
print(o)

Submission status: Accepted

Solution code:
import itertools
import math
import numpy as np
import fractions
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
import bisect
import sys
sys.setrecursionlimit(10**9)

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

    i = (2*X-Y)/3
    j = (2*Y-X)/3

    if i < 0 or j < 0 or not(i.is_integer() and j.is_integer()):
        print(0)
        exit()

    i = int(i)
    j = int(j)

    def comb(n, r, mod):
        r = min(r, n-r)
        res = 1
        for i in range(r):
            res = res * (n - i) * pow(i+1, mod-2, mod) % mod
        return res

    print(comb(i+j,i,p))


if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


def main():
    X, Y = map(int, input().split())

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

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

    MOD = 10 ** 9 + 7  # 法
    N = a + b  # N!までモジュラ逆数を計算する O(N)
    fact = [1, 1]  # fact[n] = (n! mod MOD)
    factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod MOD)
    inv = [0, 1]

    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)

    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

    n = a + b  # 総数
    r = min(a, b)  # 選ぶ数
    # nCr = n! * r!^-1 * (n-r)!^-1
    print(cmb(n, r, MOD))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def mod_com(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)


x, y = map(int, input().split())
mod = 10 ** 9 + 7
dif = abs(x - y)
num = min([x, y]) - dif
if num % 3 != 0:
    print(0)
    exit()
num_1 = num / 3 + dif
num_2 = num / 3
print(mod_com(int(num_1 + num_2), int(num_1), mod))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def pow(x, n , mod):
    res = 1
    while n > 0:
        if  bin(n & 1) == bin(1) :
            res = res * x % mod
        x = x*x % mod
        n = n >>1
    return res   

def combination(n,a):
    x = 1
    for i in range(a):
        x = x * (n-i) % mod
    y = 1
    for i in range(a):
        y = y * (a-i) % mod
    y = pow(y, mod-2, mod)
    return (x*y % mod)

x, y = map(int, input().split())
mod = 10**9 + 7
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:
        ans = combination(n+m,n)
        print(ans)

Submission status: Accepted

Solution code:
m = 10 ** 9 + 7
def cmb(x,y):
    r = 1
    for i in range(1, y + 1):
        r = (r * (x - i + 1) * pow(i, m-2, m)) % m
    return r

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

a = (2 * x - y) / 3
b = (2 * y - x) / 3
if (x + y) % 3 == 0 and a >= 0 and b >= 0:
    print(cmb(int((x + y) / 3), int(a)))
else:
    print(0)

Submission status: Accepted

Solution code:
def cmb(n, r, p): # 組み合わせの総数 109+7 で割ったあまりを求める Satoooh Blog 2020/02/27 4分 
    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)

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



# 初期入力
X,Y = (int(x) for x in input().split())

# X+Y が3の倍数、かつY=2XとY=X/2の間にある必要あり
kotae =0
if (X+Y) %3 !=0 or X*2< Y or Y*2 <X :
    a =b =0
else: #a(1,2) + b(2,1)=(X,Y)  の連立法手式を解く　X,Yは入力値
    b=(2*X -Y)//3
    a=X-2*b

    # (1,2)と(2,1)の数がわかったので、その組み合わせ
    if b<a:
        a,b = b,a
    #kotae = kumiawase_num(a+b,a) 
    mod =10**9 +7
    kotae = cmb(a+b,a,mod ) 
    
print(kotae)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
def nck(n, k):
    numer, denom = 1, 1
    for i in range(k):
        numer = numer * (n - i) % MOD
        denom = denom * (k - i) % MOD
    return numer * pow(denom, MOD-2, MOD) % MOD

x, y = map(int, input().split())
# (1, 2) 動く回数をm回、(2, 1) 動く回数をn回とする
n = -1
for m in range(min(x//1, y//2) + 1):
    rx = x - m
    ry = y - 2 * m
    if rx == ry * 2:
        n = ry
        break

if n == -1:
    print(0)
else:
    print(nck(m+n, min(m, n)))

Submission status: Accepted

Solution code:
mod = 10**9+7
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 mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod
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:
    A = int((2*Y-X)/3)
    B = int((2*X-Y)/3)
    print(mod_comb_k(A+B,A,mod))

Submission status: Accepted

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

mod=10**9+7
n=10**6
f=[1,1]
g=[1,1]
h=[0,1]

for i in range(2,n+1):
  f.append(f[-1]*i%mod)
  h.append((-h[mod%i]*(mod//i))%mod)
  g.append(g[-1]*h[i]%mod)
  
def cmb(n,r):
  p=f[n]*g[r]*g[n-r]%mod
  return p

if x==y:
  if x%3==0:
    print(cmb((x+y)//3,x//3))
  else:
    print(0)
elif x>y:
  if 2*y-x>=0 and (2*y-x)%3==0:
    print(cmb((x+y)//3,(2*y-x)//3))
  else:
    print(0)
else:
  if 2*x-y>=0 and (2*x-y)%3==0:
    print(cmb((x+y)//3,(2*x-y)//3))
  else:
    print(0)

Submission status: Accepted

Solution code:
import math

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

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

'''
(1, 2)をn回、(2, 1)をm回
'''

if 2*x-y >= 0 and 2*y-x >= 0 and (2*x-y) % 3 == 0 and (2*y-x) % 3 == 0:
    n = int((2*y-x)/3)
    m = int((2*x-y)/3)

    p = 10 ** 9 + 7
    N = n + m  # N は必要分だけ用意する
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]

    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)

    ans = cmb(N, m, p)

    print(ans)
else:
    print(0)

Submission status: Accepted

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

plus = X+Y

if not plus%3==0:
    print(0)
elif abs(X-Y)>plus//3:
    print(0)
else:
    row = plus//3
    col = Y-row
    l, r = 1, 1
    for c in range(col):
        l = (l*(row-c))%mod
        r = r*(c+1)%mod
    print((l*pow(r, mod-2, mod))%mod)

Submission status: Accepted

Solution code:
x, y = [int(s) for s in input().split()]

a, a_mod = divmod(2 * y - x, 3)
b, b_mod = divmod(2 * x - y, 3)
if a < 0 or a_mod != 0 or b < 0 or b_mod != 0:
    print(0)
    exit()

mod = 10 ** 9 + 7

n = a + b
temp_list = [1] * (n + 1)
for i in range(1, n + 1):
    temp_list[i] = i * temp_list[i - 1] % mod

stop = a if a < b else b
i_temp_list = [1] * (n + 1)
i_temp_list[-1] = pow(temp_list[-1], mod - 2, mod)
for i in range(n, stop, -1):
    i_temp_list[i - 1] = i_temp_list[i] * i % mod

ans = temp_list[n] * i_temp_list[a] * i_temp_list[b] % 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]
factinv = [1, 1]
inv = [0, 1]
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)

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

n = (2*Y - X) // 3
m = (2*X - Y) // 3
ans = cmb(n + m, min(n, m), p)
print(ans)