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

def modinv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = a // b
        a -= t * b
        b, a = a, b
        u -= t * v
        v, u = u, v
    u = u % m
    if (u < 0):
        u += m
    return u

def fact(n):
    if n <= 1:
        return 1
    ret = 1
    for i in range(2, n + 1):
        ret *= i
        ret = ret % (10 ** 9 + 7)
    
    return ret

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

nx, ny = (2 * y - x) / 3, (2 * x - y) / 3

if nx.is_integer() and ny.is_integer():
    n2x = int(nx)
    n2y = int(ny)
    gnx = modinv(fact(n2x), 10 ** 9 + 7)
    gny = modinv(fact(n2y), 10 ** 9 + 7)
    print((fact(n2x + n2y) * gnx % (10 ** 9 + 7)) * gny % (10 ** 9 + 7))
else:
    print('0')

Submission status: Wrong Answer

Solution code:
mod = 10**9+7

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

    choice = min(X,Y) - abs(X-Y)

    if choice >= 0 and choice %3 == 0:
        N = choice//3
        ans = 1
        for i in range(N+1,2*N+1):
            ans *= i
            ans %= mod
        for i in range(1,N+1):
            ans *= pow(i,mod-2,mod)
            ans %= mod
        return ans
    else:
        return 0

    

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

Submission status: Wrong Answer

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


def pow(a, b, p):
    if b == 0:
        return 1
    if b % 2 == 0:
        d = pow(a, b // 2, p)
        return (d * d) % p
    else:
        return (a * pow(a, b - 1, p)) % p


def fact(a, p):
    f = 1
    for i in range(1, a + 1):
        f *= i
        f %= p
    return f


if (X + Y) % 3 == 0:
    N = (X + Y) // 3
    ans = fact(N, MOD) * pow(fact(X - N, MOD), MOD - 2, MOD) * \
        pow(fact(Y - N, MOD), MOD - 2, MOD)
    ans %= MOD
else:
    ans = 0

print(ans)

Submission status: Wrong Answer

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

if (2 * X - Y) % 3 == 0:
    a = int((2 * X - Y) / 3)
else:
    a = 'No'
if (2 * Y - X) % 3 == 0:
    b = int((2 * Y - X) / 3)
else:
    b = 'No'

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

if a == 'No' or b == 'No':
    print(0)
else:
    ans = cmb(a + b, a)
    print(ans % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
import math


def combinations_count(n, r):
    if r < n - r:
        t = r
    else:
        t = n - r
    ans1 = 1
    ans2 = 1
    for i in range(t):
        ans1 *= (n-i)
        ans2 *= (t-i)
    return((ans1//ans2)% (10 ** 9 + 7))
        
X, Y = map(int, input().split())

if (X+Y)%3 == 0 and X < 2*Y and Y < 2 * X:
    print(combinations_count((X+Y)//3, (2*X-Y)//3))
else:
    print("0")

Submission status: Wrong Answer

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

if((2*Y)%3 != 0 or (2*X-Y)%3 != 0):
    print("No")
else:
    a =  (2*Y-X) / 3
    b =  (2*X-Y) / 3

    calc1 = math.factorial(a+b)
    calc2 = math.factorial(a)
    calc3 = math.factorial(b)
    calc = calc1 // (calc2*calc3)
    print(calc % (10**9+7))

Submission status: Wrong Answer

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

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

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

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

    return result

x, y = map(int, input().split())
if ((2*x - y) % 3 != 0) or ((2*y - x)% 3 != 0):
    print(0)
else:
    mod = 10**9 + 7
    s = (2*x - y) // 3
    t = (2*y - x) // 3
    val = cmb(s+t, s)
    print(val%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=-X/3+2*Y/3
b=2*X/3-Y/3
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:
a,b=map(int,input().split())
import math
if (a+b)%3!=0:
  print(0)
  exit()
f=(a+b)//3
g=a-f
f=f-g
h=min(f,g)
ans=1

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
  

print(comb(f+g,min(f,g),10**9+7))

Submission status: Wrong Answer

Solution code:
import sys
MOD = 10**9+7

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])
            result %= MOD
    return result

X,Y = map(int,input().split())
if (2*X-Y) % 3 != 0 or (2*Y-X) % 3 != 0:
    print(0)
    sys.exit()
n = (2*X-Y)//3
m = (2*Y-X)//3
k = n + m
print(cmb(k,n))

Submission status: Wrong Answer

Solution code:
def comb(a,b,m):
	if b == 0 or b == a:
		ret = 1
	else:
		ret = 1
		for i in range(a-b+1,a+1):
			ret = (ret * i) % m
		for i in range(1,b+1):
			ret = (ret * pow(i,m-2,m) ) % m
	return ret

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

ans = 0
if (2*x-y) % 3 == 0 and (2*y-x) % 3 == 0:
    x, y = (2*x-y) // 3, (2*y-x) // 3
    ans = comb(x+y,y,mod)
print(ans)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc145/tasks/abc145_d

MOD = 1000000007

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

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 main():
    X, Y = map(int, input().split())

    if (X + Y) % 3 != 0 or max(X,Y) > min(X,Y):
        print(0)
        return
    a = X // 3
    b = Y // 3

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

    print(ans)

main()

Submission status: Wrong Answer

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

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

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

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

    return result

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

ans = 0
if (X+Y)%3 != 0:
    pass
else:
    N = (X+Y)//3
    t = X - N
    if t > 0:
         if (2*N-t) == Y:
             ans = cmb(N,t)
             ans = ans%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import math

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())
if ((x + y) % 3 != 0):
	print("0")
else:
	n_x = (2 * x - y) // 3
	n_y = (2 * y - x) // 3
	n_xy = (x + y) // 3
	print(int(cmb(n_xy,n_x))%1000000007)

Submission status: Wrong Answer

Solution code:
import math

def modinv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = a // b
        a -= t * b
        b, a = a, b
        u -= t * v
        v, u = u, v
    u = u % m
    if (u < 0):
        u += m
    return u

def fact(n):
    if n <= 1:
        return 1
    ret = 1
    for i in range(2, n + 1):
        ret *= i
        ret = ret % (10 ** 9 + 7)
    
    return ret

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

nx, ny = - x / 3 + 2 * y / 3, 2 * x / 3 - y / 3

if nx.is_integer() and ny.is_integer():
    n2x = int(nx)
    n2y = int(ny)
    gnx = modinv(fact(n2x), 10 ** 9 + 7)
    gny = modinv(fact(n2y), 10 ** 9 + 7)
    print((fact(n2x + n2y) * gnx % (10 ** 9 + 7)) * gny % (10 ** 9 + 7))
else:
    print('0')

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7
fac = [1] * (10 ** 6 + 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
a, b = x - t * 3, y - t * 3
if a * 2 == b or b * 2 == a:
    n = t * 2 + min(a, b)
    print((fac[n] * pow(fac[n - t], MOD - 2, MOD)
           * pow(fac[t], MOD - 2, MOD)) % MOD)
else:
    print(0)

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 = X - tot
x = tot - y

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import math

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())
if ((x + y) % 3 != 0):
	print("0")
else:
	n_x = (2 * x - y) // 3
	n_y = (2 * y - x) // 3
	n_xy = (x + y) // 3
	print(cmb(n_xy,n_x)%1000000007)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
 
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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

X, Y = MAP()

x, y = 0, 0
while (X!=0 or Y!=0):
	if X >= 3 and Y >= 3:
		x += 1
		y += 1
		X -= 3
		Y -= 3
	else:
		if 0 < X < 3:
			X -= 1
			Y -= 2
			y += 1
			if Y < 0:
				print(0)
				sys.exit()
		elif 0 < Y < 3:
			Y -= 1
			X -= 2
			x += 1
			if X < 0:
				print(0)
				sys.exit()

H = 10**6//2
W = 10**6//2
factorial = [1]
for i in range(1, H+W):
	factorial.append(factorial[i-1] * i % mod)


def power(x, y):
	if y == 0:
		return 1
	elif y == 1:
		return x % mod
	elif y % 2 == 0:
		return power(x, int(y/2)) ** 2 % mod
	else:
		return power(x, int((y-1)/2)) ** 2 * x % mod
def C(n, r):
	return (((factorial[n] * x_inv[r]) % mod) * x_inv[n-r]) % mod

x_inv = [0] * (H+W)
x_inv[-1] = power(factorial[-1], mod-2)
for i in range(H+W-2, -1, -1):
	x_inv[i] = x_inv[i+1] * (i+1) % mod

print(C(x+y, y))

Submission status: Wrong Answer

Solution code:
import itertools
x,y=map(int,input().split())
x=min(x,y)
y=max(x,y)
a=y-x
x-=a
y-=a*2
#print(x,y)
if x!=y or x%3!=0 or y%3!=0 or x<0 or y<0:
    print(0)
else:
    b=x//3
    ans=0
    #print(a,b)
    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(a+2*b, b, mod=10**9+7))

Submission status: Wrong Answer

Solution code:
import math

def modinv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = a // b
        a -= t * b
        b, a = a, b
        u -= t * v
        v, u = u, v
    u = u % m
    if (u < 0):
        u += m
    return u

def fact(n):
    if n <= 1:
        return 1
    ret = 1
    for i in range(2, n + 1):
        ret *= i
        ret = ret % (10 ** 9 + 7)
    
    return ret

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

nx, ny = - x / 3 + 2 * y / 3, 2 * x / 3 - y / 3

if nx.is_integer() and ny.is_integer():
    n2x = int(nx)
    n2y = int(ny)
    gnx = modinv(fact(n2x), 10 ** 9 + 7)
    gny = modinv(fact(n2y), 10 ** 9 + 7)
    print(fact(n2x + n2y) * gnx * gny % (10 ** 9 + 7))
else:
    print('0')

Submission status: Wrong Answer

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

import numpy as np

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

MOD = 10**9 + 7

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U,MOD):
    x = np.arange(U,dtype=np.int64); x[0] = 1
    fact = cumprod(x,MOD)
    x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
    fact_inv = cumprod(x,MOD)[::-1]
    return fact,fact_inv

U = 10**6
fact, fact_inv = make_fact(U,MOD)

if (X+Y) % 3 != 0:
    print(0)
    exit()
A = (2*X - Y) // 3
B = (2*Y - X) // 3
answer = fact[A+B] * fact_inv[A] % MOD * fact_inv[B] % MOD
print(answer)

Submission status: Wrong Answer

Solution code:
def find_power(n):
    # 0!からn!までのびっくりを出してくれる関数
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(10**9+7)
    return powlist

def find_inv_power(n):
    #0!からn!までの逆元を10**9+7で割ったあまりリストを作る関数
    powlist=find_power(n)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist

def combi(a,b,n,r,mod):
    if n<r:
        return 0
    elif n>=r:
        return (a[n]*b[r]*b[n-r])%(mod)


x,y=map(int,input().split())
power=find_power(1000000)
invpower=find_inv_power(1000000)
if (2*x-y)%3!=0 or (2*y-x)%3!=0:
    print(0)
else:
    if (2*x-y)>=0 and (2*y-x)>=0:
        a=(2*y-x)//3
        b=(2*x-y)//3
        print(combi(power,invpower,a+b,b,10**9+7))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

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

# a + 2b = X
# 2a + b = Y
b = (2 * X - Y) / 3  # 下2、右1移動の回数
a = X - 2 * b  # 下1、右2移動の回数
mod = 10 ** 9 + 7

if int(b) != b or int(a) != a:
    ans = 0
elif b < 0 or a < 0:
    ans = 0
else:
    fact_list = []
    N = int(a + b)
    R = int(a)

    for i in range(1, N + 1):
        if i == 1:
            fact_n = 1 % mod
        else:
            fact_n = fact_list[i - 2] * i % mod
        fact_list.append(fact_n)

    fact_n_r = fact_list[N - R - 1]
    fact_r = fact_list[R - 1]

    w = pow(fact_n_r * fact_r % mod, (mod - 2), mod)

    ans = fact_n * w % mod

print(ans)

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=-X/3+2*Y/3
b=2*X/3-Y/3
if not (a.is_integer() and b.is_integer()):
  print(0)
else:
  print(comb(int(a+b), int(a), mod))

Submission status: Wrong Answer

Solution code:
import math
ab = input().split()
a, b = int(ab[0]), int(ab[1])
n=int((a+b)/3)
if a>b:
	m=a-n
else:
	m=b-n
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

print(combinations_count(n, m))

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
 
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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

X, Y = MAP()

x, y = 0, 0
while (X!=0 or Y!=0):
	if X >= 3 and Y >= 3:
		x += 1
		y += 1
		X -= 3
		Y -= 3
	else:
		if 0 < X < 3:
			X -= 1
			Y -= 2
			y += 1
			if Y < 0:
				print(0)
				sys.exit()
		elif 0 < Y < 3:
			Y -= 1
			X -= 2
			x += 1
			if X < 0:
				print(0)
				sys.exit()

print(x, y) 

H = 10**6//2
W = 10**6//2
factorial = [1]
for i in range(1, H+W):
	factorial.append(factorial[i-1] * i % mod)


def power(x, y):
	if y == 0:
		return 1
	elif y == 1:
		return x % mod
	elif y % 2 == 0:
		return power(x, int(y/2)) ** 2 % mod
	else:
		return power(x, int((y-1)/2)) ** 2 * x % mod
def C(n, r):
	return (((factorial[n] * x_inv[r]) % mod) * x_inv[n-r]) % mod

x_inv = [0] * (H+W)
x_inv[-1] = power(factorial[-1], mod-2)
for i in range(H+W-2, -1, -1):
	x_inv[i] = x_inv[i+1] * (i+1) % mod

print(C(x+y, y))

Submission status: Wrong Answer

Solution code:
a,b=map(int,input().split())
aa=a
bb=a
x=0
y=0
while aa>0 and bb>0:
	if aa>bb:
		aa-=1
		x+=1
	else:
		bb-=1
		y+=1
	aa-=1
	bb-=1
if aa!=0 or bb!=0:
	print(0)
	exit()
mod=10**9+7
fac=[1]
for i in range(max(a,b)):
	fac.append(fac[i]*(i+1)%mod)
x+=y
r=pow(fac[y]*fac[x-y]%mod,mod-2,mod)
print(fac[x]*r%mod)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def mpow(x: int, k: int, MOD=1000000007) -> int:
    """
    x^kのmodを返します
    """
    res = 1
    y = x
    while (k):
        if(k % 2 == 1):
            res = (res * y) % MOD
        y = (y ** 2) % MOD
        k = k // 2
    return res

def mfact(MAX=200000, MOD=1000000007) -> 'List[int]':
    """
    MAXまでの階乗のmodの配列を返します
    """
    f = [1]
    for i in range(1, MAX):
        f.append(f[-1] * i % MOD)
    return f

def inv(x: int, MOD=1000000007) -> 'List[int]':
    """
    フェルマーの小定理に基づく逆元を返します
    """
    return mpow(x, MOD - 2, MOD)

def mcomb(n: int, k: int, f: 'List[int]', MOD=1000000007) -> int:
    """
    nCkのmodを返します
    """
    a = f[n]
    b = f[n-k]
    c = f[k]
    bc = (b * c) % MOD
    return (a * inv(bc)) % MOD

def solve(X: int, Y: int):
    if (2*Y-X) % 3 != 0 or (2*X-Y) % 3 != 0:
        print(0)
        return
    x = (2*Y-X) // 3
    y = (2*X-Y) // 3
    f = mfact(2000000)
    print(mcomb(x+y, x, f))
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(X, Y)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def comb(a,b,m):
	if b == 0 or b == a:
		ret = 1
	else:
		ret = 1
		for i in range(a-b+1,a+1):
			ret = (ret * i) % m
		for i in range(1,b+1):
			ret = (ret * pow(i,m-2,m) ) % m
	return ret

mod = 10**9+7
x, y = [ int(v) for v in input().split() ]
x, y = (2*x-y) // 3, (2*y-x) // 3

print(comb(x+y,y,mod))

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7

def main():
    x, y = map(int, input().split(' '))
    if (2*x-y) % 3 == 0 and (2*y-x) % 3 == 0:
        n = (2*x-y) // 3
        m = (2*y-x) // 3
        print(cmb(n+m, n) % mod)
    else:
        print(0)


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
a, b = map(int, input().split())

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

def power(x, y, mod):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2, mod)**2 % mod
    else            : return power(x, y//2, mod)**2 * x % 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

import math
if (2 * a - b) % 3 != 0 or (2 * b - a) % 3 != 0:
    print(0)
else:
    d = (2 * b - a) // 3
    c = (2 * a - b) // 3
    print(comb(c+d, c, 10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res


def modinv(a, mod):
    return modpow(a, mod - 2, mod)


def main():
    x, y = map(int, input().split())
    if (2 * y - x) % 3 != 0 or  (2 * x - y) % 3 != 0 or (2 * x - y) < 0 or (2 * y - x) % 3 < 0:
        print(0)
        exit()
    p = (2 * y - x) // 3
    q = (2 * x - y) // 3
    
    ans = 1
    for i in range(1, p + q + 1):
        ans = (ans * i) % MOD
    
    v,z=1,1
    for i in range(1, p + 1):
        v = (v * i) % MOD
        
    for i in range(1, q + 1):
        z = (z * i) % MOD
    
    vz = (v*z)%MOD
    ans = ans*modinv(vz,MOD) % MOD
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7
N = 10 ** 6
fact = [1]*(N+1)
rfact = [1]*(N+1)
r = 1
for i in range(1, N+1):
  fact[i] = r = r * i % MOD
rfact[N] = r = pow(fact[N], MOD-2, MOD)
for i in range(N, 0, -1):
  rfact[i-1] = r = r * i % MOD

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % MOD

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD

x,y = map(int, input().split())
ans = 0
if not (x + y) % 3:
  cnt = (x+y) // 3
  a = abs(x-y)
  if cnt >= a:
    r = (cnt - a) // 2
  ans = comb(cnt,r)
print(ans)

Submission status: Wrong Answer

Solution code:
import math

def ncr(n, r):
    r = min(r, n - r)
    if r == 0: return 1;
    if r == 1: return n;
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i 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 *= numerator[k]
    return result

def combi(i,j,mod):
    out = ncr(i+j,j)
    return out % mod

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

if (2*x-y)%3 == 0 and (2*y-x)%3 == 0:
    i = (2*x-y)//3
    j = (2*y-x)//3
    print(combi(i,j,10**9+7))
else:
    print(0)

Submission status: Wrong Answer

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

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

    def invf(self,n):
        return self.inv[n]

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

s,t=LI()
a=(2*t-s)//3
b=(2*s-t)//3
if (2*t-s)%3!=0 or (2*s-t)%3!=0:
    print(0)
    show(a,b)
    exit()

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

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
 
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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

X, Y = MAP()

x, y = 0, 0
while (X!=0 or Y!=0):
	if X >= 3 and Y >= 3:
		x += 1
		y += 1
		X -= 3
		Y -= 3
	else:
		if X < 3:
			X -= 1
			Y -= 2
			y += 1
			if Y < 0:
				print(0)
				sys.exit()
		elif Y < 3:
			Y -= 1
			X -= 2
			x += 1
			if X < 0:
				print(0)
				sys.exit()

print(x, y) 

H = 10**6//2
W = 10**6//2
factorial = [1]
for i in range(1, H+W):
	factorial.append(factorial[i-1] * i % mod)


def power(x, y):
	if y == 0:
		return 1
	elif y == 1:
		return x % mod
	elif y % 2 == 0:
		return power(x, int(y/2)) ** 2 % mod
	else:
		return power(x, int((y-1)/2)) ** 2 * x % mod
def C(n, r):
	return (((factorial[n] * x_inv[r]) % mod) * x_inv[n-r]) % mod

x_inv = [0] * (H+W)
x_inv[-1] = power(factorial[-1], mod-2)
for i in range(H+W-2, -1, -1):
	x_inv[i] = x_inv[i+1] * (i+1) % mod

print(C(x+y, y))

Submission status: Wrong Answer

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

mod = 10 ** 9 + 7
N = 10 ** 6
g1 = [1, 1]  # 元
g2 = [1, 1]  # 逆元
inverse = [0, 1]  # 逆元計算用

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

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

if ((2 * X - Y) > 0) and ((2 * X - Y) % 3 == 0):
    t = (2 * X - Y) // 3
else:
    print(0)
    exit()

if ((2 * Y - X) > 0) and ((2 * Y - X) % 3 == 0):
    s = (2 * Y - X) // 3
else:
    print(0)
    exit()

print(cmb(s + t, s, mod))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	X,Y = inputMap()

	print(1)

if __name__ == "__main__":
	main()