n, k = gets.split.map(&:to_i)
arr = []
for num in 1..n do
  arr.push(num ** k)
end

result = arr.inject(:+) % (10 ** 9)
puts result