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: Wrong Answer

Solution code:

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

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

level = (X+Y)//3
ind = Y - level + 1

if ind <= 0:
    print(0)
    exit()

def comb(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


a = int(comb(level, ind-1))

print(a % (10^9+7))

Submission status: Wrong Answer

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

total = 0
n = min(x // 1, y // 2)
for i in range(n):
  a = (x - 1 * i) // 2
  b = (y - 2 * i) // 1
  if a == b:
    total += len(list(itertools.combinations(range(i + 1 + a), a))) % (10 ** 9 + 7)
print(total)

Submission status: Wrong Answer

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

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 )

Z=X+Y
if Z%3 == 0:
    D=int(Z/3)
    print(cmb(D,abs(D-X),MOD))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import math
x, y = map(int, input().split())
if x * 2 < y or y * 2 < x:
    print("0")
elif (x + y) % 3 != 0:
    print("0")
else:
    x1 = x - (x + y)/3
    y1 = y - (x + y)/3
    l = int(max(x1, y1))
    s = int(min(x1, y1))
    root = 1
    for i in range(l + s - l + 1, l +s + 1):
        root *= i
    for j in range(s):
        root = root/(j+1)
    answer = int(root) % (10 ** 9 + 7)
    print(int(root))

Submission status: Wrong Answer

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

MOD = 10 ** 9 + 7


def no():
  print(0)
  exit(0)


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

if not 1 / 2 <= x / y <= 2:
  no()

if x % 3 == 1:
  x += 2
  y += 1

if x % 3 == 2:
  x += 1
  y += 2


n = x // 3 + y // 3
r = x // 3
# c = 1
# for i in range(n, n - r, -1):
#   c *= i
#   c %= MOD
# for i in range(1, r + 1):
#   c //= i
# c %= MOD
# import math
# print(math.factorial(n)//math.factorial(n-r)//math.factorial(r)%MOD)


# def c(n, r):
#   if r == 1:
#     return n
#   if c == 1:
#     return 1
#   return (c(n - 1, r) + c(n - 1, r - 1)) % MOD
#print(c(n, r))

# https://fishi.devtail.io/weblog/2015/06/25/computing-large-binomial-coefficients-modulo-prime-non-prime/

"""
Using Fermat's little theorem to calculate nCk mod m, m is prime
Computation O(n)
"""

# modular exponentiation: b^e % mod 
# python's built-in pow(b,e,mod) would be faster than this function, 
# but I am still keeping it here for completion
def mod_exp(b,e,mod):
    r = 1
    while e > 0:
        if (e&1) == 1:
            r = (r*b)%mod
        b = (b*b)%mod
        e >>= 1

    return r

# get degree of p in n! (exponent of p in the factorization of n!)
def fact_exp(n,p):
    e = 0
    u = p
    t = n
    while u <= t:
        e += t//u
        u *= p

    return e

# Using Fermat's little theorem to compute nCk mod p
# considering cancelation of p in numerator and denominator
# Note: p must be prime
def fermat_binom_advanced(n,k,p):
    # check if degrees work out
    num_degree = fact_exp(n,p) - fact_exp(n-k,p)
    den_degree = fact_exp(k,p)
    if num_degree > den_degree:
        return 0

    if k > n:
        return 0

    # calculate numerator and cancel out occurrences of p
    num = 1
    for i in range(n,n-k,-1):
        cur = i
        while cur%p == 0:
            cur //= p
        num = (num*cur)%p

    # calculate denominator and cancel out occurrences of p
    denom = 1
    for i in range(1,k+1):
        cur = i
        while cur%p == 0:
            cur //= p
        denom = (denom*cur)%p

    # numerator * denominator^(p-2) (mod p)
    return (num * mod_exp(denom,p-2,p))%p

if __name__ == '__main__':
    # mod = 1000000007 # prime

    # (950 choose 100) mod 1000000007
    print(fermat_binom_advanced(n,r,MOD)) # should be 640644226

Submission status: Wrong Answer

Solution code:
import sys
mod = 10**9+7
X, Y = map(int, input().split())
if (X+Y) % 3 != 0:
	print(0)
	sys.exit()

tot = (X+Y) // 3

y = abs(tot-X)
x = tot - y

if x == 0 or y == 0:
	print(1)
	sys.exit()

ans = 1
for i in range(y+1, tot+1):
	ans *= i
	ans %= mod

for i in range(1,x+1):
	ans *= pow(i, mod-2, mod)
	ans %= mod

print(ans%mod)

Submission status: Wrong Answer

Solution code:
p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x%p
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
A = [1 for _ in range(10**6+1)]
for i in range(1,10**6+1):
    A[i] = (A[i-1]*i)%p
B = [1 for _ in range(10**6+1)]
B[10**6] = pow(A[10**6],p-2)
for i in range(10**6-1,1,-1):
    B[i] = (B[i+1]*(i+1))%p

X,Y = map(int,input().split())
if (X+Y)%3!=0:
    cnt = 0
else:
    k = (X+Y)//3
    if X>Y:
        X,Y = Y,X
    n = X-k
    cnt = (A[k]*B[n]*B[k-n])%p
print(cnt)

Submission status: Wrong Answer

Solution code:
def is_integer(n):
    try:
        float(n)
    except ValueError:
        return False
    else:
        return float(n).is_integer()

X,Y = map(int,input().split())
a = (2*Y-X)/3
b = (2*X-Y)/3
if (X == 0 or Y == 0):
    print(0)
    exit()
if is_integer(a):
    a = int(a)
else:
    print(0)
    exit()
if is_integer(b):
    b = int(b)
else:
    print(0)
    exit()
n = a+b

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

mod = 10**9+7 
ans = cmb(n,a) % mod
print(ans)

Submission status: Wrong Answer

Solution code:
import math

def main():

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

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

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

    mod = pow(10, 9) + 7
    p1 = 1
    for i in range(1, n+m+1):
        p1 *= i
        p1 %= mod

    p2 = 1
    for i in range(1, n+1):
        p2 *= i
        p2 %= mod

    p3 = 1
    for i in range(1, m+1):
        p3 *= i
        p3 %= mod

    p2 = powfast(p2, mod-2, mod)
    p3 = powfast(p3, mod-2, mod)
    return ((p1 * p2) % mod) * p3 % mod


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


if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:

n, m = map(int,input().split())


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

N = 10**6
mod = 10**9+7
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 (n+m) % 3 != 0:
    print(0)
elif m/n >= 2 or n/m >= 2:
    print(0)
else:
    t = int((n+m)/3)+1
    k = int(min(n-t+1,m-t+1))+1
    print(cmb(t-1,k-1,10**9+7))

Submission status: Wrong Answer

Solution code:
import random
MOD = 10 ** 9 + 7
fac = [1] * (10 ** 6 * 2 + 2)
for i in range(len(fac) - 1):
    fac[i + 1] = fac[i] * (i + 1) % MOD
x, y = map(int, input().split())
t = min(x, y) // 3
if (2 * x - y) % 3 or (2 * y - x) % 3:
    print(0)
    exit(0)
a, b = (2 * x - y) // 3, (2 * y - x) // 3
k = min(a, b)
n = a + b
print((fac[n] * pow(fac[n - k], MOD - 2, MOD)
       * pow(fac[k], MOD - 2, MOD)) % MOD)

Submission status: Wrong Answer

Solution code:
import random
MOD = 10 ** 9 + 7
fac = [1] * (10 ** 6 * 2 + 2)
for i in range(len(fac) - 1):
    fac[i + 1] = fac[i] * (i + 1) % MOD
x, y = map(int, input().split())
t = min(x, y) // 3
if (2 * x - y) % 3 or (2 * y - x) % 3:
    print(0)
a, b = (2 * x - y) // 3, (2 * y - x) // 3
k = min(a, b)
n = a + b
print((fac[n] * pow(fac[n - k], MOD - 2, MOD)
       * pow(fac[k], MOD - 2, MOD)) % MOD)

Submission status: Wrong Answer

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

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]
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 = na()
a = (-1/3) * x + (2/3) * y
b = (2/3) * x - (1/3) * y
if a.is_integer() and b.is_integer():
    print(cmb(int(a+b),int(a), mod))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys
x,y = input().split(' ')
x = int(x)
y = int(y)

diff = abs(x-y)
same = max(x,y) - diff * 2

if (same%3 != 0) or diff < 0 or same< 0:
    print(0)
    sys.exit(0);



same = same//3;
print(same, diff)
mm = 1000000007
def c(n,m):
    tmp1 = 1;
    tmp2 = 1;
    for i in range(1,m+1):
        tmp1 *= (n -i +1)
        tmp2 *= i
    return ((tmp1 // tmp2) % mm)


print( c(same*2+diff, same))

Submission status: Wrong Answer

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

total = 0
n = min(x // 1, y // 2)
for i in range(n):
  a = (x - 1 * n) // 2
  b = (y - 2 * n) // 1
  if a == b:
    total += len(list(itertools.combinations(range(i + 1 + a), a))) % (10 ** 9 + 7)
print(total)

Submission status: Wrong Answer

Solution code:
import numpy as np
v=np.array(list(map(int, input().split())) )
mod = 10**9 +7
import math
def cmb(n, r,mod):
    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 = (result*int(numerator[k]))%mod

    return result
  
A = np.array([[2,1],[1,2]])
inv_A = np.linalg.inv(A)

k = np.dot(inv_A,v)
if abs(round(k[0]+ k[1])-(k[0]+k[1]))<10**(-4):
  print(cmb(int(k[0]+k[1]),int(k[0]),mod))
else:
  print(0)

Submission status: Wrong Answer

Solution code:
import sys


def alg_combination_mod(n, r, mod):
    r = min(n - r, r)
    if r == 0:
        return 1
    else:
        denominator = 1
        for i in range(n, n - r, -1):
            denominator = (denominator * i) % mod
        molecule = 1
        for i in range(1, r + 1):
            molecule = (molecule * i) % mod
        return denominator * pow(molecule, mod - 2, mod) % mod


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    x, y = list(map(int, readline().split()))
    if x / y == 2 or y / x == 2:
        print(1)
    else:
        cnt = min(x // 3, y // 3)
        x -= cnt * 3
        y -= cnt * 3
        xcnt = 0
        ycnt = 0
        if x == 0 and y == 0:
            xcnt = cnt
            ycnt = cnt
        elif x != 0 and y / x == 2:
            xcnt = cnt
            ycnt = cnt + x
        elif y != 0 and x / y == 2:
            xcnt = cnt + y
            ycnt = cnt
        else:
            print(0)
            exit()
        print(xcnt, ycnt, xcnt * 2 + ycnt, xcnt + ycnt * 2)
        print(alg_combination_mod(xcnt + ycnt, xcnt, mod))


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import numpy as np
v=np.array(list(map(int, input().split())) )
mod = 10**9 +7
import math
def cmb(n, r,mod):
    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 = (result*int(numerator[k]))%mod

    return result
  
A = np.array([[2,1],[1,2]])
inv_A = np.linalg.inv(A)

k = np.dot(inv_A,v)
if abs(round(k[0]+ k[1])-(k[0]+k[1]))<10**(-6):
  print(cmb(int(k[0]+k[1]),int(k[0]),mod))
else:
  print(0)

Submission status: Wrong Answer

Solution code:
#!python3.4.3

X, Y = map(int, input().split(' '))
count = 0
for i in range(1, X+1):
    for j in range(1, Y+1):
        x = 1*i + 2*j 
        y = 2*i + 1*j
        if x==X and y==Y:
            count+=1            
print(count*2)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce
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=[int(x) for x in input().split()]
a = X%3
b = Y%3
mod = 10**9+7 #出力の制限
N = 10**4
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 a==b==0:
  if X==Y:
    c = X//3
    #print(c)
    N = c*2
    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(c*2,c,mod))
  else:
    if X>Y:
      l = X-Y
      d = (Y-l)//3
      N = l+d*2
      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(l+d*2,d,mod))
    else:
      l = Y-X
      d = (X-l)//3
      N = l+d*2
      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(l+d*2,d,mod))
elif a==2 and b==1:
  x =X-2
  y =Y-1
  if x==y:
    c = x//3
    N = c*2+1
    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(c*2+1,c,mod))
  else:
    if x>y:
      l = x-y
      d = (y-l)//3
      N = l+d*2+1
      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(l+d*2+1,d+1,mod))
    else:
      l = y-x
      d = (x-l)//3
      N = l+d*2+1
      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(l+d*2+1,d+1,mod))
elif a==1 and b==2:
  x =X-1
  y =Y-2
  if x==y:
    c = x//3
    N = c*2+1
    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(c*2+1,c,mod))
  else:
    if x>y:
      l = x-y
      d = (y-l)//3
      N = l+d*2+1
      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(l+d*2+1,d+1,mod))
    else:
      l = y-x
      d = (x-l)//3
      N = l+d*2+1
      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(l+d*2+1,d+1,mod))
else:
  print(0)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

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

counter = 0


def move(x, y, X, Y):
    global counter
    if (X + Y - x - y) % 3 != 0:
        return
    # if x >X:
    #     return
    # if y > Y:
    #     return
    if (x == X) and (y == Y):
        counter += 1
        return
    if Y > 2 * (X - x) + y:
        return
    if Y < (X - x) / 2 + y:
        return

    move(x + 1, y + 2, X, Y)
    move(x + 2, y + 1, X, Y)


move(0, 0, x, y)
print(counter / hash_no)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

x,y=map(int,input().split())
if (2*y-x)%3==0 and (2*x-y)%3==0:
    a=(2*y-x)//3
    b=(2*x-y)//3
    ans=combinations_count(a+b,a)
    print(ans%(10**9+7))
else:
    print('0')

Submission status: Wrong Answer

Solution code:
x, y = map(int, input().split())
n, m = 0, 0
for i in range(x+1):
    j = (x - i)/2
    if 2*i + j== y:
        n, m = int(i+j), int(i)

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

a = cmb(n,m)%(10**9+7)

print(a)

Submission status: Wrong Answer

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

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

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

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

if (2*y-x)%3!=0 or (2*x-y)%3!=0:
    print('0')
else:
    a=(2*y-x)//3
    b=(2*x-y)//3
    n=a+1
    r=b
    ans=comb(n+r-1,r,mod)
    print(ans%mod)

Submission status: Wrong Answer

Solution code:
mod=10**9+7

def framod(n, mod, a=1):
  for i in range(1,n+1):
    a=a * i % mod
  return a
  
def power(n, r, mod):
  if r == 0: return 1
  if r%2 == 0:
    return power(n*n % mod, r//2, mod) % mod
  if r%2 == 1:
    return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
  a=framod(n, mod)
  b=framod(k, mod)
  c=framod(n-k, mod)
  return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod
  
X, Y=map(int, input().split())
a=round(-X/3+2*Y/3, 10)
b=round(2*X/3-Y/3, 10)
if not (a.is_integer() and b.is_integer() and a>=0 and b>=0):
  print(0)
else:
  print(comb(int(a+b), int(a), mod))

Submission status: Wrong Answer

Solution code:
import sys
import itertools
from math import sqrt
input = sys.stdin.readline
mod = 10 ** 9 + 7

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

a = a_3 // 3
b = b_3 // 3

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

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

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

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

comb = Combination(5000000)
print(comb(a + b, a))

Submission status: Wrong Answer

Solution code:
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=factorial(n) %p
  b=factorial(k) %p
  c=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 and x != 0 and y != 0:
    s = (x+y)//3
    a = (s - (abs(x-y)//3))//2
    print(comb(s,a,10**9+7))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
def is_integer(n):
    try:
        float(n)
    except ValueError:
        return False
    else:
        return float(n).is_integer()
        
X,Y = map(int,input().split())
a = (2*Y-X)/3
b = (2*X-Y)/3
if is_integer(a):
    a = int(a)
else:
    print(0)
    exit()
if is_integer(b):
    b = int(b)
else:
    print(0)
    exit()
n = a+b

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

mod = 10**9+7 
ans = cmb(n,a) % mod
print(ans)

Submission status: Wrong Answer

Solution code:
from math import factorial

large = int(1e+9 + 7)

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

X2 = 2*X - Y
Y2 = -X + 2*Y

if X2%3 != 0:
    print "0"
    exit()
elif Y2%3 != 0:
    print "0"
    exit()

X2 = X2/3
Y2 = Y2/3

ans = 1

n = X2+Y2
m = Y2

for i in range(n-m+1, n+1):
    ans = ans*i
    ans = ans%large

for i in range(1, m+1):
    ans = ans*i
    ans = ans%large

print ans

Submission status: Wrong Answer

Solution code:
import sys

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


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

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

    def make_factorial_list(self, n):
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv


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

if w.is_integer():
    w = int(w)
else:
    print(0)
    sys.exit()

a = min(b, w-b)
comb = Combination(10**6)
ans = comb(w, a)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys


def alg_combination_mod(n, r, mod):
    r = min(n - r, r)
    if r == 0:
        return 1
    else:
        denominator = 1
        for i in range(n, n - r, -1):
            denominator = (denominator * i) % mod
        molecule = 1
        for i in range(1, r + 1):
            molecule = (molecule * i) % mod
        return denominator * pow(molecule, mod - 2, mod) % mod


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    x, y = list(map(int, readline().split()))
    if x / y == 2 or y / x == 2:
        print(1)
    else:
        cnt = min(x // 3, y // 3)
        x -= cnt * 3
        y -= cnt * 3
        xcnt = 0
        ycnt = 0
        if x == 0 and y == 0:
            xcnt = cnt
            ycnt = cnt
        elif x != 0 and y / x == 2:
            xcnt = cnt + x
            ycnt = cnt
        elif y != 0 and x / y == 2:
            xcnt = cnt
            ycnt = cnt + y
        else:
            print(0)
            exit()
        print(alg_combination_mod(xcnt + ycnt, xcnt, mod))


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import math
import itertools

def read():
    X, Y = list(map(int, input().strip().split()))
    return X, Y

def init_mod_combinations(MAX=500000, MOD=1000000007):
    fac = [0 for _ in range(MAX)]
    finv = [0 for _ in range(MAX)]
    inv = [0 for _ in range(MAX)]
    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
    return fac, finv, inv

def mod_combinations(n, k, MOD=1000000007):
    fac, finv, inv = init_mod_combinations(MAX=n+1, MOD=MOD)
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD


def solve(X, Y):
    # X = 2p + q, Y = p + 2q
    p = (2 * X - Y) // 3
    q = (2 * Y - X) // 3
    if 2*p+q!=X or p+2*q!=Y:
        # 到達不可能
        return 0
    # p+q 回の移動で到達可能
    # 移動パターンの総数は(p+q)Cp
    print("%dC%d" % (p+q, p))
    return mod_combinations(p+q, p)

if __name__ == '__main__':
    inputs = read()
    output = solve(*inputs)
    print("%d" % output)

Submission status: Wrong Answer

Solution code:
def nCr(n, r):
    """
    Calculate the number of combination (nCr = nPr/r!).
    The parameters need to meet the condition of n >= r >= 0.
    It returns 1 if r == 0, which means there is one pattern
    to choice 0 items out of the number of n.
    """

    # 10C7 = 10C3
    r = min(r, n-r)

    # Calculate the numerator.
    numerator = 1
    for i in range(n, n-r, -1):
        numerator *= i

    # Calculate the denominator. Should use math.factorial?
    denominator = 1
    for i in range(r, 1, -1):
        denominator *= i

    return numerator // denominator
a,s=map(int,input().split())
x=(a-2*s)//(-3)
y=(s-2*a)//(-3)
if x==0 and y==0:
  print("0")
else:
  d=nCr(x+y,x)
  print(d%(10**9+7))

Submission status: Wrong Answer

Solution code:
#import sys

#sys.setrecursionlimit(10000)

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

    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] = numerator[k - offset] // pivot
                denominator[k] = denominator[k] // pivot

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




def mod_combination(n, k, mod):
    # nCk (mod m)
    def mod_permutation(n, k, mod):
        if n<=k:
            return 1
        else:
            return (n * mod_permutation(n-1,k,mod))%mod

    def mod_inv_permutation(k, mod):
        k, mod = int(k), int(mod)
        if k<=1:
            return 1
        else:
            return (pow(k,mod-2,mod) * mod_inv_permutation(k-1, mod))%mod

    return (mod_permutation(n,n-k,mod) * mod_inv_permutation(k, mod))%mod


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=factorial(n) %p
    b=factorial(k) %p
    c=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())

ans = 0
if (x + y) % 3 != 0:
    ans = 0
else:
    a = (x + y) // 3
    b = (2*x - y) // 3
    ans = cmb(a,b, pow(10,9) + 7)
    #ans = mod_combination(a,b,pow(10,9) + 7)

print(ans)