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:
MOD = 10 ** 9 + 7

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    X, Y = ZZ()
    if (X + Y)%3 != 0:
        print(0)
        return

    N = (X + Y)//3
    if abs(X - Y) > N:
        print(0)
        return
        
    fact = [0] * (N + 1) # fact[n] = n!
    ifact = [0] * (N + 1)

    for i in range(N+1):
        if i == 0:
            fact[i] = 1
            continue
        fact[i] = i * fact[i-1]
        fact[i] %= MOD
    ifact[N] = pow(fact[N], MOD-2, MOD)
    for i in range(N)[::-1]:
        ifact[i] = ((i+1) * ifact[i+1])%MOD

    m = (2*X - Y)//3
    n = (-X + 2*Y)//3

    output = fact[m+n] * ifact[m] * ifact[n] % MOD
    print(output)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 10**9+7

def modcmb(n, r, mod):
    r = min(r, n-r)
    x = 1
    y = 1
    for i in range(1,r+1):
        x *= i
        x %= MOD
        y *= n-i+1
        y %= MOD
    
    return y * pow(x, mod-2, mod) % mod


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

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

    ans = modcmb(x + y, x, MOD)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from functools import reduce

m, n = map(int, input().split())
mod = 10 ** 9 + 7


def ncr(p, k):
    if k == 0:
        return 1
    elif k < 0:
        return 0
    else:
        num = reduce(lambda x, y: x * y % mod, range(p, p - k, -1))
        den = reduce(lambda x, y: x * y % mod, range(1, k + 1))
        return num * pow(den, mod - 2, mod) % mod


if (m + n) % 3 != 0:
    print(0)
else:
    p = (m + n) // 3
    k = m - p
    print(ncr(p, k))

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


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


def main():
    mod = 10 ** 9 + 7
    input = stdin.buffer.readline
    x, y = map(int, input().split())

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

        x_min = (x + y) // 3

        print(cmb((x + y) // 3, x - x_min, mod))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def initialize_cmb(m, mod=10 ** 9 + 7):
    fac = [1]
    finv = [1]
    inv = [0] * (m + 1)
    if m >= 1:
        fac.append(1)
        finv.append(1)
        inv[1] = 1
        pre_fac = 1
        pre_finv = 1
        for i in range(2, m + 1):
            pre_fac = pre_fac * i % mod
            fac.append(pre_fac)
            inv[i] = mod - inv[mod % i] * (mod // i) % mod
            pre_finv = pre_finv * inv[i] % mod
            finv.append(pre_finv)
    return fac, finv


def cmb(n, k, fac, finv, mod=10 ** 9 + 7):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


def main():
    mod = 10 ** 9 + 7
    input = stdin.buffer.readline
    x, y = map(int, input().split())

    if (x + y) % 3 != 0 or 2 * x < y or 2 * y < x:
        print(0)
    else:
        fac, finv = initialize_cmb((x + y) // 3, mod)

        x_min = (x + y) // 3

        print(cmb((x + y) // 3, x - x_min, fac, finv, mod))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
import math
#from scipy.special import comb

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

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

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

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


ans = 0
md = 10**9+7
if((x+y)%3 != 0 or (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 = (2*x - y)//3
    n = (x+y)//3
    ans = comb(n,a,md)
    print(ans)

Submission status: Accepted

Solution code:
MOD=10**9+7

def cmb(n, r):
    if n < r: return 0 #date added
    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])
            result = result%MOD

    return result

x, y = map(int, input().split())
a = (2*y - x)/3
b = (2*x - y)/3

#print(a, b)

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

Submission status: Accepted

Solution code:
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

# nCr mod m
# modinvが必要
# rがn/2に近いと非常に重くなる
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

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

Submission status: Accepted

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

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

    n = (2*x-y)//3
    m = (2*y-x)//3
    r = min(n,m)
    result = 1
    if n < 0 or m < 0:
        print(0)
        exit()
    for i in range(r):
        result = result*(n+m-i)*inv(i+1,mod)%mod
    
else :
    result = 0

print(result)

Submission status: Accepted

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

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def mod_combinations_count(n, r, mod):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

if (x+y)%3!=0:
    print(0)
else:
    n=(x+y)//3
    m=(-x+2*y)//3
    if n<0 or m<0 or n<m:
        print(0)
        exit()
    else:
        print(mod_combinations_count(n,m,mod)%mod)

Submission status: Accepted

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

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

def mcomb(n, k):
    fac = [0] * (n + 1)
    fac[0] = 1
    for i in range(1, n + 1):
        fac[i] = fac[i - 1] * i % 1000000007


    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], 1000000005, 1000000007) * pow(fac[k], 1000000005, 1000000007) % 1000000007

N = (-1*X+2*Y)//3
M = (2*X-Y)//3
print(mcomb(N+M, N)%(10**9+7))

Submission status: Accepted

Solution code:
# a**bのmodを取りたい時に高速にできる
def modpow(a, n, mod):
    res = 1
    # 45 = 101101
    # ここでいう、1X11X1の部分飲み計算すれば良い
    # a**45 = a**32 + a**8 + a**4 + a**1なので、これだけ計算すれば良い
    # そしてそのためには、45を2進数に変えて、右ビットシフトしていけばok
    # なので、n >>= 1をする
    # ex)45,22,11,5,2,1
    while (n > 0):
        # print(n, a, res)
        # 3&1みたいな論理積とった結果、両方1のものがあった場合にresにたす
        if n & 1:
            res = res * a % mod
        # a = 掛け算の結果を更新する。
        # a*b の mod(c)は。a mod(c)*b mod(c)と同じなので、掛け算するaもmodをとっていく
        a = a * a % mod
        # n>>1で、1桁ずつ減らしていく
        # 101101 > 10110みたいな
        # 先頭の1文字が減るわけではない。45->45-32みたいな感じではない
        # でも、やりたいのは、1X11X1の部分のみ計算するための、右bitシフトなので45->22の部分に特に意味はない
        # 101101 > 10110をすることで末尾が一つずつ消していけることが重要
        # n=n>>1をすることで二進法展開ができる
        n = n >> 1
    return res


def modcomb(n, r, mod):
    if r > n - r:
        r = n - r
    nPr, rPr = 1, 1
    for i in range(r):
        nPr = nPr * (n - i) % mod
        rPr = rPr * (i + 1) % mod
    # print(n, r, nPr, rPr)
    # nCrのmodを高速に取りたい
    # nCr は nPr / rPr
    # 1/(33333P33333)のmodを取りたい
    # 1/277540578 のmodを取りたい
    # print(nPr, modpow(rPr, mod - 2, mod))
    # nCrのmodを高速にとる。nPr / rPr を nPr * (1/rPr)に分ける
    # modにおいて、rPrにbをかけると1になる。そのようなbがrPrの逆元である
    return nPr * modpow(rPr, mod - 2, mod) % mod


def main():
    X, Y = map(int, input().split())
    n = (-X + 2 * Y) / 3
    m = (2 * X - Y) / 3
    # これで(i+1,j+2)をとる回数がn回(i+2,j+1)をとる回数がm回だとわかる
    # 少数が出てきたら計算できないので0を返す
    if not(n.is_integer() and m.is_integer()):
        return 0
    if n >= 0 and m >= 0:
        # n+mCnを計算する。modを高速にとる
        return modcomb(int(n + m), int(n), mod=10 ** 9 + 7)
    else:
        return 0


print(main())
# print(modpow(277540578, 10**9 + 5, 10**9 + 7))

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:
import math
import time

def rpt_fact(a,b):
    mod = 10 ** 9 + 7
    txt = bin(b)[2:]
    ls = [a]
    res = []
    for i in range(len(txt)):
        ls.append(ls[-1]**2 % mod)
    for i in range(1,len(txt)+1):
        if txt[-i] == "1":
            res.append(ls[i-1])
    ans = 1
    for i in res:
        ans *= i
        ans % mod
    return ans


[x,y] = [int(i) for i in input().split()]
st = time.time()
mod = 10 ** 9 + 7


if (x + y) % 3 != 0:
    print(0)
else:
    #(1,2)がa回,(2,1)がb回
    #-a+b
    _atb = x - y
    atb = (x + y)//3
    a = (atb - _atb)//2
    b = (atb + _atb)//2
    #a+b C a
    if a < 0 or b < 0:
        print(0)
    elif a == 0 or b == 0:
        print(1)
    else:
        n = a + b
        r = min(a,b)
        son = n
        mom = r

        for i in range(1,r):
            son *= (n - i)
            mom *= i
            son %= mod
            mom %= mod
        mom = rpt_fact(mom,mod-2) % mod
        # mom ** (mod - 2)
        print(son*mom % mod)
        #print(time.time()-st)

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

x = X % 3
y = Y % 3

sa = X - Y
to = ( X + Y ) // 3
aa = ( sa + ( X + Y ) // 3 ) // 2

ans = 1

if x == 0 and y == 0:
  print(cmb(to, aa, p))

elif x == 1 and y == 2:
  print(cmb(to, aa, p))
        
elif x == 2 and y == 1:
  print(cmb(to, aa, p))
  
else:
  print(0)

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


X, Y = map(int, input().split())
p = 10 ** 9 + 7
turn = (X + Y)//3
N = turn + 10  # 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)

if (X + Y) % 3 != 0:
    print(0)
    exit()
turn = (X + Y)//3
move1 = (Y - X + turn) //2
move2 = (X - Y + turn) //2

print(cmb(turn, move1, p))

Submission status: Accepted

Solution code:
#ABC145D
def main():
    import sys, math
    X, Y = map(int, sys.stdin.readline().split())
    '''
    i +2*j ==X
    2*i +j ==Y
    '''
    if (2*Y-X)%3==0:
        i = (2*Y-X)//3
        j = Y-2*i
    else:
        i,j=0,0
    #print(i, j)
    mod = 10**9+7
    def calc(n):
        ans = 1
        for i in range(n, 1, -1):
            ans *= i
            ans %= mod
        return ans
    
    ans = calc(i+j)
    #print(calc(-1))
    #print(ans)
    
    #calc2(calc(i), mod-2)
    gg1 = pow(calc(i), mod-2, mod)
    gg2 = pow(calc(j), mod-2, mod)
    
    if i<0 or j<0:
        print(0)
    elif i==0 and j==0:
        print(0)
    else:
        print(ans*gg1*gg2%mod)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    def main():
        X,Y=map(int,input().split())
        n=(-X+2*Y)/3
        m=(2*X-Y)/3

        # https://atcoder.jp/contests/abc156/submissions/11621672
        def modpow(a, b, mod=10 ** 9 + 7):
            ret = 1
            while b > 0:
                if b % 2 == 1:
                    ret = ret * a % mod
                a = a * a % mod
                b //= 2
            return ret
        
        
        def modcomb(n, c, mod=10 ** 9 + 7):
            if c > n - c:
                c = n - c
            u, d = 1, 1
            for i in range(c):
                u = u * (n - i) % mod
                d = d * (i + 1) % mod
            return u * modpow(d, mod - 2) % mod
        
        
        """mod = 10 ** 9 + 7
        n, a, b = map(int, input().split())
        ans = (modpow(2, n) - 1) % mod
        ans = (ans-modcomb(n, a)) % mod
        ans = (ans-modcomb(n, b)) % mod
        print(ans)"""
        
        # combどうしの積をとると余りがずれるので避ける！　普通のcombを計算して最後にmodをとって。
        
        # comb(n + k - 1, n) # 重複組み合わせkHn．k種類の箱にn個の玉        
        if n.is_integer() and m.is_integer() and n>=0 and m>=0:
            return modcomb(int(n+m),int(n))
        else: return 0
    print(main())
    
resolve()

Submission status: Accepted

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

SIZE=10**6+1; MOD=10**9+7 #998244353 #ここを変更する
 
SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD
 
def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0
 
print(choose(X+Y,X))

Submission status: Accepted

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

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

#2 * left + up * 4 = 2 * x
#left * 2 + up = y

up = (2 * x - y) // 3
left = (2 * y - x) // 3

if up < 0 or left < 0:
    print(0)
    exit()

#互いに素な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

#(up + left)C(up)
mod = 10**9 + 7
res = 1
for i in range(1, left + up + 1):
    res = res * i % mod
for i in range(1, up + 1):
    res = res * mod_inv(i, mod) % mod
for i in range(1, left + 1):
    res = res * mod_inv(i, mod) % mod
print(res % 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

m = 2 * x - y
n = 2 * y - x
if m >= 0 and n >= 0 and m % 3 == 0 and n % 3 == 0:
    print(com((n + m) // 3, n // 3, mod))
else:print(0)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """

    def __init__(self, n_max, mod=10 ** 9 + 7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        if n < r:
            return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n + 1):
            fac.append(fac[i - 1] * i % self.mod)
            facinv.append(facinv[i - 1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n + 1)
        modinv[1] = 1
        for i in range(2, n + 1):
            modinv[i] = self.mod - self.mod // i * modinv[self.mod % i] % self.mod
        return modinv

    def comb_with_repetition(self, n, r):
        # 重複組み合わせ
        return self.__call__(n + r - 1, r)


def main():
    X, Y = map(int, input().split())
    if (X + Y) % 3 != 0:
        print(0)
        return
    else:
        if Y > 2 * X:
            print(0)
            return
        if 2 * Y < X:
            print(0)
            return

        comb = Combination(n_max=10 ** 6 + 1)
        n = (X + Y) // 3
        r = X - n
        ans = comb(n, r)

        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
x, y= map(int, input().split())
mod=10**9+7
import math
a=(2*y-x)//3
b=(2*x-y)//3

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

else:
	L=[1]*(a+b+1)
	for i in range(1,a+b+1):
		L[i]=L[i-1]*i
		L[i]=L[i]%mod
	p=pow(L[a], mod-2, mod)
	q=pow(L[b], mod-2, mod)
	ans=(L[a+b]*p*q)%mod
	print(ans)

Submission status: Accepted

Solution code:

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

a, s = divmod(2*X - Y, 3)
b, t = divmod(-X + 2*Y, 3)

mod = 10 ** 9 + 7
N = 10 ** 6
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]

def cmb(n, r, mod):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fac[n] * ( finv[r] * finv[n-r] % mod ) % mod
 
for i in range(2, N + 1):
  fac.append(( fac[-1] * i ) % mod)
  inv.append(mod - ( inv[mod % i] * (mod // i)) % mod)
  finv.append( finv[-1] * inv[-1]  % mod)

if s != 0 or t !=0:
  print(0)
else:
  print(cmb(a+b, a, mod))

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
if (x+y)%3 != 0:
    print(0)
    quit()
elif x < (x+y)//3 or y < (x+y)//3:
    print(0)
    quit()
else:
    n = (x+y)//3
    r = x-n

mod = 10**9+7
def cmb(n,r,mod):
    r = min(r, n-r)
    return (fact[n] * factinv[r] * factinv[n-r]) % mod
def makefact(n,mod):
    fact = [1,1]
    factinv = [1,1]
    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)
    return fact,factinv
fact,factinv = makefact(n,mod)

print(cmb(n,r,mod))

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline
    x,y=map(int, readline().rstrip().split())
    z=2*x-y
    if z%3 != 0 or z < 0:
        print(0)
        return
    b=z//3
    a=x-2*b
    if a < 0:
        print(0)
        return
    mod=10**9+7
    n=a+b
    r=min(a,b)

    ans=1

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

if 'doTest' not in globals():
    resolve()
    sys.exit()

Submission status: Accepted

Solution code:
import math

x, y = map(int, input().split())
mod = 10 ** 9 + 7
a = (2 * y - x) / 3
b = (2 * x - y) / 3

if (not a.is_integer()) or (not b.is_integer()) or \
    (a < 0) or (b < 0):
    print(0)
else:
    a, b = int(a), int(b)
    I = [1] * (a + b + 1)
    for n in range(1, a+b+1):
        I[n] = I[n-1] * n
        I[n] %= mod
    i, j, k = I[a+b], I[a], I[b]
    j = pow(j, mod-2, mod)
    k = pow(k, mod-2, mod)

    ans = i * j * k
    ans %= mod
    print(ans)

Submission status: Accepted

Solution code:
X, Y = map(int, input().split())
mod = 10**9+7
b = (2*Y-X)//3
a = Y - 2*b
max_num = a + b + 5
facts = [1 for i in range(max_num)]
invs = [1 for i in range(max_num)]
 
def inv(x):
    return pow(x,mod-2,mod)
 
for i in range(1,max_num):
    facts[i] = facts[i-1]*i%mod
    invs[i] = inv(facts[i])
 
def nCk(n,k):
    try:
        return facts[n]*invs[k] * invs[n-k] % mod
    except IndexError:
        print(n, k, len(facts), len(invs))
if (X+Y)%3 == 0 and a>=0 and b >=0:
    print(nCk(a+b, a))
else:
    print(0)

Submission status: Accepted

Solution code:
import sys


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


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """

    def __init__(self, n_max, mod=10 ** 9 + 7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        if n < r:
            return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n + 1):
            fac.append(fac[i - 1] * i % self.mod)
            facinv.append(facinv[i - 1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n + 1)
        modinv[1] = 1
        for i in range(2, n + 1):
            modinv[i] = self.mod - self.mod // i * modinv[self.mod % i] % self.mod
        return modinv


def main():
    X, Y = map(int, input().split())
    if (X + Y) % 3 != 0:
        print(0)
        return
    a = (X + Y) // 3
    two = X - a
    if two < 0:
        print(0)
        return
    if two == 0:
        print(1)
        return
    cmb = Combination(a + 1)
    print(cmb(a, two))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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

n = (X + Y) // 3
x = (2 * X - Y) // 3
y = (-X + 2 * Y) // 3
if (X + Y) % 3 or x < 0 or y < 0:
    print(0)
    exit()


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


print(mod_com(n, x))

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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

n = (X + Y) // 3
x = (2 * X - Y) // 3
y = (-X + 2 * Y) // 3
if (X + Y) % 3 or x < 0 or y < 0:
    print(0)
    exit()


def mod_com(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    if k > n - k:
        k = n - k
    if k == 0:
        return 1
    ans = 1
    for i in range(n - k + 1, n + 1):
        ans = ans * i % MOD

    inv = [0] * (k + 1)
    inv[1] = 1
    for i in range(2, k + 1):
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        ans = ans * inv[i] % MOD

    return ans


print(mod_com(n, x))

Submission status: Accepted

Solution code:
def com(x,y,mod):
    bunb = 1
    buns = 1
    for i in range(y):
        buns = buns * (x-i) % mod
        bunb = bunb * (i+1) % mod
 
    bunb_inv = pow(bunb,mod-2,mod)
    d = (buns * bunb_inv) % mod
    return (buns*pow(bunb,mod-2,mod))%mod

x,y = map(int,input().split())
setcou = 0
katacou = 0
while True:
    if x * 2 == y or y * 2 == x:
        katacou = min(x,y)
        break
    elif x < 3 or y < 3:
        print(0)
        exit()
    elif x >= 3 and y >= 3:
        setcou += 1
        x -= 3
        y -= 3

print(com(setcou*2+katacou,setcou,10**9+7))

Submission status: Accepted

Solution code:
def fact(n, k, mod):
    res = 1
    for i in range(k):
        res = res * (n - i) % mod
    return res

def c(x, y, mod):
    y = min(x, x - y)
    return (fact(x, y, mod) * pow(fact(y, y, mod), mod - 2 , mod)) % mod

P = 10**9 + 7
X, Y = map(int, input().split())
if (X + Y) % 3 > 0:
    print(0)
    exit()
n = (X + Y) // 3
x = X - n
y = Y - n
if 0 > x or 0 > y:
    print(0)
    exit()
print(c(x + y, x, P))

Submission status: Accepted

Solution code:

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

def div(a, b):
    return a*power(b, mod-2)%mod

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

if y>2*x or x>2*y:
    print(0)
elif (x+y)%3!=0:
    print(0)
else:
    w1=(2*y-x)//3
    h1=(2*x-y)//3

    mod=10**9+7

    ic=1
    ih=1
    for i in range(h1):
        ic=ic*(w1+1+i)%mod
        ih=ih*(i+1)%mod

    ic=div(ic,ih)

    print(ic)

Submission status: Accepted

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

N = 10**6+1
def pow_mod(x, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return pow_mod(x * x % MOD, n // 2) % MOD
    else:
        return x * pow_mod(x * x % MOD, n // 2) % MOD

fact = [1]
for i in range(1,N+1):
    fact.append( (fact[i-1] * i) % MOD )

inv = [1] * (N+1)
inv[N] = pow_mod(fact[N], MOD-2)
for i in range(N, 1, -1):
    inv[i-1] = inv[i] * (i) % MOD

def cmb_mod(n,r):
    return fact[n] * inv[r] * inv[n-r] % MOD


if (X+Y) % 3 != 0:
    print(0)
else:
    n = (2*X - Y) // 3
    m = (2*Y - X) // 3
    if n < 0 or m < 0:
        print(0)
    else:
        print(cmb_mod(n+m, n))

Submission status: Accepted

Solution code:
"""
組み合わせ, nCrのmod

(i+1, j+2)で動く回数をm回、(i+2, j+1)で動く回数をn回とすると
m + 2n = x
2m + n = y
の方程式の解として、m,nが0以上の整数で求められる必要がある

m,nが0以上の整数で求められなければそのような行き方はない
求められれば、全部でm+n回の動きの中でどのm回で(i+1, j+2)の動きをするか（ないし、どのn回で(i+2, j+1)の動きをするか）が行き方の数なので、m+nCmを求めれば良い
"""
x,y = map(int, input().split())

mod = 10**9+7

def choose(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 # modの世界では逆元はpow(x,mod-2)をかけることと同じ

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

#if n >= 0 and m >= 0 and int(n)*10 == n*10 and int(m)*10 == m*10:
#    ans = choose(int(m+n), int(m))
if n >= 0 and m >= 0 and not n%1 and not m%1:
    ans = choose(int(m+n), int(m))
else:
    ans = 0
print(ans)

Submission status: Accepted

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

mod = 10**9+7

def choose(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 # modの世界では逆元はpow(x,mod-2)をかけることと同じ

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

if n >= 0 and m >= 0 and int(n)*10 == n*10 and int(m)*10 == m*10:
    ans = choose(int(m+n), int(m))
else:
    ans = 0
print(ans)

Submission status: Accepted

Solution code:
X,Y = map(int,input().split())
# 何回移動するか
r = (X+Y)//3
# 移動の可能性 rC(x-r)
from functools import reduce
mod = 10**9+7

if (X+Y)%3==0 and X<= 2*Y and Y<= 2*X :
    r = (X+Y)//3
    l = min
    if r != X and r != Y:
        num = reduce(lambda x,y:x*y%mod,[k+1 for k in range(r)])
        p = reduce(lambda x,y:x*y%mod,[k+1 for k in range(X-r)])
        q = reduce(lambda x,y:x*y%mod,[k+1 for k in range(2*r-X)])
        ans = num*pow(p,mod-2,mod)*pow(q,mod-2,mod)%mod
        print(ans%mod)   
    else:
        print(1)
else:
    print(0)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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

n = (X + Y) // 3
x = (2 * X - Y) // 3
y = (-X + 2 * Y) // 3
if (X + Y) % 3 or x < 0 or y < 0:
    print(0)
    exit()

MOD = 1000000007
COM_MAX = n

fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1

for i in range(2, COM_MAX + 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


def mod_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


print(mod_com(n, x))

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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

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

n = (X + Y) // 3
x = (2 * X - Y) // 3
y = (-X + 2 * Y) // 3
if x < 0 or y < 0:
    print(0)
    exit()

MOD = 1000000007
COM_MAX = n

fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1

for i in range(2, COM_MAX + 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


def mod_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


print(mod_com(n, x))