#coding: utf-8
##yuki_129
import math

def comb(n,m):
 return math.factorial(n)/(math.factorial(m)*math.factorial(n-m))
 
n=int(raw_input())
m=int(raw_input())

x=n/1000
y=x%m
res=comb(m,y)%1000000000

print res