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:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
		
#階乗#
lim = 10**6   #必要そうな階乗の限界を入力
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1] % mod

#階乗の逆元#
fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod

X, Y = MAP()

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

if a%1 == b%1 == 0 and 0 <= a and 0 <= b:
	print(C(int(a+b), int(a)))
else:
	print(0)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
		
#階乗#
lim = 10**6   #必要そうな階乗の限界を入力
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1] % mod

#階乗の逆元#
fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod

X, Y = MAP()

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

if a%1 == b%1 == 0 and 0 <= a and 0 <= b:
	print(C(int(a+b), int(a)))
else:
	print(0)

Submission status: Accepted

Solution code:
M=10**9+7
x,y=map(int,input().split())
ans=0
if (x+y)%3==0:
  a=(2*y-x)//3
  b=(2*x-y)//3
  if a>=0 and b>=0:
    f1,f2=1,1
    for i in range(a+1,a+b+1):
      f1*=i
      f1%=M
    for i in range(1,b+1):
      f2*=i
      f2%=M
    ans=f1*pow(f2,M-2,M)

print(ans%M)

Submission status: Accepted

Solution code:
import math
mod=10**9+7
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
def div(a, b):
    return mul(a, pow(b, mod-2,mod))
x,y=map(int,input().split())
x,y=min(x,y),max(x,y)
s=y-x
if (x-s)<0 or 3*((x-s)//3)+2*s!=y:
  print(0)
else:
  a=(x-s)//3
  b=(y-2*s)//3+s
  A=1
  B=1
  C=1
  for i in range(1,a+b+1):
    A*=i
    A%=mod
  for i in range(1,a+1):
    B*=i
    B%=mod
  for i in range(1,b+1):
    C*=i
    C%=mod
  print(div(A,mul(B,C)))

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def mod_com_once(n, r, MOD):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    r = min(r, n - r)
    numer = denom = 1
    for i in range(n - r + 1, n + 1):
        numer = numer * i % MOD
    for i in range(1, r + 1):
        denom = denom * i % MOD
    return numer * pow(denom, MOD - 2, MOD) % MOD


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

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

    p, q = (-X + 2 * Y) // 3, (2 * X - Y) // 3
    if p < 0 or q < 0:
        print(0)
        return

    ans = mod_com_once(p + q, p, MOD)

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
X, Y = map(int, input().split())
      
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 = 10**9+7
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]
for i in range(2, (X+Y)//3+1):
  fac.append(fac[-1] * i % mod)
  inv.append(-inv[mod % i] * (mod // i) % mod)
  finv.append(finv[-1] * inv[-1] % mod)
  
ans = 0
x = 0
y = 0
if (X + Y) % 3 == 0:
  x = (2*Y-X) // 3
  y = (2*X-Y) // 3
  ans = cmb(x+y, x, mod)

print(ans)

Submission status: Accepted

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

m, r = divmod(2*Y-X, 3)
if r != 0:
    print(0)
    exit()

n = Y - 2*m

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

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

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

print(combination(n+m, n))

Submission status: Accepted

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


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



ans = 1
for i in range(0,x//2+2):
    j = x - 2*i
    if 2*j + i == y:
        a = i
        b = j
        break
else:
    print(0)
    exit()

for i in range(1,a+b+1):
    ans *= i%p
    ans %= p
ans %= p

a_inv = 1
for i in range(1,a+1):
    a_inv *= i%p
    a_inv %= p
a_inv = pow(a_inv,p-2,p)

b_inv = 1
for i in range(1,b+1):
    b_inv *= i%p
    b_inv %= p
b_inv = pow(b_inv,p-2,p)

ans *= (a_inv*b_inv)%p

print(ans%p)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
x, y = list(map(int, input().split(' ')))
# K馬(右上のみ) -> パスカルの三角形っぽい
mmm = 1000000000 + 7
sss = x + y
if sss % 3 != 0:
    print(0)
    exit()
hoge = sss // 3
# 上にp, 右にq
# 2p + q = y
# 2q + p = x
# p + q = hoge
# p = y - hoge
# q = x - hoge
p =  y - hoge
q = x - hoge
#print(hoge, p, q)
if p < 0 or q < 0:  # 3 0 の時で Wrong Answer
    print(0)
    exit()

# 二項係数 mod [検索]
fac = []
inv = []
inv_fac = []
def init(n):
    fac.append(1)
    fac.append(1)
    inv.append(0)
    inv.append(1)
    inv_fac.append(1)
    inv_fac.append(1)
    for i in range(2, n):
        fac.append(fac[-1] * i % mmm)
        inv.append(mmm - inv[mmm%i] * (mmm // i) % mmm)
        inv_fac.append(inv_fac[-1] * inv[-1] % mmm)

def choice(a, b):
    if a < b:
        return 0
    return fac[a] * (inv_fac[b] * inv_fac[a-b] % mmm) % mmm

init(hoge * 2 + 1)
print(choice(hoge, p) % mmm)

# nCk - TLE でした
# def choice(a, b):
#     if a == b or b == 0:
#         return 0
#     if a < b:
#         return choice(b, a)
#     bunshi = a
#     t = min(b, (a-b))
#     bunbo = t
#     for i in range(1, t):
#         bunshi *= (a-i) % mmm
#         bunbo *= (t-i) % mmm
#     return bunshi // bunbo

Submission status: Accepted

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

    facn = 1
    facr = 1
    facnr = 1
    for i in range(1, n + 1):
        facn = (facn * i) % mod
        if i == r:
            facr = facn
        if i == n - r:
            facnr = facn
    
    b = 1
    invfacr = 1
    invfacnr = 1
    while b <= mod:
        if b & (mod - 2) != 0:
            invfacr = (invfacr * facr) % mod
            invfacnr = (invfacnr * facnr) % mod
        facr = (facr * facr) % mod
        facnr = (facnr * facnr) % mod
        b *= 2

    print((facn * invfacr * invfacnr) % mod)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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())



#  a = (i+2,j+1) の回数
#  b = (i+1,j+2) の回数
ans = 0
for a in range(X//2 + 1):
    b = X - a * 2
    y = 2 * b + a
    if b >= 0 and Y == y:
        ans = cmb(a+b, a) % (10**9 + 7)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def modinv(a):
    b = MOD
    u = 1
    v = 0
    while b:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u

    u %= MOD
    if u < 0:
        u += MOD
    return u


def factorial(N):
    if N == 0 or N == 1:
        return 1
    res = N
    for i in range(N - 1, 1, -1):
        res *= i
        res %= MOD
    return res


def solve():
    X, Y = Scanner.map_int()
    if (X + Y) % 3 != 0:
        print(0)
        return
    B = (2 * Y - X) // 3
    A = (2 * X - Y) // 3
    if A < 0 or B < 0:
        print(0)
        return
    n = factorial(A + B)
    m = factorial(A)
    l = factorial(B)
    ans = n * modinv(m * l % MOD) % MOD
    print(ans)


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    x, y = map(int, readline().split())
    ans = 0
    tmp = 1

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

    def com(n, r, mod):
        r = min(r, n - r)
        if r == 0:
            return 1
        res = ilist[n] * iinvlist[n - r] * iinvlist[r] % mod
        return res

    ilist = [0]
    iinvlist = [1]
    tmp = 1


    for i in range(1, x + y + 1):
        tmp *= i
        tmp %= mod
        ilist.append(tmp)
        iinvlist.append(modinv(tmp, mod))


    for b in range(x//2+1):
        a = x - 2 * b
        if 2*a + b == y:
            ans += ilist[a+b] * iinvlist[a] * iinvlist[b] % mod
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
x, y = map(int,input().split())
p = 10 ** 9 + 7
if (x + y) % 3 != 0 or 2*x < y or 2*y < x:
    print(0)
    exit()
a = (2 * y -x) // 3
b = (2 * x -y) // 3

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:
mod=10**9+7
def fact(n):
    ans=1
    for i in range(1,n+1):
        ans*=i
        ans%=mod
    return ans

x,y=map(int,input().split())
if (x+y)%3!=0: print(0)
else:
    temp=(x+y)//3
    if x<temp or x>2*temp: print(0)
    else:
        dx=x-temp
        fc_temp=fact(temp)
        fc_dx=fact(dx)
        fc_temp_dx=fact(temp-dx)
        fc_dx=pow(fc_dx,mod-2,mod)
        fc_temp_dx=pow(fc_temp_dx,mod-2,mod)
        ans=fc_temp*fc_dx%mod*fc_temp_dx%mod
        print(ans)

Submission status: Accepted

Solution code:
# フェルマーの小定理
X, Y = map(int, input().split())

m = 1000000007
def mcomb(n, k):
    a = 1
    b = 1
    for i in range(k):
        a *= n - i
        a %= m
        b *= i + 1
        b %= m
    return a * pow(b, m - 2, m) % m
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
print(mcomb(n, a))

Submission status: Accepted

Solution code:
# フェルマーの小定理
X, Y = map(int, input().split())

m = 1000000007


def make_factorial_table(n):
    result = [0] * (n + 1)
    result[0] = 1
    for i in range(1, n + 1):
        result[i] = result[i - 1] * i % m
    return result


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], m - 2, m) * pow(fac[k], m - 2, m) % m


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 = make_factorial_table(n)
print(mcomb(n, a))

Submission status: Accepted

Solution code:
def nCr(n, r, mod):
    x, y = 1, 1
    for r_ in range(1, r+1):
        x = x*(n+1-r_)%mod
        y = y*r_%mod
    return x*pow(y, mod-2, mod)%mod

x, y = map(int, input().split())
mod = 10**9+7
if (x+y)%3 or 2*x<y or 2*y<x:
    print(0)
else:
    print(nCr((x+y)//3,(2*x-y)//3, mod))

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  
nums = 10**6 # 制約に合わせよう
g1, g2, inverse = [1, 1] , [1, 1], [0, 1]
 
for num in range(2, nums + 1):
    g1.append((g1[-1] * num) % mod)
    inverse.append((-inverse[mod % num] * (mod//num)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)
    
x, y = map(int, input().split())
if (x+y)%3 or 2*x<y or 2*y<x:
    print(0)
else:
    print(cmb((x+y)//3,(2*x-y)//3, mod))

Submission status: Accepted

Solution code:
def cmbp(n,k):
    nCk = 1
    MOD = 10**9+7

    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= MOD

    for i in range(1,k+1):
        nCk *= pow(i,MOD-2,MOD)
        nCk %= MOD
    return nCk
x,y=map(int,input().split())
if (x+y)%3==0:
  n=int((2*y-x)/3)
  m=int((2*x-y)/3)
  if n>=0 and m>=0:
    print(cmbp(m+n,n))
  else:
    print(0)
else:
  print(0)

Submission status: Accepted

Solution code:
mod=10**9+7
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()

a,b=mi()
if (a+b)%3!=0:
  print(0)
  sys.exit()
s=(a+b)//3
a-=s
b-=s
if a<0 or b<0:
  print(0)
  sys.exit()
fac=[1]*700000
for i in range(1,700000):
  fac[i]=(fac[i-1]*i)%mod
m=a+b
n=min(a,b)
c=1
for j in range(m,m-n,-1):
  c*=j
  c=c%mod
print((c*pow(fac[n],mod-2,mod))%mod)

Submission status: Accepted

Solution code:
# フェルマーの小定理
X, Y = map(int, input().split())

m = 1000000007

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) % m


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], m - 2, m) * pow(fac[k], m - 2, m) % m


print(mcomb(n, a))

Submission status: Accepted

Solution code:
def comb_mod(n,r,m):
    ans = 1
    for i in range(1,r+1):
        ans *= (n-i+1) % m
        ans *= pow(i,m-2,m) % m
        ans = ans % m
    return ans

x,y = map(int,input().split())
m = 10**9+7
if x > 2*y or 2*x < y or (x+y)%3 != 0:
    ans = 0
else:
    n = (x+y)//3
    r = x-n
    ans = comb_mod(n,r,m)
print(ans)

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
if (x+y)%3!=0:
    print(0)
    exit()
if x<y:
    x,y=y,x
if 2*y<x:
    print(0)
    exit()
mod=10**9+7
a=(2*y-x)//3
b=(2*x-y)//3
mx=10**6
k=[1]*(mx+1)
def inv(n):
    return pow(n,mod-2,mod)
for i in range(mx):
    k[i+1]=k[i]*(i+1)%mod
ans=(k[a+b]*inv(k[a])*inv(k[b]))%mod
print(ans)

Submission status: Accepted

Solution code:
# ABC145D

import sys
input=sys.stdin.readline
MOD=10**9+7

factorial=[1]*(2*10**6+1)
for i in range(1,2*10**6+1):
    factorial[i]=factorial[i-1]*i
    factorial[i]%=MOD

def modinv(x):
    return pow(x,MOD-2,MOD)
    
def comb(n,r):
    return (factorial[n]*modinv(factorial[n-r])*modinv(factorial[r]))%MOD

def main():
    X,Y=map(int,input().split())
    a=(2*Y-X)
    b=(2*X-Y)
    A=a//3
    B=b//3
    ans=0
    if a%3==0 and b%3==0 and a>=0 and b>=0:
        ans=comb(A+B,A)
    print(ans)
    
    
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
def ncr(n, r):
    num, den = 1, 1
    if n - r < r:
        r = n - r
    for i in range(1, r + 1):
        num *= n - i + 1
        num %= MOD
        den *= i
        den %= MOD
    return num * pow(den, MOD - 2, MOD) % MOD


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

if Z % 3 or Y > 2 * X or Y < X // 2:
    print(0)
else:
    print(ncr(Z // 3, X - Z // 3))

Submission status: Accepted

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

if (X + Y) % 3 or Y > 2 * X or Y < X // 2:
    print(0)
    exit()

n = (X + Y) // 3
r = X - (X + Y) // 3
num, den = 1, 1
if n - r < r:
    r = n - r
for i in range(1, r + 1):
    num *= n - i + 1
    num %= MOD
    den *= i
    den %= MOD

print((num * pow(den, MOD - 2, MOD)) % MOD)

Submission status: Accepted

Solution code:
def ncr(n, r):
    return fac[n] * facinv[r] * facinv[n - r] % MOD


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

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

if (X + Y) % 3 or Y > 2 * X or Y < X // 2:
    print(0)
    exit()
d = (X + Y) // 3
print(ncr(d, X - (X + Y) // 3))

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os

# 検索用タグ、10^9+7 組み合わせ、スプレッドシートでのトレース

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)

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

def prepare_simple(n, mod=pow(10, 9) + 7):
    # n! の計算
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= mod
    fn = 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 fn, invs


def prepare(n, mod=pow(10, 9) + 7):
    # 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


# 実装を行う関数
def resolve(test_def_name=""):
    x, y = map(int, input().split())

    all_move_count = (x + y) // 3

    x_move_count = all_move_count
    y_move_count = 0

    x_now = all_move_count * 2
    y_now = all_move_count

    canMake= False
    for i in range(all_move_count+1):
        if x_now == x and y_now == y:
            canMake = True
            break

        x_move_count -= 1
        y_move_count += 1
        x_now -= 1
        y_now += 1

    if not canMake:
        print(0)
        return


    ans = cmb(all_move_count,x_move_count)

    print(ans)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3 3"""
        output = """2"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """2 2"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """999999 999999"""
        output = """151840682"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
X,Y=map(int,input().split())
mod=10**9+7
if (X+Y)%3!=0:
  print(0)
else:
  N=int((2*Y-X)/3)
  M=int((2*X-Y)/3)
  if N<0 or M<0:
    print(0)
  if N==0 or M==0:
    print(1)
  if N>0 and M>0:
    List=[0 for i in range(N+M)]
    List[0]=1
    for i in range(N+M-1):
      List[i+1]=List[i]*(i+2)%mod
    print(List[N+M-1]*pow(List[N-1],mod-2,mod)*pow(List[M-1],mod-2,mod)%mod)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


def prepare_simple(n, mod=pow(10, 9) + 7):
    # n! の計算
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= mod
    fn = 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 fn, invs


def prepare(n, mod=pow(10, 9) + 7):
    # 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


# 実装を行う関数
def resolve(test_def_name=""):
    x, y = map(int, input().split())

    all_move_count = (x + y) // 3

    x_move_count = all_move_count
    y_move_count = 0

    x_now = all_move_count * 2
    y_now = all_move_count

    canMake= False
    for i in range(all_move_count+1):
        if x_now == x and y_now == y:
            canMake = True
            break

        x_move_count -= 1
        y_move_count += 1
        x_now -= 1
        y_now += 1

    if not canMake:
        print(0)
        return

    fns, invs = prepare(all_move_count)
    ans = (fns[all_move_count] * invs[x_move_count] * invs[all_move_count - x_move_count]) % (pow(10, 9) + 7)

    print(ans)
    # fn, invs = prepareSimple(10)
    # ans = (fn * invs[3] * invs[10 - 3]) % (pow(10, 9) + 7)
    # print(ans)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3 3"""
        output = """2"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """2 2"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """999999 999999"""
        output = """151840682"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


def prepareSimple(n, mod=pow(10, 9) + 7):
    # n! の計算
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= mod
    fn = 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 fn, invs


def prepare(n, mod=pow(10, 9) + 7):
    # 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


# 実装を行う関数
def resolve(test_def_name=""):
    x, y = map(int, input().split())

    all_move_count = (x + y) // 3

    x_move_count = all_move_count
    y_move_count = 0

    x_now = all_move_count * 2
    y_now = all_move_count

    canMake= False
    for i in range(all_move_count+1):
        if x_now == x and y_now == y:
            canMake = True
            break

        x_move_count -= 1
        y_move_count += 1
        x_now -= 1
        y_now += 1

    if not canMake:
        print(0)
        return

    fn, invs = prepareSimple(all_move_count)
    ans = (fn * invs[x_move_count] * invs[all_move_count - x_move_count]) % (pow(10, 9) + 7)

    print(ans)
    # fn, invs = prepareSimple(10)
    # ans = (fn * invs[3] * invs[10 - 3]) % (pow(10, 9) + 7)
    # print(ans)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3 3"""
        output = """2"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """2 2"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """999999 999999"""
        output = """151840682"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

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

a, b = (2 * Y - X) // 3, (2 * X - Y) // 3
if (2 * X - Y) % 3 != 0 or a*b < 0:
    print(0)
else:
    print((fac(a + b) * pow(fac(a), MOD-2, MOD) * pow(fac(b), MOD-2, MOD)) % (10**9 + 7))