N=int(raw_input())
M=int(raw_input())
n=(N-(N/M/1000)*1000*M)/1000
ans=1
for i in range(n):
    ans*=M-i
    ans/=i+1
print ans%1000000000