def nCr(n,r):
    r=min(r,n-r)
    X=1
    for i in range(1,r+1):
        X*=n-i+1
        X//=i
    return X%Mod
N=int(input())
M=int(input())
Mod=10**9


R=N%(1000*M)//1000
print(nCr(M,R))