n=int(input())
m=int(input())
r=n//1000%m
ans=1
div=1
for i in range(1,r+1):
    ans*=m-r+i
    div*=i
print(ans//div%1000000000)