N=int(input())
M=int(input())
U=N%(1000*M)
P=U//1000
#PをN人に適当に配る
#mCp mod(10**9) を求めればいい
ans=1
for i in range(1,P+1):
    ans=ans*(M+1-i)//i
print(ans%(10**9))