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: Runtime Error

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

mod = 10**9 + 7

# import math
# def comb(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

# def comb(n,r,mod):
# 	'''
# 	return nCr
# 	O(min{n-r, r})
# 	'''
# 	a=1
# 	b=1
# 	r = min(r,n-r)
# 	for i in range(r):
# 		a = a*(n-i)%mod
# 		b = b*(i+1)%mod
# 	return a*pow(b,mod-2,mod)%mod

if (x+y)%3!=0:
    print(0)
    exit()
else:
    n = int((2/3)*x - (1/3)*y)
    m = int((2/3)*y - (1/3)*x)
    if n>=0 and m>=0:
        print(comb(n+m,m,mod))
        exit()
    else:
        print(0)
        exit()

Submission status: Runtime Error

Solution code:
p = 10**9 + 7

def pow_mod(p,a,n):
    res = 1
    while n > 0:
        if n % 2 == 1:
            res = (res * a) % p
        n = n // 2
        a = (a*a)%p
    return res


def comb_mod(n,k):
    global fac
    res = fac[n] * pow_mod(p,fac[k],p-2) * pow_mod(p,fac[n-k],p-2) % p
    return res

X,Y = map(int,input().split())
X,Y = max(X,Y),min(X,Y)
n = (X+Y)//3

fac = [1]
foo = 1
for i in range(1,n+1):
    foo = (foo*i)%p
    fac.append(foo)

k = 2*n - X
if (X+Y)%3 != 0 or n < k:
    ans = 0
else:
    ans = comb_mod(n,k)
print(ans)

Submission status: Runtime Error

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

mod = 10**9 + 7

import math
def comb(n,r):
    return (math.factorial(n)//(math.factorial(n-r)*math.factorial(r)))

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

Submission status: Runtime Error

Solution code:
import sys

# import numpy as np
import math
from fractions import gcd
from collections import deque
import bisect

sys.setrecursionlimit(1000000000000)


def factorial(n):
    w = 10**9 + 7
    table = [1]*(n+1)
    for i in range(1, n+1):
        table[i] = table[i-1]*i % w
    return table


def modinv(a, m):
    b = m
    u = 1
    v = 0

    while b > 0:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u


def moddiv(x, y, m=10**9+7):
    y_inv = modinv(y, m)
    return x * y_inv % m


def perm(N1, N2):
    table = factorial(N1+N2)
    s = table[N1+N2]
    a = table[N1]
    b = table[N2]
    return moddiv(moddiv(s, a), b)


def main():
    # map(int, input().split())
    # l = list(map(int, input().split()))

    x, y = map(int, input().split())
    diff = abs(x-y)

    if diff == 0:
        if x % 3 != 0:
            print(0)
            return
        cnt = x // 3
        ret = perm(cnt, cnt)
    else:
        if (min(x, y)-diff) % 3 != 0:
            print(0)
            return
        cnt = (min(x, y) - diff) // 3
        ret = perm(cnt, cnt+diff)

    print(ret)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

# import numpy as np
import math
from fractions import gcd
from collections import deque
import bisect

sys.setrecursionlimit(10000000000000)


def factorial(n):
    w = 10**9 + 7
    table = [1]*(n+1)
    for i in range(1, n+1):
        table[i] = table[i-1]*i % w
    return table


def modinv(a, m):
    b = m
    u = 1
    v = 0

    while b > 0:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u


def moddiv(x, y, m=10**9+7):
    y_inv = modinv(y, m)
    return x * y_inv % m


def perm(N1, N2):
    table = factorial(N1+N2)
    s = table[N1+N2]
    a = table[N1]
    b = table[N2]
    return moddiv(moddiv(s, a), b)


def main():
    # map(int, input().split())
    # l = list(map(int, input().split()))

    x, y = map(int, input().split())
    diff = abs(x-y)

    if diff == 0:
        if x % 3 != 0:
            print(0)
            return
        cnt = x // 3
        ret = perm(cnt, cnt)
    else:
        if (min(x, y)-diff) % 3 != 0:
            print(0)
            return
        cnt = (min(x, y) - diff) // 3
        ret = perm(cnt, cnt+diff)

    print(ret)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

# import numpy as np
import math
from fractions import gcd
from collections import deque
import bisect

sys.setrecursionlimit(10**12)


def factorial(n):
    w = 10**9 + 7
    table = [1]*(n+1)
    for i in range(1, n+1):
        table[i] = table[i-1]*i % w
    return table


def modinv(a, m):
    b = m
    u = 1
    v = 0

    while b > 0:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u


def moddiv(x, y, m=10**9+7):
    y_inv = modinv(y, m)
    return x * y_inv % m


def perm(N1, N2):
    table = factorial(N1+N2)
    s = table[N1+N2]
    a = table[N1]
    b = table[N2]
    return moddiv(moddiv(s, a), b)


def main():
    # map(int, input().split())
    # l = list(map(int, input().split()))

    x, y = map(int, input().split())
    diff = abs(x-y)

    if diff == 0:
        if x % 3 != 0:
            print(0)
            return
        cnt = x // 3
        ret = perm(cnt, cnt)
    else:
        if (min(x, y)-diff) % 3 != 0:
            print(0)
            return
        cnt = (min(x, y) - diff) // 3
        ret = perm(cnt, cnt+diff)

    print(ret)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

# import numpy as np
import math
from fractions import gcd
from collections import deque
import bisect

sys.setrecursionlimit(1000000)


def factorial(n):
    w = 10**9 + 7
    table = [1]*(n+1)
    for i in range(1, n+1):
        table[i] = table[i-1]*i % w
    return table


def modinv(a, m):
    b = m
    u = 1
    v = 0

    while b > 0:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u


def moddiv(x, y, m=10**9+7):
    y_inv = modinv(y, m)
    return x * y_inv % m


def perm(N1, N2):
    table = factorial(N1+N2)
    s = table[N1+N2]
    a = table[N1]
    b = table[N2]
    return moddiv(moddiv(s, a), b)


def main():
    # map(int, input().split())
    # l = list(map(int, input().split()))

    x, y = map(int, input().split())
    diff = abs(x-y)

    if diff == 0:
        if x % 3 != 0:
            print(0)
            return
        cnt = x // 3
        ret = perm(cnt, cnt)
    else:
        if (min(x, y)-diff) % 3 != 0:
            print(0)
            return
        cnt = (min(x, y) - diff) // 3
        ret = perm(cnt, cnt+diff)

    print(ret)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

# import numpy as np
import math
from fractions import gcd
from collections import deque
import bisect

sys.setrecursionlimit(10000)


def factorial(n):
    w = 10**9 + 7
    table = [1]*(n+1)
    for i in range(1, n+1):
        table[i] = table[i-1]*i % w
    return table


def modinv(a, m):
    b = m
    u = 1
    v = 0

    while b > 0:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u


def moddiv(x, y, m=10**9+7):
    y_inv = modinv(y, m)
    return x * y_inv % m


def perm(N1, N2):
    table = factorial(N1+N2)
    s = table[N1+N2]
    a = table[N1]
    b = table[N2]
    return moddiv(moddiv(s, a), b)


def main():
    # map(int, input().split())
    # l = list(map(int, input().split()))

    x, y = map(int, input().split())
    diff = abs(x-y)

    if diff == 0:
        if x % 3 != 0:
            print(0)
            return
        cnt = x // 3
        ret = perm(cnt, cnt)
    else:
        if (min(x, y)-diff) % 3 != 0:
            print(0)
            return
        cnt = (min(x, y) - diff) // 3
        ret = perm(cnt, cnt+diff)

    print(ret)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

# import numpy as np
import math
from fractions import gcd
from collections import deque
import bisect

sys.setrecursionlimit(10000)


def factorial(n):
    w = 10**9 + 7
    table = [1]*(n+1)
    for i in range(1, n+1):
        table[i] = table[i-1]*i % w
    return table


def modinv(a, m):
    b = m
    u = 1
    v = 0

    while b > 0:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u


def moddiv(x, y, m=10**9+7):
    y_inv = modinv(y, m)
    return x * y_inv % m


def perm(N1, N2):
    table = factorial(N1+N2)
    s = table[N1+N2]
    a = table[N1]
    b = table[N2]
    return moddiv(moddiv(s, a), b)


def main():
    # map(int, input().split())
    # l = list(map(int, input().split()))

    x, y = map(int, input().split())
    diff = abs(x-y)

    if diff == 0:
        if x % 3 != 0:
            return
        cnt = x // 3
        ret = perm(cnt, cnt)
    else:
        if (min(x, y)-diff) % 3 != 0:
            return
        cnt = (min(x, y) - diff) // 3
        ret = perm(cnt, cnt+diff)

    print(ret)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def cnb(n,k,p):
  if k>n:
    return 0
  c,d=1,1
  for i in range(k+1,n+1):
    c = (c*i)%p
  for i in range(1,k+1):
    d = (d*i)%p
  return (c*pow(d,p-2,p))%p

p=10**9+7
if X > 2*Y or Y > 2*X:
  pass
elif (X+Y)%3:
  pass
else:
  ans=cnb((X+Y)//3,(-X+2*Y)//3,p)

print(ans)

Submission status: Runtime Error

Solution code:
[x,y]=list(map(int,input().split()))
if ((x%3)+(y%3))%3!=0:
	print(0)
else:
	n=int((x+y)/3)
	r=y-n
	if r<0 or r>n:
		print(0)
	else:
		if r>n-r:
			r=n-r
		mod=1000000007
		kaijo=[1]
		for i in range(1,n+1):
			kaijo.append(kaijo[-1]*i%mod) #これで、kaijo[i]=i!となる。
		gyakugen=[pow(kaijo[n-r],mod-2,mod)]
		for i in reversed(range(1,n-r)):
			gyakugen.append(gyakugen[-1]*i) #これで、gyakugen[i]=n-r-iの逆元となる
		kotae=kaijo[n]*gyakugen[0]*gyakugen[n-2*r]%mod

		print(kotae)

Submission status: Runtime Error

Solution code:
a,b = map(int, input().split())
tried = (a + b)//3
p = 10**9 +7

if a < tried or b < tried or (a+b)%3 != 0:
    print(0)
    quit()
one = (2/3)* a - (1/3)* b
n = tried
r = min(one, tried-one)
n_fac = 1
r_fac = 1
n_r_fac = 1

for i in range(2,n+1):
    n_fac *= i
    n_fac %= p
for i in range(2,r+1):
    r_fac *= i
    r_fac %= p
for i in range(2,n-r+1):
    n_r_fac *= i
    n_r_fac %= p
r_fac_inverse = pow(r_fac, p-2, p)
n_r_fac_inverse = pow(n_r_fac, p-2, p)

print((n_fac * r_fac_inverse * n_r_fac_inverse)%p)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

# -*- coding: utf-8 -*-


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret

    def perm(self, n, r):
        """
        nPrの値を返す
        """
        ret = self.f[n] * self.inv[n-r]
        ret %= self.mod
        return ret


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

x = (2*Y-X)/3
y = (2*X-Y)/3

if 0 <= x and x == int(x) and 0 <= y and y == int(y):
    F = FactMod(x+y+1, 10**9+7)
    ans = F.comb(x+y, x)
else:
    ans = 0
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

# -*- coding: utf-8 -*-


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret

    def perm(self, n, r):
        """
        nPrの値を返す
        """
        ret = self.f[n] * self.inv[n-r]
        ret %= self.mod
        return ret


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

x = (2*Y-X)/3
y = (2*X-Y)/3
F = FactMod(x+y+1, 10**9+7)

if 0 <= x and x == int(x) and 0 <= y and y == int(y):
    ans = F.comb(x+y, x)
else:
    ans = 0
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

# -*- coding: utf-8 -*-


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret

    def perm(self, n, r):
        """
        nPrの値を返す
        """
        ret = self.f[n] * self.inv[n-r]
        ret %= self.mod
        return ret


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

y = (2*Y-X)/3
x = (2*X-Y)/3
F = FactMod(x+y, 10**9+7)

if 0 <= x and x == int(x) and 0 <= y and y == int(y):
    ans = F.comb(x+y, x)
else:
    ans = 0
print(ans)

Submission status: Runtime Error

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

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

def calc(x, y):
  if  (x + y) % 3 != 0:
    return 0
  n = (2*y - x ) / 3
  m = (2*x - y) /3
  return permutations_count(n+m, n) % (pow(10,9) + 7)

print(calc(x, y))

Submission status: Runtime Error

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

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

def calc(x, y):
  if  (x + y) % 3 != 0:
    return 0
  n = (2*y - x ) / 3
  m = (2*x - y) /3
  return permutations_count(n+m, n)

print(calc(x, y))

Submission status: Runtime Error

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

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

def calc(x, y):
  if  x + y % 3 != 0:
    return 0
  n + 2m = x
  2n + m = y
  n = (2*y - x ) / 3
  m = (2*x - y) /3
  return permutations_count(n+m, n)

print(calc(x, y))

Submission status: Runtime Error

Solution code:
import math

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

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

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

num = 1

for x in range(m + n, n, -1):
    num *= x

den = 1
for x in range(1, m + 1):
    den *= x

print(int(num / den) % MOD)

Submission status: Runtime Error

Solution code:
def modpow(a, b, mod=1):
    ret = 1
    while b > 0:
        if b % 2 == 1:
            ret = ret * a % mod
        a, b = a * a % mod, b // 2
    return ret


MOD = 10 ** 9 + 7
X, Y = map(int, input().split())
A, B = (2 * X - Y) // 3, (2 * Y - X) // 3
if (X + Y) % 3 != 0 or A < 0 or B < 0:
    print(0)
else:
    ans = 1
    for n in range(A + B, A, -1):
        ans = ans * n % MOD
    for n in range(1, B + 1):
        ans = ans * modpow(n, MOD - 2, MOD) % MOD

print(ans)

Submission status: Runtime Error

Solution code:
# D - Knight

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

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

import math

if a%1 != 0 or b%1 != 0:
    print(0)
else:
    a = int(a)
    b = int(b)
    # 最短経路の数 nCr
    ans = (math.factorial(a + b) // (math.factorial(a) * math.factorial(b))) % (10**9 + 7)

    print(ans)

Submission status: Runtime Error

Solution code:
package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

const (
    M = 1000000007
)

var (
    fac  []int
    ifac []int
)

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

func mpow(x int, n int) int {
    ans := 1
    for n != 0 {
        if n&1 == 1 {
            ans = ans * x % M
        }
        x = x * x % M
        n = n >> 1
    }
    return ans
}

func comb(a int, b int) int {
    if a == 0 && b == 0 {
        return 1
    }
    if a < b || a < 0 {
        return 0
    }
    tmp := ifac[a-b] * ifac[b] % M
    return tmp * fac[a] % M
}

func main() {
    X := readInt()
    Y := readInt()

    if (X+Y)%3 != 0 {
        fmt.Println(0)
        return
    }

    fac = make([]int, 666667)
    ifac = make([]int, 666667)

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

    if a < 0 || b < 0 {
        fmt.Println(0)
        return
    }

    fac[0] = 1
    ifac[0] = 1
    for i := 0; i < 666666; i++ {
        fac[i+1] = fac[i] * (i + 1) % M
        ifac[i+1] = ifac[i] * mpow(i+1, M-2) % M
    }

    fmt.Println(comb(a+b, min(a, b)) % M)
}

const (
    ioBufferSize = 1 * 1024 * 1024 // 1 MB
)

var stdinScanner = func() *bufio.Scanner {
    result := bufio.NewScanner(os.Stdin)
    result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
    result.Split(bufio.ScanWords)
    return result
}()

func readString() string {
    stdinScanner.Scan()
    return stdinScanner.Text()
}

func readInt() int {
    result, err := strconv.Atoi(readString())
    if err != nil {
        panic(err)
    }
    return result
}

Submission status: Runtime Error

Solution code:
import itertools
X, Y=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
MOD = 10**9 + 7
from math import factorial
# a = factorial(n+m) / factorial(n) / factorial(m)

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

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

    # print(f"n:{n}, m:{m}")

    if n<0 or m<0:
        print(0)
    else:
        # ret = 1
        # for i in range(m):
        #     ret = ret * ((X+Y)//3 - i) % MOD * pow(i + 1, MOD-2, MOD) % MOD
        a = factorial(n+m) / factorial(n) / factorial(m)
        print(a%MOD)

Submission status: Runtime Error

Solution code:
import itertools
X, Y=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
MOD = 10**9 + 7
if (X+Y)%3 != 0:
    print(0)
else:

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

    # print(f"n:{n}, m:{m}")

    if n<0 or m<0:
        print(0)
    else:
        for i in range(m):
            ret = ret * (n - i) % MOD * pow(i + 1, MOD-2, MOD) % MOD
        print(ret)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
x, y = map(int, input().split())

# 10 ** 9 + 7 is prime?

ans = 0
cnt = int((x + y) / 3)

if (x + y) % 3 != 0:
    ans = 0
elif x < cnt or x > 2 * cnt:
    ans = 0
else:
    m = int((2 * y - x) / 3) 
    n = cnt - m
   modulo = (10 ** 9) + 7
    fact = 1
    for i in range(1, n+1):
        fact = (fact * (m + i) / i) % modulo
    ans = int(fact)

print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
x, y = map(int, input().split())

ans = 0
cnt = int((x + y) / 3)

def fact(n):
    ret = 1
    if n <= 1:
        ret = 1
    else:
        ret = n * fact(n-1)
    return ret

if (x + y) % 3 != 0:
    ans = 0
elif x < cnt or x > 2 * cnt:
        ans = 0
else:
    m = int((2 * y - x) / 3) 
    ans = int(fact(cnt) / (fact(m) * fact(cnt  - m)))

print(ans)

Submission status: Runtime Error

Solution code:
X,Y=map(int,input().spilt())
mult1=1
mult2=1
if (2*Y-X)%3 ==0:
    x=(2*Y-X)//3
    y=(2*X-Y)//3
    for i in range(min(x,y)):
        mult1*=(x+y-i)
        mult2*=min(x,y)-i
    print((mult2//mult1)%(10**9+7))
else:
    print(0)

Submission status: Runtime Error

Solution code:
# import numpy as np
#N=int(input().strip())
#x=[0]*N
#y=[0]*N
#
#for i in range(N):
#    x[i],y[i]=list(map(int,input().strip().split()))

import sys

def power_l(x,power): # for mod
    if power==0:
        return 1
    elif power<0:
        print('error')
        sys.exit(1)
    res = 1
    sq = x%mod
    while(power>0):
        if power&1 > 0:
            res*=sq
            res=res%mod
        sq = sq**2 %mod
        power = power >> 1
    return res%mod

def inv(x): # x^(-1)=x^(p-2) mod
    ans = power_l(x,mod-2)
    return ans
##########################
mod = 10**9+7

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

if (X+Y)%3 !=0:
    print(0)
    sys.exit()
m = (2*X-Y)//3
n = X-2*m

# compute m+nCm=(m+n)!/(m!n!)
# make factorial
f=[1]
for i in range(m+n-1):
    f.append((f[i]*(i+2))%mod)

denom = (f[m-1]*f[n-1])%mod

ans=(f[m+n-1] * inv(denom)) %mod
print(ans)

Submission status: Runtime Error

Solution code:
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

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

Submission status: Runtime Error

Solution code:
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

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

Submission status: Runtime Error

Solution code:
[x,y]=list(map(int,input().split()))
if ((x%3)+(y%3))%3!=0:
	print(0)
else:
	n=int((x+y)/3)
	r=y-n
	if r<0 or r>n:
		print(0)
	else:
		if r>n-r:
			r=n-r
		mod=1000000007
		kaijo=[1]
		for i in range(1,n+1):
			kaijo.append(kaijo[-1]*i%mod) #これで、kaijo[i]=i!となる。
		gyakugen=[pow(kaijo[n-r],mod-2,mod)]
		for i in reversed(range(1,n-r)):
			gyakugen.append(gyakugen[-1]*i%mod) #これで、gyakugen[i]=n-r-iの逆元となる
		kotae=kaijo[n]*gyakugen[0]*gyakugen[n-2*r]%mod

		print(kotae)

Submission status: Runtime Error

Solution code:
[x,y]=list(map(int,input().split()))
if ((x%3)+(y%3))%3!=0:
	print(0)
else:
	n=int((x+y)/3)
	r=y-n
	if r<0 or r>n:
		print(0)
	else:
		if r>n-r:
			r=n-r
		mod=1000000007
		kaijo=[1]
		for i in range(1,n+1):
			kaijo.append(kaijo[-1]*i) #これで、kaijo[i]=i!となる。
		gyakugen=[pow(kaijo[n-r],mod-2,mod)]
		for i in reversed(range(1,n-r)):
			gyakugen.append(gyakugen[-1]*i%mod) #これで、gyakugen[i]=n-r-iの逆元となる
		kotae=kaijo[n]*gyakugen[0]*gyakugen[n-2*r]%mod

		print(kotae)

Submission status: Runtime Error

Solution code:
[x,y]=list(map(int,input().split()))
if ((x%3)+(y%3))%3!=0:
	print(0)
else:
	n=int((x+y)/3)
	r=y-n
	if r<0 or r>n:
		print(0)
	else:
		if r>n-r:
			r=n-r
		mod=1000000007
		kaijo=[1]
		for i in range(1,n+1):
			kaijo.append(kaijo[-1]*i) #これで、kaijo[i]=i!となる。
		gyakugen=[pow(kaijo[n-r],mod-2,mod)]
		for i in reversed(range(1,n-r)):
			gyakugen.append(gyakugen[-1]*i%mod) #これで、gyakugen[i]=n-r-iの逆元となる
		kotae=kaijo[n]*gyakugen[0]*gyakugen[n-2*r]

		print(kotae)

Submission status: Runtime Error

Solution code:
X, Y = map(int, input().split())
import math
a = 2*Y -X
b = 2*X -Y
if a % 3 == 0 and b % 3 == 0:
  k = a // 3
  l = b // 3
  ue = math.factorial(k+l)
  sita_1 = math.factorial(k)
  sita_2 = math.factorial(l)
  total = ue // (sita_1 * sita_2)
  print(total % (7 + 10 ** 9))
else:
  print(0)

Submission status: Runtime Error

Solution code:
X, Y = map(int, input().split())
import math
if (2 * Y - X ) % 3 == 0 and (2 * X -  Y) % 3 == 0:
  k = (2 * Y - X) // 3
  l = (2 * X - Y) // 3
  ue = math.factorial(k+l)
  sita_1 = math.factorial(k)
  sita_2 = math.factorial(l)
  total = ue //(sita_1 * sita_2)
  print(total % (7 + 10 ** 9))
else:
  print(0)

Submission status: Runtime Error

Solution code:
#coding: utf-8
import math
import heapq

MOD = 10**9+7

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


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

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

Submission status: Runtime Error

Solution code:
import math
a,b=map(int,input().split())
if (a+b)%3!=0:
  print(0)
else:
  n=(a+b)//3
  r=(2*b-a)//3
  def nCr(n,r):
    mod=10**9+7
    def exgcd(a,b):
      u0,u1,v0,v1=1,0,0,1
      while b!=0:
        q,a,b=a//b,b,a%b
        u0,u1=u1,u0-q*u1
        v0,v1=v1,v0-q*v1
      return u0
    def inv_mod(a,n):
      return exgcd(a,n)%n
    ans=((math.factorial(n))*(inv_mod(math.factorial(n-r),mod))*(inv_mod(math.factorial(r),mod)))%mod
    return ans
  print(nCr(n,r))

Submission status: Runtime Error

Solution code:
import math
import numpy as np

def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=calc(np.math.factorial(n)) %p
  b=calc(np.math.factorial(k)) %p
  c=calc(np.math.factorial(n-k)) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
 
x, y = map(int, input().split())

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

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

    

    ans = comb(a+b, b, 1000000007)

    # answer = (a+b)! / a!b! mod 10^9+7

    
print(ans)

# 999999 999999

Submission status: Runtime Error

Solution code:
import math
import numpy as np

def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=np.math.factorial(n) %p
  b=np.math.factorial(k) %p
  c=np.math.factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
 
x, y = map(int, input().split())

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

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

    

    ans = comb(a+b, b, 1000000007)

    # answer = (a+b)! / a!b! mod 10^9+7

    
print(ans)

# 999999 999999

Submission status: Runtime Error

Solution code:
x,y=int(input()),int(input())
xans=x//2
ans,m,j,k=0,1,1,1
for i in range(xans):
  if y==(xans-i)*2+i:
    m=1 
    for l in range(1,i+1):
      m*=l
    k=1
    for l in range(1,xans-i+1):
      k*=l
    j=1
    for l in range(1,xans+1):
      j*=l
  ans+=j/m/k
if y==2*x:
  ans+=1
ans=ans//1
print(int(ans%1000000007))

Submission status: Runtime Error

Solution code:
x,y=int(input()),int(input())
xans=x//2
ans,m,j,k=0,1,1,1
for i in range(xans):
  if y==(xans-i)*2+i:
    m=1 
    for l in range(1,i+1):
      m*=l
    k=1
    for l in range(1,xans-i+1):
      k*=l
    j=1
    for l in range(1,xans+1):
      j*=l
  ans+=j/m/k
if y==2*x:
  ans+=1
ans=ans//1
print(int(ans%1000007))

Submission status: Runtime Error

Solution code:
x,y=int(input()),int(input())
xans=x//2
ans,m,k,j=0,1,1,1
for i in range(xans):
  if y==(xans-i)*2+i:
    m=1 
    for l in range(1,i+1):
      m*=l
    k=1
    for l in range(1,xans-i+1):
      k*=l
    j=1
    for l in range(1,xans+1):
      j*=l
  ans+=j/m/k
if y==2*x:
  ans+=1
ans=ans//1
print(ans%1000007)

Submission status: Runtime Error

Solution code:
def factorials(n,m):
    # 0~n!のリスト
    f = [1,1]
    for i in range(2,n+1):
        f.append(f[-1]*i%m)

    # 0~n!の逆元のリスト
    g = [1]
    for i in range(n):
        g.append(pow(f[i+1],m-2,m))

    return f,g

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

m = 10**9+7

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

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

f,g = factorials(a+b,m)

nCr = f[a+b]*g[b]*g[a]

print(nCr%m)

Submission status: Runtime Error

Solution code:
x,y=int(input()),int(input())
xans=x//2
ans=0 
for i in range(xans):
  if y==(xans-i)*2+i:
    m=1 
    for l in range(1,i+1):
      m*=l
    k=1
    for l in range(1,xans-i+1):
      k*=l
    j=1
    for l in range(1,xans+1):
      j*=l
  ans+=j/m/k
if y==2*x:
  ans+=1
ans=ans//1
print(ans%1000007)

Submission status: Runtime Error

Solution code:
x,y=int(input()),int(input())
xans=x//2
ans=0 
for i in range(xans):
  if y==(xans-i)*2+i:
    m=1 
    for l in range(1,i+1):
      m*=l
    k=1
    for l in range(1,xans-i+1):
      k*=l
    j=1
    for l in range(1,xans+1):
      j*=l
  ans+=j/m/k
if y==2*x:
  ans+=1
print(ans%1000007)

Submission status: Runtime Error

Solution code:
from sys import stdin
import math
import bisect
import heapq
import numpy as np
from math import factorial

x,y = [int(x) for x in stdin.readline().rstrip().split()]

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

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

def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

print(combinations_count(a+b,a)%(10**9+7))

Submission status: Runtime Error

Solution code:
import math
import sys

def permtest(n, k = 1):
    p = math.factorial(n) / math.factorial(n - k)
    return int(p)

ans_num = 10**9+7
x,y = map(int,input().split())
if x > y:
    tmp = x
    x = y
    y = tmp

over = y-x

if x-over < 0 or (x-over) % 3 != 0:
    print(0)
    sys.exit()

left = int(over+(x-over)*2/3)
right = int(over+(x-over)/3)
print(permtest(left,right) % ans_num)

Submission status: Runtime Error

Solution code:
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

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

MOD = 10**9+7
x, y = map(int, input().split())
if (x+y)%3 != 0 or 3*x < x+y or 3*y < x+y:
    print(0)
    exit()
n = (x+y)//3
x -= n
y -= n
fact = [0, 1]
for i in range(2,n+1):
    fact.append(fact[i-1] * i % MOD)
factX = fact[x]
factY = fact[y]
factN = fact[n]

c = factN * modinv(factX, MOD) * modinv(factY, MOD)
c %= MOD
print(c)