n=int(input())
m=int(input())

amari = (n%(m*1000)) // 1000
mod=10**9

def  nCk(n,k):
    x,y=1,1
    for i in range(n,n-k,-1):
        x*=i
    for i in range(k,0,-1):
        y*=i
    return x//y

if m <= amari:
    print(1)
else:
    print(nCk(m,amari)%mod)