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:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


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


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


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


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


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

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

    return ret


MOD = 10**9 + 7

X, Y = read_ints()
if (X + Y) % 3 != 0 or Y / X > 2 or Y / X < 1 / 2:  # !=0
    print(0)
    exit()

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


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


# def com(n, k, mod):
#     if k == 0:
#         return 1
#     s = n
#     mod = 10**9 + 7
#     inv = [0, 1]
#     for c in range(2, k + 1):
#         inv.append((-(mod // c) * inv[mod % c]) % mod)
#         s = (((s * (n + 1 - c)) % mod) * inv[c]) % mod
#     return s


a = combination(pascal_depth, pascal_k, MOD)
print(a)

Submission status: Accepted

Solution code:
def comb(n,k):
  s=1
  r=min(k,n-k)
  p=10**9+7
  for c in range(r):
    s=(s*(n-c)*pow(c+1,p-2,p))%p
  return s

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

if (x+y)%3:
  print(0)
else:
  m=y-(x+y)//3
  n=x-(x+y)//3
  if m < 0 or n < 0:
    print(0)
  else:
    print(comb(m+n,m))

Submission status: Accepted

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


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


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


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


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


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

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

    return ret


MOD = 10**9 + 7

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

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

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


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


a = cmb(pascal_depth, pascal_k, MOD)
print(a)

Submission status: Accepted

Solution code:
import sys
import math
from operator import mul
from functools import reduce
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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= (int(_) for _ in input().split()) 
if (x+y)%3!=0:
    print(0)
    sys.exit()
else:
    n=(x+y)/3
    n=int(n)
    if x<n or y<n:
         print(0)
         sys.exit()
    else:
        x=x-n
        y=y-n
        ans=int(cmb(x+y, x,mod))
        print(ans%1000000007)

Submission status: Accepted

Solution code:


def com(n,k):
    if k==0:
        return 1
    s=n
    p=10**9+7
    inv=[0,1]
    for c in range(2,k+1):
        inv.append((-(p//c)*inv[p%c])%p)
        s=(((s*(n+1-c))%p)*inv[c])%p
    return s


x,y=map(int,input().split())
if (x+y)%3!=0 or 2*y<x or 2*x<y:
    print(0)
else:
    r=min(2*y-x,2*x-y)//3
    print(com((x+y)//3,r))

Submission status: Accepted

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

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

if X % 3 == 1 and Y % 3 == 1:
    print(0)
    exit()
if X % 3 == 2 and Y % 3 == 2:
    print(0)
    exit()

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


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

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



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

Submission status: Accepted

Solution code:
def mp(a,n,mod):
    if n==1:
        return a%mod
    aq=(mp(a,n//2,mod))**2
    ar=a**(n%2)
    return (((aq)%mod)*ar)%mod


def s_comb(n,k):
    s=1
    r=min(k,n-k)
    p=10**9+7
    for c in range(r):
        s=(s*(n-c)*mp(c+1,p-2,p))%p
    return s

x,y=map(int,input().split())
if (x+y)%3!=0 or 2*y<x or 2*x<y:
    print(0)
else:
    r=int(min(2*y-x,2*x-y)/3)
    print(s_comb(int((x+y)/3),r))

Submission status: Accepted

Solution code:
def d_knight():
    X, Y = [int(i) for i in input().split()]

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

    if not (X <= 2 * Y and Y <= 2 * X):
        return 0

    n, m = (-X + 2 * Y) / 3, (2 * X - Y) / 3
    if not (n.is_integer() and m.is_integer()):
        return 0

    n, m = int(n), int(m)
    return combination(n + m, n, 10**9 + 7)

print(d_knight())

Submission status: Accepted

Solution code:


def s_comb(n,k):
    s=1
    r=min(k,n-k)
    p=10**9+7
    for c in range(r):
        s=(s*(n-c)*pow(c+1,p-2,p))%p
    return s


x,y=map(int,input().split())
if (x+y)%3!=0 or 2*y<x or 2*x<y:
    print(0)
else:
    r=min(2*y-x,2*x-y)//3
    print(s_comb((x+y)//3,r))

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
m=10**9+7
if (2*x-y)%3==0 and (2*y-x)%3==0 and 2*x>=y and 2*y>=x:
    a,b=(2*x-y)//3,(2*y-x)//3
    c=min(a,b)
    p=1
    for i in range(c):
        p=(p*(a+b-i)*pow(i+1,m-2,m))%m
    print(p)
else:
    print(0)

Submission status: Accepted

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

def nCk(n, k, mod=10**9+7):
  
  ans = 1
  for i in range(1, k+1):
    ans = ans*(n-i+1)*pow(i, mod-2, mod)%mod
    
  return ans

ans = 0

if (2*x-y)%3==0 and (2*y-x)%3==0 and 2*y-x>=0 and 2*x-y>=0:
  k = (2*x-y)//3
  l = (2*y-x)//3
  
  ans = nCk(k+l, min(k, l))

print(ans)

Submission status: Accepted

Solution code:
x, y = map(int, input().split())
n = (2*y - x)//3 
m = (2*x - y)//3
mod = 10**9+7
def inv(x):
        return pow(x, mod-2, mod)
def fact(x):
        f = 1 
        for i in range(1, x + 1): 
                f *= i
                f %= mod    
        return f
def comb(n, r): 
        return (fact(n) * inv(fact(n-r)) * inv(fact(r))) % mod 
res = comb(n+m, m)
if (x + y) % 3 == 0 and n >= 0 and m >= 0:
        print(res)
else:
        print(0)

Submission status: Accepted

Solution code:
import subprocess
import os
import time


import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

input = sys.stdin.readline


mod = 10**9+7
N = 10**6
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]


# def find_n(x, y):
#     moves = int((x+y)/3)
#     for n in range(moves+1):
#         if n + (moves-n)*2 == x and n*2 + (moves-n) == y:
#             return n % mod, (moves-n) % mod


# def cmb(n, r):
#     return math.factorial(n) % mod // ((math.factorial(r) % mod) * (math.factorial(n-r) % mod))


def cmb(n, r):
    if r < 0 or r > n:
        return 0
    r = min(r, n-r)

    return g1[n] * g2[r] * g2[n-r] % mod


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

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

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

    # n, m = find_n(x, y)

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

    ans = cmb(n+m, n)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
ts=time.time()
sys.setrecursionlimit(10**6)
#input=sys.stdin.readline().rstrip
show_flg=False
show_flg=True

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo
        
ans=0

s,t=LI()
a=(2*t-s)//3
b=(2*s-t)//3


if (2*t-s)%3!=0 or (2*s-t)%3!=0:
    print(0)
    exit()

cm=Comb(a+b+1+1)
ans=cm.comb(a+b,min(a,b))
print(ans)

Submission status: Accepted

Solution code:
def cmb(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    """
    階乗テーブル、逆元の階乗テーブルを作成する
    """
    fac = [1, 1] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)
    
    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


X, Y = map(int, input().split())
# 後の、n, mの大小を一定にするため
if X > Y:
    X, Y = Y, X
dist = X + Y
   
if dist % 3 != 0:
    print(0)
else:
    # (+1,+2) の移動の回数を n、(+2,+1) の移動の回数を m とする)
    # total = n + m
    # 以下の式は、2n + m = X, n + 2m = Y の連立方程式を解いた結果
    total = int((X+Y) / 3)
    n = X - total
    
    # n < 0 もしくは m < 0 の場合、たどり着けない
    # Y > X なので、m > n
    # n < 0 → 2X - Y < 0
    if Y > 2*X:
        print(0)
    else:
        MOD = 10**9 + 7

        fac, ifac = make_tables(MOD, total)
        ans = cmb(total, n, MOD, fac, ifac)
        print(ans)

Submission status: Accepted

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

mod = 10**9 + 7
n = (2*y - x) // 3 # (+1, +2)
m = (2*x - y) // 3 # (+2, +1)
N = 10**6
g1 = [1,1]
g2 = [1,1]
inverse = [0,1]

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


if __name__ == '__main__':
    if (x+y) % 3 != 0:
        print(0)
        exit()
    if n < 0 or m < 0:
        print(0)
        exit()
    sum = n + m
    r = min(n,m)

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

    print(comb(sum,r,mod))

Submission status: Accepted

Solution code:
Z = 10 ** 9 + 7


def z_pow(a, n):
    # a ^ n
    if n == 0:
        return 1
    if n == 1:
        return a % Z
    m = n // 2
    i = n - m * 2
    x = z_pow(a, m)
    return (x * x * z_pow(a, i)) % Z


def n_comb(n, i):
    if n - i < i:
        return n_comb(n, n - i)
    e = [1 for j in range(n + 1)]
    for j in range(n):
        e[j + 1] = (e[j] * (j + 1)) % Z
    return (e[n] * z_pow(e[i], Z - 2) * z_pow(e[n - i], Z - 2)) % Z


def calc(X, Y):
    if (X + Y) % 3 != 0:
        return 0
    n = (X + Y) // 3
    if X < n or Y < n:
        return 0
    return n_comb(n, X - n)


(X, Y) = tuple([int(s) for s in input().split()])
print(calc(X, Y))

Submission status: Accepted

Solution code:


g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル

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

mod = 10**9+7 #出力の制限



def resolve():
    global g1
    global g2
    X,Y=(int(i) for i in input().split())
    if (2*X-Y)%3!=0 or 2*X-Y <0:
        print(0)
        return 
    if (2*Y-X)%3!=0 or 2*Y-X <0:
        print(0)
        return 
    a=(2*X-Y)//3
    b=(2*Y-X)//3

    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル

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

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def main():
    X, Y = (int(i) for i in input().split())
    fac = [0] * max(X, Y)
    finv = [0] * max(X, Y)
    inv = [0] * max(X, Y)
    MOD = (10**9) + 7

    def COMinit(m):
        fac[0] = 1
        finv[0] = 1
        if m > 1:
            fac[1] = 1
            finv[1] = 1
            inv[1] = 1
            for i in range(2, m):
                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

    COMinit(max(X, Y))
    if (X+Y) % 3 != 0:
        return print(0)
    n = (2*Y - X) // 3
    m = (2*X - Y) // 3
    print(COM(n+m, m))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def combination_modp(n, r, p): # nCr modpを求める
    r = min(n-r, r)
    result = 1
    for i in range(n, n-r, -1):
        result *= i
        result %=p
    for i in range(1, r+1):
        result *= pow(i,p-2,p)
        result %= p
    return result

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

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

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

ans = combination_modp(a+b,a,mod)
print(ans)

Submission status: Accepted

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

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


def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

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

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

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

    return result

print(cmb(a+b,a)%mod)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
X, Y = map(int, input().split())

mod = 10 ** 9 + 7

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

a = int(a)
b = int(b)
N = a + b
f = [1]
for i in range(1,a+b+1):
    f.append((f[-1] * i) % mod)
ans = f[a+b] * (pow(f[a], mod-2, mod) * pow(f[b], mod-2, mod) % mod) % mod
print(ans)

Submission status: Accepted

Solution code:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
 
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
 
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
 
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
 
    return result
x,y = map(int,input().split())
mod=10**9+7
if (x+y)%3!=0 or x>2*y or y>2*x:
  print('0')
else:
  p=(2*y-x)//3
  q=(2*x-y)//3
  print(cmb(p+q,p)%mod)

Submission status: Accepted

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

def comb(n,r,mod, g):
    if r < 0 or n < r: return 0
    return g[n] * pow(g[r], mod-2, mod) * pow(g[n-r], mod-2, mod) % mod

def cmb_mod(n, r, mod):
    g = [1,1]
    for i in range(2, n+1):
        g.append( (g[-1] * i) % mod)
    return comb(n, r, mod, g)

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

Submission status: Accepted

Solution code:


def s_comb(n,k):
    s=1
    r=min(k,n-k)
    p=10**9+7
    for c in range(r):
        s=(s*(n-c)*pow(c+1,p-2,p))%p
    return s

x,y=map(int,input().split())
if (x+y)%3!=0 or 2*y<x or 2*x<y:
    print(0)
else:
    r=int(min(2*y-x,2*x-y)/3)
    print(s_comb(int((x+y)/3),r))

Submission status: Accepted

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

if (X+Y) % 3 != 0:
    print(0)
else:
    n = (2*Y-X)//3
    m = (2*X-Y)//3
    '''
    n*(1,2) + m*(2,1) = (x, y)
    x = n+2m
    y = 2n+m
    2x = 2n+4m
    2x-y = 3m
    m = (2x-y)/3
    n = (2y-x)/3 
    '''
    if 0 > n or 0 > m:
        print(0)
    else:
        ans = 1
        for i in range(1,n+1):
            ans *= (n+m+1-i)*pow(i,mod-2,mod)
            ans %= mod
        print(ans)

Submission status: Accepted

Solution code:
import math

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

if __name__ == "__main__":
    X, Y = map(int, input().split())

    #initial: (X,Y) = (0,0)

    num = 10**9 + 7
    sum = 0
    #print(num)
    for i in range(X+1):# i は1step回数。２stepを行う回数は(X-i)//2(余りあったらbreak)
        if (X-i)% 2 == 0:
            j = (X-i)//2
            #print("i and j is ", i, j)
            if i * 2 + j  == Y:
                #conbination_num1 = (math.factorial(i + j) / math.factorial(i)) % num
                sum += combination(i+j, i, num)  

    print(int(sum))

Submission status: Accepted

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

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

def main():
    if (X+Y) % 3 or X > 2*Y or Y > 2*X:
        print(0)
        return
    n = (X+Y) // 3
    r = Y - n
    print(combination(n, r))

main()

Submission status: Accepted

Solution code:
mod = 10**9 + 7

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
N = 10**6

def main():
    x, y = map(int, input().split(' '))
    if (2*x-y) % 3 == 0 and (2*y-x) % 3 == 0:
        n = (2*x-y) // 3
        m = (2*y-x) // 3
        for i in range( 2, N + 1 ):
            g1.append( ( g1[-1] * i ) % mod )
            inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
            g2.append( (g2[-1] * inverse[-1]) % mod )
        print(cmb(n+m, n, mod))
    else:
        print(0)


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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



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

Submission status: Accepted

Solution code:
def sq(a, b, mod):  # aのb乗を剰余,kは初期値#20191116-D-Knight
    if b == 0:
        return 1
    elif b % 2 == 0:
        return sq(a, b // 2, mod)**2 % mod
    else:
        return sq(a, b - 1, mod) * a % mod


def nCk(n, k, mod=10**9 + 7):
    x = max(k, n - k)
    y = min(k, n - k)
    kkai = 1
    for i in range(2, y + 1):
        kkai = (kkai * i) % mod
    nkkai = 1
    for i in range(x + 1, n + 1):
        nkkai = (nkkai * i) % mod
    answer = sq(kkai, mod - 2, mod) * nkkai % mod
    return answer


from sys import exit
X, Y = map(int, input().split())
if (X + Y) % 3 != 0:
    print(0)
    exit()

if X % 2 == 0:
    syurui = X - (X // 2) + 1
else:
    syurui = X - (X // 2)
for i in range(syurui):
    two = i
    one = X - two * 2
    if (two + one * 2) == Y:
        print(nCk(two + one, two))
        exit()
print(0)

Submission status: Accepted

Solution code:
#lにa回、rにb回進む
x,y = map(int,input().split())
#x = a +2b
#y = 2a+b
#x+y = 3a+3b
#a+b = (x+y)/3
#b=x-a+b
b = x-(x+y)/3
a = (x-2*b)
ans = 0
#print("a:{} b:{}".format(a,b))
if a<0 or b<0 or b-int(b)>0.00001 or a-int(a)>0.00001:
  print(ans)
  exit()

MAX = int(a+b)+1
MOD = 1000000007

fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]

#テーブルを作る前処理
def COMinit():
    fac[0],fac[1] = 1,1
    finv[0],finv[1] = 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

COMinit()
print(COM(int(a+b),int(a)))

Submission status: Accepted

Solution code:
#lにa回、rにb回進む
x,y = map(int,input().split())
#x = a +2b
#y = 2a+b
#x+y = 3a+3b
#a+b = (x+y)/3
#b=x-a+b
b = x-(x+y)/3
a = (x-2*b)
ans = 0
#print("a:{} b:{}".format(a,b))
if a<0 or b<0 or b-int(b)>0.00001 or a-int(a)>0.00001:
  print(ans)
  exit()
 
MAX = 1000000;
MOD = 1000000007;
 
fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]
 
#テーブルを作る前処理
def COMinit():
    fac[0],fac[1] = 1,1
    finv[0],finv[1] = 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
 
COMinit()
print(COM(int(a+b),int(a)))

Submission status: Accepted

Solution code:
def comb(n, k, mod):
    if k > (n // 2):
        k = n - k
    a = 1
    for i in range(k):
        a = (a * (n - i)) % mod
    b = 1
    for i in range(k - 1):
        b = (b *(k - i)) % mod
    a = (a * pow(b, mod - 2, mod)) % mod
    return a


X, Y = map(int, input().split())
ans = 0
mod = 10 ** 9 + 7
if X > Y:
    X, Y = Y, X
##Yのほうが大きいとして考える
if not (X + Y) % 3 == 0 or Y > 2 * X:
    ans = 0
else:
    n = (X + Y) // 3
    d = Y - X
    a = 2*n - X
    ans = comb(n, a, mod)
print(ans)

Submission status: Accepted

Solution code:
#abc145d
import sys

def com(n,r,m):
 f=[1,1]
 for i in range(2,n+1):
  f.append(f[i-1]*i%m)
 return f[n]*pow(f[r]*f[n-r]%m,m-2,m)%m

mod=10**9+7
x,y=map(int,raw_input().split())
z=(x+y)/3
if (x+y)%3 or abs(x-y)>z:
 print 0
 sys.exit()
print com(z,x-z,mod)

Submission status: Accepted

Solution code:
def comb(n, k, mod):
    if k > (n // 2):
        k = n - k
    a = 1
    for i in range(k):
        a *= (n - i)
        a %= mod
    for i in range(k - 1):
        a = (a * pow(k - i, mod - 2, mod)) % mod

    return a

X, Y = map(int, input().split())
ans = 0
mod = 10 ** 9 + 7
if X > Y:
    X, Y = Y, X
##Yのほうが大きいとして考える
if not (X + Y) % 3 == 0 or Y > 2 * X:
    ans = 0
else:
    n = (X + Y) // 3
    d = Y - X
    a = 2*n - X
    ans = comb(n, a, mod)
print(ans)

Submission status: Accepted

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

def cmb(n, r, mod):
    from operator import mul
    from functools import reduce

    N = n + r
    g1 = [1, 1]  # 元テーブル
    g2 = [1, 1]  # 逆元テーブル
    inverse = [0, 1]  # 逆元テーブル計算用テーブル

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

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


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

else:
    a = (x + y)//3
    b = x-a

    if x-a <0 or y-a <0:
        ans = 0
    else:
        mod = 10**9+7 #出力の制限
        ans = cmb(a, b, mod)

print(int(ans))

Submission status: Accepted

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

MOD = 1000000007

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

        return int(fac[n] * finv[r] * finv[n - r] % mod)

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

if (x + y) % 3 != 0:
    print(0)
else:
    print(comb_mod(n + m, n, MOD))

Submission status: Accepted

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


def main():
    X, Y = map(int, input().split())
    MOD = 10 ** 9 + 7
    if (X + Y) % 3 != 0:
        print(0)
        exit()
    m = (2 * X - Y) // 3
    n = (2 * Y - X) // 3

    
    N = 10**6
    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル
    
    for i in range( 2, N + 1 ):
        g1.append( ( g1[-1] * i ) % MOD )
        inverse.append( ( -inverse[MOD % i] * (MOD//i) ) % MOD )
        g2.append( (g2[-1] * inverse[-1]) % MOD )
    
    ans = cmb(n + m, n, MOD, g1, g2)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def createFacArr(n, mod):
    fac = [0] * n
    finv = [0] * n
    inv = [0] * n
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, n):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod
    return fac, finv, inv

def comb(n ,k, mod, fac, finv, inv):
    '''
    二項係数の計算
    '''
    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():
    if (X + Y) % 3 != 0:
        return 0
    # 移動回数を求める
    m = (2 * X - Y) // 3
    n = X - 2 * m
    fac, finv, inv = createFacArr(10**6*2, MOD)
    return comb(m+n, n, MOD, fac, finv, inv)

print(main())

Submission status: Accepted

Solution code:
import math

MOD = 10**9 + 7

# nCk
def comb(n, r):
    r = min(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
  
# nCk mod
def comb_mod(n, r, mod):
  r = min(r, n-r)
  
  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 )

  return g1[n] * g2[r] * g2[n-r] % mod

X, Y = map(int, input().split())
  
if (X+Y)%3!=0:
  print(0)
  quit()

# (+1,+2):n, (+2,+1):m
m = (X*2 - Y) // 3
n = X - m*2

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

ans = comb_mod(n+m, n, MOD)

print(ans)

Submission status: Accepted

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

def main():
    X, Y = map(int, input().split())
    t = X + Y
    MOD = int(1e9) + 7
    
    if t%3 != 0:
        print(0)
        return
    
    kai = [1] * (1 + (X + Y) // 3)
    for i in range(1, len(kai)):
        kai[i] = (kai[i-1] * i) % MOD

    t //= 3
    ans = 0
    for a in range(t+1):
        if (X - a) % 2 == 0 and (X - a)//2 == Y - 2*a:
            b = Y - 2*a
            ans += kai[a+b] * pow(kai[a], MOD-2, MOD) * pow(kai[b], MOD-2, MOD)
            ans %= MOD
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def sq(a, b, mod):#aのb乗を剰余,kは初期値#20191116-D-Knight
    if b==0:
        return 1
    elif b%2==0:
        return sq(a, b//2, mod)**2%mod
    else:
        return sq(a, b-1, mod)*a%mod

def nCk(n, k, mod=10 ** 9 + 7):
    x=max(k, n-k)
    y=min(k, n-k)
    kkai=1
    for i in range(2, y+1):
        kkai=(kkai*i)%mod
    nkkai=1
    for i in range(x+1, n+1):
        nkkai=(nkkai*i)%mod
    answer=sq(kkai, mod-2, mod)*nkkai%mod
    return answer
    
import math
c    = [list(map(int, input().split())) for _ in range(1)]
aa=(2*c[0][1]-c[0][0])
bb=(2*c[0][0]-c[0][1])
k=10**9+7

if aa%3!=0 or bb%3!=0:
    print(0)
elif aa<0 or bb<0:
    print(0)
else:
    a=aa//3
    b=bb//3
    answer=nCk(a+b,a)%k
    print(answer)