n = gets.to_i

ans = 0
while n>0 do
  if (n&1 == 1)
    ans += 1
    ans %= 1004535809
  end
  n >>= 1
end

puts ans