money=int(input())
childs=int(input())
def t(v,r):
    s=1
    for vs in range(r+1,v+1):
        s=s*vs
    return s
num1k=int((money-int(money/childs/1000)*1000*childs)/1000)
print(t(childs,num1k)//t(childs-num1k,1)%1000000000 )