def combi n,k
    if k == 0
        return 1
    else
        return (n - k + 1) * combi(n,k - 1) / k
    end
end

n = gets.to_i / 1000
m = gets.to_i
p combi(m,[m - n % m,n % m].min) % 1000000000