Problem:


Score : 400 points

Problem Statement

There is a knight - the chess piece - at the origin (0, 0) of a two-dimensional grid.

When the knight is at the square (i, j), it can be moved to either (i+1,j+2) or (i+2, j+1).

In how many ways can the knight reach the square (X, Y)?

Find the number of ways modulo 10^9 + 7.

Constraints

1 \leq X \leq 10^6

1 \leq Y \leq 10^6

All values in input are integers.

Input

Input is given from Standard Input in the following format:

X Y

Output

Print the number of ways for the knight to reach (X, Y) from (0, 0), modulo 10^9 + 7.

Sample Input 1

3 3

Sample Output 1

2

There are two ways: (0,0) \to (1,2) \to (3,3) and (0,0) \to (2,1) \to (3,3).

Sample Input 2

2 2

Sample Output 2

0

The knight cannot reach (2,2).

Sample Input 3

999999 999999

Sample Output 3

151840682

Print the number of ways modulo 10^9 + 7.



Sample input:
3 3


Sample output:
2

Submission status: Accepted

Solution code:
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 and (2*y - x)%3 == 0 and (2*x - y) >= 0 and (2*y - x) >=0:
    a = (2*x - y)//3
    b = (2*y - x)//3
    c = cmb(a+b,a)
    print(c%(10**9 + 7))
else:
    print(0)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs,math,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
mod = 10**9+7 #出力の制限
N = 10**6
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

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 )
# a = cmb(n,r)
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

x,y = m()


li = []
count = 0

for i in range(0,x+1):
    nx = x - i
    ny = y - 2*i

    if nx >= 0 and ny >= 0 and nx == 2*ny:
        count += cmb(i+ny,i)
        count %= mod
print(count)

Submission status: Accepted

Solution code:
MOD=1000000007

def combination(n,m):
    if m==0:
        return 1
    else:
        return combination(n-1,m-1)*n//m

def pow_mod(a, b, p):
    if b == 0:
        return 1
    elif b%2 == 0:
        d = pow_mod(a, b//2, p)
        return (d**2)%p
    else:
        return (a*pow_mod(a,b-1,p))%p    
    
def factorial_mod(n,p):
    tmp = 1
    for i in range(1,n+1):
        tmp *= i
        tmp %= p
    return tmp


      
x,y=map(int,input().split())
if (x+y)%3!=0:
  print(0)
elif x*2<y:
  print(0)
elif y*2<x:
  print(0)
else:
  a=(x+y)//3
  x-=a
  y-=a
  #x+yCx
  if x>y:
    a=x
    x=y
    y=a
  W=x+1
  H=y+1
  ans = factorial_mod(W-1 + H-1, MOD)
  ans *= pow_mod(factorial_mod(H-1,MOD), MOD-2, MOD)
  ans %= MOD
  ans *= pow_mod(factorial_mod(W-1,MOD), MOD-2, MOD)
  ans %= MOD

 
  print(ans)

Submission status: Accepted

Solution code:
x, y = map(int, input().split())
mod = 1000000007
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
if (x + y) % 3 != 0:
  print(0)
else:
  n = (x + y) // 3
  if n > x or n > y:
    print(0)
  else:
    nx = x - n
    comb = Combination(n)
    print(comb(n, nx))

Submission status: Accepted

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 sum_ > x or sum_ > y:
        print(0)
        return

    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: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from math import factorial
from itertools import permutations

def cmb_fnct(MOD):
    #MOD:素数
    fact_mod = [1,1]
    inv_mod = [0,1]
    inv_fact_mod = [1,1]
    i = len(fact_mod)
    i_ = len(inv_fact_mod)

    def cmb(n,r):
        nonlocal i, i_
        r = min(r, n-r)
        if r<0: 
            return 0
        if r==0:
            return 1
        if r==1: 
            return n%MOD

        while n >= i:
            fact_mod[i:i] = [(fact_mod[i-1]*i)%MOD]
            i += 1

        while n-r >= i_:
            inv_mod[i_:i_] = [(-inv_mod[MOD%i_]*(MOD//i_))%MOD]
            inv_fact_mod[i_:i_] = [(inv_fact_mod[i_-1]*inv_mod[i_])%MOD]
            i_ += 1

        return fact_mod[n] * inv_fact_mod[r] * inv_fact_mod[n-r] % MOD
    return cmb

def solve():
    X, Y = map(int, input().split())
    a = -(X-2*Y)/3
    b = -(-2*X+Y)/3
    if a == int(a) and b == int(b):
        a = int(a)
        b = int(b)
    else:
        return '0'
    cmb = cmb_fnct(10**9+7)

    return str(cmb(a+b,a))

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

Submission status: Accepted

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 and (2*x-y) >= 0 and (2*y-x) >= 0:
    i = (2*x-y)//3
    j = (2*y-x)//3
    print(combi(i,j,10**9+7))
else:
    print(0)

Submission status: Accepted

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
    if c < 0 or d < 0:
        print(0)
    else:
        print(comb(c+d, c, 10 ** 9 + 7))

Submission status: Accepted

Solution code:
import math
X, Y = map(int,input().split())
if (X+Y)%3 != 0:
    print(0)
    exit(0)

k = (X+Y)//3
if k > X or k > Y:
    print(0)
    exit(0)

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 + 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(k,abs(k-X),mod))

Submission status: Accepted

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

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

p = (x+y)//3
if min(x,y) < p:
    print(0)
    exit()

fact = [1]
fact_inv = [1]
for i in range(10**6+4):
    new_fact = fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))


def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod

x = min(x,y)

print(mod_comb_k(p,x-p,mod))

Submission status: Accepted

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

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 = result * int(numerator[k]) % (1e9+7)

    return result


if 2 * X < Y or X > 2 * Y or (X+Y)%3 != 0:
    print(0)
else:
    D = 1e9+7
    M = (X+Y)//3
    m = (2*X-Y)//3
    n=(2*Y-X)//3 
    res = cmb(M,m) % D
    """for i in range(M, M-m,-1):
        res *= i 
    for i in range(1,m+1):
        res //= i """
    print(int(res))

Submission status: Accepted

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())
mod = 10 ** 9 + 7
ans_comb = []
for i in range(x // 2 + 1):
    j = x - 2 * i
    if 2 * i + j == x and 2 * j + i == y:
        ans_comb = [i, j]
if len(ans_comb) == 0:
    print(0)
else:
    print(comb(ans_comb[0] + ans_comb[1], ans_comb[1], 10 ** 9 + 7))

Submission status: Accepted

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)
if q<0: print(0),sys.exit()

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

Submission status: Accepted

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

mod = 10**9 +7

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

def inv(a,mod):
    r = [1,0,a]
    w = [0,1,mod]
    while w[2]!=1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = w
        w = r_new
    x,y = w[0],w[1]    # a*x+y*mod = 1
    return (mod+x%mod)%mod




if (x+y) % 3 == 0 and y <= 2*x and 2*y >= x:
    n = (x+y)//3
    m = x-n
    ans = fact(n,mod) * inv(fact(n-m,mod),mod) * inv(fact(m,mod),mod)
    print(ans % mod)
else:
    print(0)
    exit()

Submission status: Accepted

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


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

n = 2 * X - Y
m = 2 * Y - X
if n < 0 or m < 0 or n % 3 != 0 or m % 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: Accepted

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)  < 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: Accepted

Solution code:
M = 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])

    return result

def main():
    X, Y = map(int, input().split())
    if (2*X-Y) % 3 != 0 or (2*Y-X) % 3 != 0 or 2*X < Y or 2*Y < X:
        ans = 0
    else:
        a = (2*X-Y)//3
        b = (2*Y-X)//3
        ans = cmb(a+b, a)%M
    print(ans)


if __name__ == '__main__': main()

Submission status: Accepted

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

mod = 10**9+7 #出力の制限
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())
a=(2*x-y)//3
b=(2*y-x)//3
if a!=(2*x-y)/3 or b!=(2*y-x)/3:
    print(0)
else:
    print(cmb(a+b,a,mod))

Submission status: Accepted

Solution code:

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


mod = 10 ** 9 + 7
MAX = 10**6 + 1
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

def cominit():
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[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

if (2*Y-X)%3 == 0 and (2*X-Y)%3 == 0:
    n1 = (2*Y-X)//3
    n2 = (2*X-Y)//3
    if n1 < 0 or n2 < 0:
        print(0)
    else:
        cominit()
        ans = fac[(n1+n2)]*finv[n1]*finv[n2]
        ans %= mod
        print(ans)
        
else:
    print(0)

Submission status: Accepted

Solution code:
x, y = [int(i) for i in input().split()]
if (2*x - y)%3 != 0:
    print(0)
elif (2*x - y < 0) or ((2*y - x) < 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: Accepted

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:
        print(0)
        exit()
    n_plus = (t + step) // 2
    if not 0 <= n_plus <= step:
        print(0)
        exit()
    print(com(step, n_plus))

main()

Submission status: Accepted

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()
if W < 1 or H < 1:
    print(0)
    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: Accepted

Solution code:
import sys
x,y=map(int,input().split())
if (x+y)%3!=0:
    print(0)
    sys.exit()
dx=x-(x+y)//3
dy=y-(x+y)//3
if dx<0 or dy<0:
    print(0)
    sys.exit()
fact=[1]*(dx+dy+1)
MOD=10**9+7
def inv_mod(a):
  return pow(a,MOD-2,MOD)

for i in range(1,dx+dy+1):
  fact[i] = (i*fact[i-1])%MOD
fact_inv = [1] * (dx+dy+1)
fact_inv[-1] = inv_mod(fact[-1])
for i in range(dx+dy,0,-1):
  fact_inv[i-1] = (i*fact_inv[i])%MOD

def comb(n,k):
  x = fact[n]
  x *= fact_inv[k]
  x %= MOD
  x *= fact_inv[n-k]
  x %= MOD
  return x
print(comb(dx+dy,dx))