n=int(input())
m=int(input())
l=(n//1000)//m
k=n//1000-l*m
M=10**9
c=[0]*(m+1)
c[0]=1
for i in range(m):
  nc=[0]*(m+1)
  for j in range(m):
    nc[j]+=c[j]
    nc[j]%=M
    nc[j+1]+=c[j]
    nc[j+1]%=M
  c=nc
print(c[k])