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:
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 * x - y) % 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:
X, Y = map(int, input().split())
MOD = 10 ** 9 + 7

def comb(n, k):
    ret = 1
    for i in range(1, k + 1):
        ret = ret * (n - i + 1) % MOD        
        ret = ret * pow(i, MOD - 2, MOD) % MOD
        
    return ret

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

if n == int(n) and m == int(m):
    print(comb(int(n + m), int(n)))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys
import math

MOD=10**9+7

def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx


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

if (x+y)%3!=0: print(0),sys.exit()
p=(x+y)//3
q=min((2*y-x)//3,(2*x-y)//3)

ans=1
for i in range(q):
    ans=(ans*(p-i)*egcd(i+1,MOD))%MOD
print(ans)

Submission status: Wrong Answer

Solution code:

import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
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) % (10 ** 9 + 7))
    
else:
    
    print("0")

Submission status: Wrong Answer

Solution code:
import sys; readline = sys.stdin.readline
from collections import deque


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

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

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

P = 10**9 + 7

t = n + m
s = min(n, m)

ans = 1
for i in range(t, t - s, -1):
    ans = ans * i
    ans %= P

d = 1
for i in range(s):
    d *= (i + 1)
    d %= P

def sp(x, n):
    if n == 0:
        return 1
    r = n % 2
    ret = sp(x, n//2) ** 2
    ret %= P
    if r == 1:
        ret *= x
        ret %= P
    return ret
dinv = sp(d, P - 2)

ans = ans * dinv
ans %= P

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()))
    cnt = max(x // 3, y // 3)
    x -= cnt * 3
    y -= cnt * 3
    if x == 1 and y == 2:
        xcnt = cnt
        ycnt = cnt + 1
    elif x == 2 and y == 1:
        xcnt = cnt + 1
        ycnt = cnt
    elif x == 0 and y == 0:
        xcnt = cnt
        ycnt = cnt
    else:
        print(0)
        exit()
    print(alg_combination_mod(xcnt + ycnt, xcnt, mod))


if __name__ == '__main__':
    solve()

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(2)

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

if X==0 or Y==0:
    print(0)
    exit()

N=min(X,Y)
factl=[1]
for i in range(1,N+1):
    factl.append(factl[-1]*i%mod)
invl=[pow(factl[-1],mod-2,mod)]
for i in range(N,0,-1):
    invl.append(invl[-1]*i%mod)
invl.reverse()
def Comb(a,b):
    return factl[a]*invl[a-b]*invl[b]%mod

div=Y//3
x,y=div,div
X,Y=X-3*div,Y-3*div
if X==0 and Y==0:
    pass
elif X==0 or Y==0:
    print(0)
    exit()
elif X//Y == 2 and X%Y==0:
    x+=Y
else:
    print(0)
    exit()

print(Comb(x+y,y))

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(1000005)
    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:
x, y = [int(i) for i in input().split()]
if (2*x - y)%3 != 0:
    print(0)
elif 2*x - y < 0:
    print(0)
else:
    LIM = 2*(10**6 + 5)
    fct = [1]*LIM
    inv = [1]*LIM
    MOD = 10**9 + 7
    for i in range(1, LIM):
        fct[i] = ((i%MOD)*(fct[i-1]%MOD))%MOD

    for i in range(1, LIM):
        inv[i] = (((inv[i-1])%MOD)*(pow(i, MOD-2, MOD)%MOD)%MOD)
    
    B = (2*x - y)//3
    A = x - (2*B)
    num = fct[A+B]
    den = ((inv[A]%MOD)*(inv[B])%MOD)%MOD
    print((((num)%MOD)*((den)%MOD))%MOD)

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

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


print(ans)

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

if  X>Y*2 or Y>X*2:
    print("koko")
    print(0)
    exit()
if (X+Y)%3!=0:
    print(0)
    exit()

count=0
_count=0
while X>0 and Y>0:
    if X>Y:
        X-=2
        Y-=1

        _count+=1
    else:

        X-=1
        Y-=2
    #print(X,Y)
    count+=1

#print(count,_count)
print(cmb(count,_count)%mod)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def com(com_n, com_r):
        return fac[com_n] * inv[com_r] * inv[com_n - com_r] % md

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

    # combinationの準備
    md = 10 ** 9 + 7
    n_max = 10 ** 6
    fac = [1]
    inv = [1] * (n_max + 1)
    k_fac_inv = 1
    for i in range(1, n_max + 1):
        k_fac_inv = k_fac_inv * i % md
        fac.append(k_fac_inv)
    k_fac_inv = pow(k_fac_inv, md - 2, md)
    for i in range(n_max, 1, -1):
        inv[i] = k_fac_inv
        k_fac_inv = k_fac_inv * i % md

    s, t = x + y, x - y
    if s % 3:
        print(0)
        exit()
    step = s // 3
    if (t + step) % 2 or t + step < 0:
        print(0)
        exit()
    n_plus = (t + step) // 2
    print(com(step, n_plus))

main()

Submission status: Wrong Answer

Solution code:
MOD = 1000000007

x,y = map(int,input().split())
if (x+y)%3!=0:
    print(0)
    exit()
p = (x+y)//3
W = x-p+1
H = y-p+1

if W == 1 or H == 1:
    print(1)
    exit()

numer = 1

inv = [0 for _ in range(max(W,H))]
inv[0] = 1

for i in range(W+H-2):
    numer *= i+1
    numer %= MOD

for i in range(1,len(inv)):
    inv[i] = inv[i-1]*pow(i+1,MOD-2,MOD) %MOD

print(numer*inv[H-2]*inv[W-2]%MOD)

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:
        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:
# -*- coding: utf-8 -*-

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

sub = (X - Y) // 3
times = (X + Y) // 3
if (X + Y) % 3:
    print('0')
    exit()
if abs(sub) > times:
    print('0')
    exit()

x = X - times
y = Y - times


def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


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


def combination(n, r, mod):
    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(times, y, mod))

Submission status: Wrong Answer

Solution code:
x, y = [int(i) for i in input().split()]
if (2*x - y)%3 != 0:
    print(0)
else:
    LIM = 2*(10**6 + 5)
    fct = [1]*LIM
    inv = [1]*LIM
    MOD = 10**9 + 7
    for i in range(1, LIM):
        fct[i] = ((i%MOD)*(fct[i-1]%MOD))%MOD
        #fct[i] %= MOD

    for i in range(1, LIM):
        inv[i] = (((inv[i-1])%MOD)*(pow(i, MOD-2, MOD)%MOD)%MOD)
        #inv[i] %= MOD
    
    B = (2*x - y)//3
    A = x - (2*B)
    num = fct[A+B]
    den = ((inv[A]%MOD)*(inv[B])%MOD)%MOD
    print(((num)%MOD*(den)%MOD)%MOD)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]


def main():
    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
    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 = LI()
    if (x + y) % 3 != 0:
        print(0)
        return

    sum_ = (x + y) // 3
    tmp_x = 2 * sum_
    if tmp_x > x:
        c_y = tmp_x - x
        c_x = sum_ - c_y
    else:
        c_y = -(tmp_x - x)
        c_x = sum_ - c_y

    print(cmb(sum_, c_x, MOD))


if __name__ == '__main__':
    main()

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*y-x)%3!=0 or (2*y-x)%3!=0:
    print(0)
else:
    if (2*y-x)>=0 and (2*x-y)>=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:
import sys
from heapq import heapify, heappop, heappush
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

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]) %mod

    return result

X, Y = IL()

num = 0
n = 0
for i in range(max(X,Y)+1): #(1, 2)を取る回数
  x = X - i
  y = Y - 2*i
  if x == 2*y:
    n = i
    num = i + y
    break
if num == 0:
  print(0)
else:
  print(cmb(num, n) %mod)

Submission status: Wrong Answer

Solution code:
#
import sys
import math
import numpy as np
import itertools
# いくつか入力
x,y = (int(i) for i in input().split())  

MOD = 1000000007

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

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

upper=1
lower=1

for i in range(1,a+b+1,1):
    upper *= i
    upper %= MOD

for i in range(1,a+1,1):
    lower *= i
    lower %= MOD

for i in range(1,b+1,1):
    lower *= i
    lower %= MOD

# karimono
# https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
def mul(a, b):
    return ((a % MOD) * (b % MOD)) % MOD

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % MOD
    elif y % 2 == 0 : return power(x, y//2)**2 % MOD
    else            : return power(x, y//2)**2 * x % MOD

def div(a, b):
    return mul(a, power(b, MOD-2))

answer = div(upper,lower)

print(answer)

Submission status: Wrong Answer

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

n = (2 * x - y) / 3
m = (2 * y - x) / 3
mod = 10 ** 9 + 7

if int(n) == n and int(m) == m:
    n = int(n)
    m = int(m)
    fact = [1]
    ans = comb(n + m, n, mod)
    ans %= mod
    print(ans)

else:
    print(0)

Submission status: Wrong Answer

Solution code:
x, y = [int(i) for i in input().split()]
if (2*x - y)%3 != 0:
    print(0)
else:
    LIM = 2*(10**6 + 5)
    fct = [1]*LIM
    inv = [1]*LIM
    MOD = 10**9 + 7
    for i in range(1, LIM):
        fct[i] = ((i%MOD)*(fct[i-1]%MOD))%MOD
        #fct[i] %= MOD

    for i in range(1, LIM):
        inv[i] = (((inv[i-1])%MOD)*(pow(i, MOD-2, MOD)%MOD)%MOD)
        #inv[i] %= MOD
    
    B = (2*x - y)//3
    A = x - (2*B)
    num = fct[A+B]
    den = ((inv[A]%MOD)*(inv[B])%MOD)%MOD
    print(((num)%MOD*(den)%MOD))

Submission status: Wrong Answer

Solution code:
x,y=map(int,input().split())
n=(2*x-y)/3
m=(2*y-x)/3
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 n>0 and m>0 and n%1==0 and m%1==0:
  n=int(n)
  m=int(m)
  print(cmb(n+m,n)%(10**9+7))
else:
  print(0)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]


def main():
    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
    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 = LI()
    if (x + y) % 3 != 0:
        print(0)
        return

    sum_ = (x + y) // 3
    tmp_x = 2 * sum_
    if tmp_x > x:
        c_y = tmp_x - x
        c_x = sum_ - c_y
    else:
        c_y = -(tmp_x - x)
        c_x = sum_ - c_y
    print(sum_, c_x, c_y, tmp_x)
    print(cmb(sum_, c_x, MOD))


if __name__ == '__main__':
    main()

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)


flag = True
a = 0
b = 0

if (2*y-x)%3 != 0 or (2*y-x) < 0:
  flag = False
else:
  a = (2*y-x)//3

if (2*x-y) %3 != 0 or (2*x-y) < 0:
  flag = False
else:
  b = (2*x-y)//3

if not flag:
  print(0)
else:
  print(a+b,a)
  print(cmb(a+b,a,10**9+7))

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*y-x)%3!=0 or (2*y-x)%3!=0:
    print(0)
else:
    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:
import sys
x,y = map(int, input().split( ))
mod = 10**9+7

def chs(s,t,mod):
    nume =  1
    for i in range(s-t+1,s+1):
        nume *= i
        nume %= mod 
    deno = 1
    for i in range(1,t+1):
        deno *= i
        deno %= mod
    deno = pow(deno,mod-2,mod)
    
    return (nume*deno%mod)
if (x+y)%3!=0:
    print(0)
    sys.exit()
a = (x+y)//3
x-=a
y-=a
print(chs(x+y,y,mod))

Submission status: Wrong Answer

Solution code:
# Python3 code to find minimum steps to reach
# to specific cell in minimum moves by Knight
class cell:

    def __init__(self, x=0, y=0, dist=0):
        self.x = x
        self.y = y
        self.dist = dist

    # checks whether given position is


# inside the board
def isInside(x, y, N):
    if (x >= 1 and x <= N and
            y >= 1 and y <= N):
        return True
    return False


# Method returns minimum step to reach
# target position
def minStepToReachTarget(knightpos,
                         targetpos, N):
    # all possible movments for the knight
    dx = [2, 2, 1, 1]
    dy = [1, 1, 2, 2]

    queue = []

    # push starting position of knight
    # with 0 distance
    queue.append(cell(knightpos[0], knightpos[1], 0))

    # make all cell unvisited
    visited = [[False for i in range(N + 1)]
               for j in range(N + 1)]

    # visit starting state
    visited[knightpos[0]][knightpos[1]] = True

    # loop untill we have one element in queue
    while (len(queue) > 0):

        t = queue[0]
        queue.pop(0)

        # if current cell is equal to target
        # cell, return its distance
        if (t.x == targetpos[0] and
                t.y == targetpos[1]):
            return t.dist

        # iterate for all reachable states
        for i in range(4):

            x = t.x + dx[i]
            y = t.y + dy[i]

            if (isInside(x, y, N) and not visited[x][y]):
                visited[x][y] = True
                queue.append(cell(x, y, t.dist + 1))

            # Driver Code


if __name__ == '__main__':
    N = 1000
    targetpos = list(map(int, input().split()))
    knightpos = [0, 0]
    print(int(minStepToReachTarget(knightpos,
                               targetpos, N) % 1e7)) if minStepToReachTarget(knightpos,
                                                                            targetpos, N) is not None else print(0)

# This code is contributed by
# Kaustav kumar Chanda

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())

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


print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 1000000007

x,y = map(int,input().split())
if (x+y)%3!=0:
    print(0)
    exit()
p = (x+y)//3
W = x-p+1
H = y-p+1

numer = 1

inv = [0 for _ in range(max(W,H))]
inv[0] = 1

for i in range(W+H-2):
    numer *= i+1
    numer %= MOD

for i in range(1,len(inv)):
    inv[i] = inv[i-1]*pow(i+1,MOD-2,MOD) %MOD

print(numer*inv[H-2]*inv[W-2]%MOD)

Submission status: Wrong Answer

Solution code:
x, y = [int(i) for i in input().split()]
if (2*x - y)%3 != 0:
    print(0)
else:
    LIM = 2*(10**6 + 5)
    fct = [1]*LIM
    inv = [1]*LIM
    MOD = 10**9 + 7
    for i in range(1, LIM):
        fct[i] = i*fct[i-1]
        fct[i] %= MOD

    for i in range(1, LIM):
        inv[i] = inv[i-1]*pow(i, MOD-2, MOD)
        inv[i] %= MOD
    
    B = (2*x - y)//3
    A = x - (2*B)
    num = fct[A+B]
    den = ((inv[A]%MOD)*(inv[B])%MOD)%MOD
    print(((num)%MOD*(den)%MOD))

Submission status: Wrong Answer

Solution code:
class combination():
    #素数のmod取るときのみ　速い
    def __init__(self, n, mod):
        self.n = n
        self.fac = [1] * (n + 1)
        self.inv = [1] * (n + 1)
        for j in range(1, n + 1):
            self.fac[j] = self.fac[j - 1] * j % mod

        self.inv[n] = pow(self.fac[n], mod - 2, mod)
        for j in range(n - 1, -1, -1):
            self.inv[j] = self.inv[j + 1] * (j + 1) % mod

    def comb(self, n, r, mod):
        if r > n or n < 0 or r < 0:
            return 0
        return self.fac[n] * self.inv[n - r] * self.inv[r] % mod

def examD(mod):
    X, Y = LI()
    if X%3!=0:
        ans = 0
    else:
        N = (X+Y)//3
        if N>Y:
            ans = 0
        else:
            k = (N-(X-Y))//2
            C = combination(N,mod)
            ans = C.comb(N,k,mod)
    print(ans)


import sys,copy,bisect,itertools
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD(mod)

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

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:
#gfg
# Python3 code to find minimum steps to reach
# to specific cell in minimum moves by Knight
class cell:

    def __init__(self, x=0, y=0, dist=0):
        self.x = x
        self.y = y
        self.dist = dist

    # checks whether given position is


# inside the board
def isInside(x, y, N):
    if (x >= 1 and x <= N and
            y >= 1 and y <= N):
        return True
    return False


# Method returns minimum step to reach
# target position
def minStepToReachTarget(knightpos,
                         targetpos, N):
    # all possible movments for the knight
    dx = [2, 2, 1, 1]
    dy = [1, 1, 2, 2]

    queue = []

    # push starting position of knight
    # with 0 distance
    queue.append(cell(knightpos[0], knightpos[1], 0))

    # make all cell unvisited
    visited = [[False for i in range(N + 1)]
               for j in range(N + 1)]

    # visit starting state
    visited[knightpos[0]][knightpos[1]] = True

    # loop untill we have one element in queue
    while (len(queue) > 0):

        t = queue[0]
        queue.pop(0)

        # if current cell is equal to target
        # cell, return its distance
        if (t.x == targetpos[0] and
                t.y == targetpos[1]):
            return t.dist

        # iterate for all reachable states
        for i in range(4):

            x = t.x + dx[i]
            y = t.y + dy[i]

            if (isInside(x, y, N) and not visited[x][y]):
                visited[x][y] = True
                queue.append(cell(x, y, t.dist + 1))

            # Driver Code


if __name__ == '__main__':
    N = 30
    targetpos = list(map(int, input().split()))
    knightpos = [0, 0]
    print(int(minStepToReachTarget(knightpos,
                               targetpos, N) % 1e7)) if minStepToReachTarget(knightpos,
                                                                            targetpos, N) is not None else print(0)

# This code is contributed by
# Kaustav kumar Chanda