class Calc0129
  def initialize(args)
    args = args.map { |l| l.chomp.split(/\s+/) }
    @n = args.shift.first.to_i
    @m = args.shift.first.to_i
  end

  def run
    k = @n / 1000 % @m
    (1..@m).to_a.combination(k).size % 10 ** 9
  end
end

puts Calc0129.new(STDIN.readlines).run if __FILE__ == $0